

A141811


Partial Catalan numbers: triangle read by rows n = 1, 2, 3, ... and columns k = 0, 1, ..., n1.


0



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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
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 lefttoright exceeds the accumulated number of X's from lefttoright. 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

Table of n, a(n) for n=1..45.


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.


EXAMPLE

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}]] (* JeanFranç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


CROSSREFS

Cf. A000108, A014138, A009766, A033184.
Sequence in context: A126953 A134284 A134285 * A291538 A280787 A126954
Adjacent sequences: A141808 A141809 A141810 * A141812 A141813 A141814


KEYWORD

nonn,tabl


AUTHOR

Gerald P. Del Fiacco, Jul 12 2008


EXTENSIONS

a(27)=126 corrected by JeanFrançois Alcover, Sep 27 2011


STATUS

approved



