cp's OEIS Frontend

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

%I A141811 #30 Nov 11 2024 20:30:09
%S A141811 1,3,1,10,3,2,35,10,6,5,126,35,20,15,14,462,126,70,50,42,42,1716,462,
%T A141811 252,175,140,126,132,6435,1716,924,630,490,420,396,429,24310,6435,
%U A141811 3432,2310,1764,1470,1320,1287,1430,92378,24310,12870,8580,6468,5292,4620,4290,4290,4862
%N A141811 Partial Catalan numbers: triangle read by rows n = 1, 2, 3, ... and columns k = 0, 1, ..., n-1.
%C A141811 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.
%C A141811 A breach can occur only at an odd numbered position 1, 3, 5, ..., 2n - 1.
%C A141811 The probability of a breach not occurring is: C(n)/((2n)!/(n! * n!)) = 1/(n + 1).
%C A141811 The probability of a breach occurring is: n / (n + 1).
%C A141811 The probability of a breach occurring at position 2k+1 is: R(n,k)/[(2n)!/(n!* n!)].
%H A141811 Michael De Vlieger, <a href="/A141811/b141811.txt">Table of n, a(n) for n = 1..11325</a> (rows 1 <= n <= 150, flattened).
%H A141811 Sergio Caracciolo, Matteo P. D'Achille, Vittorio Erba, Andrea Sportiello, <a href="https://arxiv.org/abs/1904.10867">The Dyck bound in the concave 1-dimensional random assignment model</a>, arXiv:1904.10867 [cond-mat.dis-nn], 2019.
%F A141811 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).
%F A141811 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.
%F A141811 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:
%F A141811 R(n, 0) = C(0) * V(n)
%F A141811 R(n, 1) = C(1) * V(n - 1)
%F A141811 R(n, 2) = C(2) * V(n - 2)
%F A141811 ...
%F A141811 R(n, n - 1) = C(n - 1) * V(1)
%F A141811 C(n) = BinomialCoefficient(2n, n) - Sum[ R(n, k) for k = 0 to n - 1 ]
%F A141811 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.
%F A141811 T(n, k) = (n-k+1)*Catalan(k)*Catalan(n-k)/2. - _G. C. Greubel_, Jun 06 2019
%e A141811 Triangle begins as:
%e A141811       1;
%e A141811       3,     1;
%e A141811      10,     3,     2;
%e A141811      35,    10,     6,    5;
%e A141811     126,    35,    20,   15,   14;
%e A141811     462,   126,    70,   50,   42,   42;
%e A141811    1716,   462,   252,  175,  140,  126,  132;
%e A141811    6435,  1716,   924,  630,  490,  420,  396,  429;
%e A141811   24310,  6435,  3432, 2310, 1764, 1470, 1320, 1287, 1430;
%e A141811   92378, 24310, 12870, 8580, 6468, 5292, 4620, 4290, 4290, 4862;
%e A141811 ...
%e A141811 C(0) = 1
%e A141811 R(1, 0) = C(0) * V(1) = 1
%e A141811 C(1) = (2!) / (1! * 1!) - R(1, 0) = 2 - 1 = 1
%e A141811 R(2, 0) = C(0) * V(2) = 3
%e A141811 R(2, 1) = C(1) * V(1) = 1
%e A141811 C(2) = (4!) / (2! * 2!) - [ R(2, 0) + R(2, 1) ] = 6 - [ 4 ] = 2
%e A141811 R(3, 0) = C(0) * V(3) = 10
%e A141811 R(3, 1) = C(1) * V(2) = 3
%e A141811 R(3, 2) = C(2) * V(1) = 2
%e A141811 C(3) = (6!) / (3! * 3!) - [ R(3, 0) + R(3, 1) + R(3, 2) ] = 20 - [ 15 ] = 5
%t A141811 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 *)
%o A141811 (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.
%o A141811 Let C(0) = 1
%o A141811 For i = 1 to 10
%o A141811 Let V(i) = (2i)! / ( i! * i! )
%o A141811 Next i
%o A141811 Let Total = 0
%o A141811 For n = 1 to 10
%o A141811 For k = 0 to n - 1
%o A141811 Let R(n, k) = C(k) * V(n - k)
%o A141811 Let Total = Total + R(n, k)
%o A141811 Next k
%o A141811 Let C(n) = (2n)! / ( n! * n! ) - Total
%o A141811 Next n
%o A141811 (PARI)
%o A141811 catalan(n) = binomial(2*n,n)/(n+1);
%o A141811 T(n,k) = (n-k+1)*catalan(k)*catalan(n-k)/2;
%o A141811 for(n=1,10, for(k=0,n-1, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Jun 06 2019
%o A141811 (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
%o A141811 (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
%o A141811 (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
%Y A141811 Cf. A000108, A014138, A009766, A033184.
%K A141811 nonn,tabl
%O A141811 1,2
%A A141811 _Gerald P. Del Fiacco_, Jul 12 2008
%E A141811 a(27)=126 corrected by _Jean-François Alcover_, Sep 27 2011