1,2

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, 120, 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 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! ) ]

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.

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

The following Basic language program 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

Cf. A000108, A014138, A009766, A033184

Sequence in context: A126953 A134284 A134285 this_sequence A126954 A107870 A078817

Adjacent sequences: A141808 A141809 A141810 this_sequence A141812 A141813 A141814

nonn,tabl

Gerald P. Del Fiacco, gerrydelfiacco(AT)hotmail.com, Jul 12 2008