login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A141811 Partial Catalan numbers: triangle read by rows n = 1, 2, 3, ... and columns k = 0, 1, ..., n-1. 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 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

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

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 Jean-François Alcover, Sep 27 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 21:37 EST 2019. Contains 319206 sequences. (Running on oeis4.)