OFFSET
1,2
COMMENTS
From the set of all possible sequences of length 2n consisting of any arbitrary arrangement of n X's and n Y's in positions 1 through 2n, each entry R(n, k) in the above triangle is hereby defined as a partial Catalan number, that is, the number of sequences wherein position 2k + 1 is the first position for which the accumulated number of Y's from left-to-right exceeds the accumulated number of X's from left-to-right. This event will be referred to as a breach.
A breach can occur only at an odd numbered position 1, 3, 5, ..., 2n - 1.
The probability of a breach not occurring is: C(n)/((2n)!/(n! * n!)) = 1/(n + 1).
The probability of a breach occurring is: n / (n + 1).
The probability of a breach occurring at position 2k+1 is: R(n,k)/[(2n)!/(n!* n!)].
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150, flattened).
Sergio Caracciolo, Matteo P. D'Achille, Vittorio Erba, Andrea Sportiello, The Dyck bound in the concave 1-dimensional random assignment model, arXiv:1904.10867 [cond-mat.dis-nn], 2019.
FORMULA
If k > 0, the first 2k positions consist of a subsequence of k X's and k Y's. If more Y's than X's were accumulated, a breach already would have occurred. If more X's than Y's were accumulated, one additional Y in position 2k + 1 would not cause a breach. Furthermore, the k X's and k Y's must have been arranged in such a way that there is no point within the first 2k positions at which the accumulated number of Y's exceeds the number of X's. Therefore the number of such subsequences is the Catalan number C(k).
Starting at position 2k + 1, there are 2n - 2k positions remaining, half of which are to be occupied with X's and half of which are to be occupied with Y's . The number of possible arrangements of these X's and Y's is the BinomialCoefficient(2n - 2k, n - k). Half of these arrangements will have a Y in position 2k + 1 thereby causing a breach. Therefore the number of sequences that will cause a breach to occur at position 2k + 1 is R(n, k) = C(k) * V(n - k) where C(0) = 1 and where C(1), C(2), C(3), etc. are the Catalan numbers and where V(i) = BinomialCoefficient(2i, i) / 2.
The Sum[ R(n, k) for k = 0 to n - 1 ] is the number of sequences in which a breach will occur. The total possible number of sequences is BinomialCoefficient(2n, n). So beginning with the arbitrary definition of C(0) = 1, the Catalan numbers can be calculated in a recursive manner as the partial Catalan numbers are being derived. For a given value of n, the algorithm is:
R(n, 0) = C(0) * V(n)
R(n, 1) = C(1) * V(n - 1)
R(n, 2) = C(2) * V(n - 2)
...
R(n, n - 1) = C(n - 1) * V(1)
C(n) = BinomialCoefficient(2n, n) - Sum[ R(n, k) for k = 0 to n - 1 ]
This algorithm allows each successive row of partial Catalan numbers to be derived and it provides the next Catalan number which is needed for the next row.
T(n, k) = (n-k+1)*Catalan(k)*Catalan(n-k)/2. - G. C. Greubel, Jun 06 2019
EXAMPLE
Triangle begins as:
1;
3, 1;
10, 3, 2;
35, 10, 6, 5;
126, 35, 20, 15, 14;
462, 126, 70, 50, 42, 42;
1716, 462, 252, 175, 140, 126, 132;
6435, 1716, 924, 630, 490, 420, 396, 429;
24310, 6435, 3432, 2310, 1764, 1470, 1320, 1287, 1430;
92378, 24310, 12870, 8580, 6468, 5292, 4620, 4290, 4290, 4862;
...
C(0) = 1
R(1, 0) = C(0) * V(1) = 1
C(1) = (2!) / (1! * 1!) - R(1, 0) = 2 - 1 = 1
R(2, 0) = C(0) * V(2) = 3
R(2, 1) = C(1) * V(1) = 1
C(2) = (4!) / (2! * 2!) - [ R(2, 0) + R(2, 1) ] = 6 - [ 4 ] = 2
R(3, 0) = C(0) * V(3) = 10
R(3, 1) = C(1) * V(2) = 3
R(3, 2) = C(2) * V(1) = 2
C(3) = (6!) / (3! * 3!) - [ R(3, 0) + R(3, 1) + R(3, 2) ] = 20 - [ 15 ] = 5
MATHEMATICA
nmax = 9; r[n_, k_] := CatalanNumber[k]*Binomial[2*(n - k), n - k]/2; Flatten[ Table[ r[n, k], {n, 1, nmax}, {k, 0, n - 1}]] (* Jean-François Alcover, Sep 27 2011 *)
PROG
(BASIC) ' Provides the partial Catalan numbers R(n, k) and the Catalan numbers C(n) for n = 1 to 10 and for k = 0 to n - 1.
Let C(0) = 1
For i = 1 to 10
Let V(i) = (2i)! / ( i! * i! )
Next i
Let Total = 0
For n = 1 to 10
For k = 0 to n - 1
Let R(n, k) = C(k) * V(n - k)
Let Total = Total + R(n, k)
Next k
Let C(n) = (2n)! / ( n! * n! ) - Total
Next n
(PARI)
catalan(n) = binomial(2*n, n)/(n+1);
T(n, k) = (n-k+1)*catalan(k)*catalan(n-k)/2;
for(n=1, 10, for(k=0, n-1, print1(T(n, k), ", "))) \\ G. C. Greubel, Jun 06 2019
(Magma) [[(n-k+1)*Catalan(k)*Catalan(n-k)/2: k in [0..n-1]]: n in [1..10]]; // G. C. Greubel, Jun 06 2019
(Sage) [[(n-k+1)*catalan_number(k)*catalan_number(n-k)/2 for k in (0..n-1)] for n in (1..10)] # G. C. Greubel, Jun 06 2019
(GAP) Flat(List([1..10], n-> List([0..n-1], k-> Binomial(2*k, k)* Binomial(2*(n-k), n-k)/(2*(k+1)) ))); # G. C. Greubel, Jun 06 2019
CROSSREFS
KEYWORD
AUTHOR
Gerald P. Del Fiacco, Jul 12 2008
EXTENSIONS
a(27)=126 corrected by Jean-François Alcover, Sep 27 2011
STATUS
approved