Gerald P. Del Fiacco - cp's OEIS frontend

User: Gerald P. Del Fiacco

Gerald P. Del Fiacco has authored 2 sequences.

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

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

Offset: 1

Gerald P. Del Fiacco, Jul 12 2008

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!)].

			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

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.

Cf. A000108, A014138, A009766, A033184.

' 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

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

[[(n-k+1)*Catalan(k)*Catalan(n-k)/2: k in [0..n-1]]: n in [1..10]]; // G. C. Greubel, Jun 06 2019

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 *)

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

[[(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

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

a(27)=126 corrected by Jean-François Alcover, Sep 27 2011

A098825 Triangle read by rows: T(n,k) = number of partial derangements, that is, the number of permutations of n distinct, ordered items in which exactly k of the items are in their natural ordered positions, for n >= 0, k = n, n-1, ..., 1, 0.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 6, 8, 9, 1, 0, 10, 20, 45, 44, 1, 0, 15, 40, 135, 264, 265, 1, 0, 21, 70, 315, 924, 1855, 1854, 1, 0, 28, 112, 630, 2464, 7420, 14832, 14833, 1, 0, 36, 168, 1134, 5544, 22260, 66744, 133497, 133496, 1, 0, 45, 240, 1890, 11088, 55650, 222480, 667485, 1334960, 1334961

Offset: 0

Gerald P. Del Fiacco, Nov 02 2004

In other words, T(n,k) is the number of permutations of n letters that are at Hammimg distance k from the identity permutation (cf. Diaconis, p. 112). - N. J. A. Sloane, Mar 02 2007

The sequence d(n) = 1, 0, 1, 2, 9, 44, 265, 1854, 14833, ... (A000166) is the number of derangements, that is, the number of permutations of n distinct, ordered items in which none of the items is in its natural ordered position.

			Assume d(0), d(1), d(2) are given. Then
  T(3, 3) = c(3, 3)*d(0) = (1)*(1) = 1;
  T(3, 2) = c(3, 2)*d(1) = (3)*(0) = 0;
  T(3, 1) = c(3, 1)*d(2) = (3)*(1) = 3;
  T(3, 0) = 3! - (1 + 0 + 3) = 6 - 4 = 2.
  d(3) = T(3, 0).
Triangle begins:
  1;
  1, 0;
  1, 0,  1;
  1, 0,  3,  2;
  1, 0,  6,  8,   9;
  1, 0, 10, 20,  45,  44;
  1, 0, 15, 40, 135, 264,  265;
  1, 0, 21, 70, 315, 924, 1855, 1854;
  ...

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.
Chris D. H. Evans, John Hughes and Julia Houston, Significance-testing the validity of idiographic methods: A little derangement goes a long way, British Journal of Mathematical and Statistical Psychology, 1 November 2002, Vol. 55, pp. 385-390.
Eric Weisstein's World of Mathematics, Partial Derangement

Mirror of triangle A008290.
Cf. A000166, A007318.
T(2n,n) gives A281262.

a098825 n k = a098825_tabl !! n !! k
a098825_row n = a098825_tabl !! n
a098825_tabl = map (zipWith (*) a000166_list) a007318_tabl
-- Reinhard Zumkeller, Dec 16 2013

t[0, 0] = 1; t[n_, k_] := Binomial[n, k]*k!*Sum[(-1)^j/j!, {j, 0, k}]; Flatten[ Table[ t[n, k], {n, 0, 10}, {k, 0, n}]] (* Robert G. Wilson v, Nov 04 2004 *)
T[n_, k_] := Binomial[n, n-k] Subfactorial[k];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 01 2021 *)
(* Sum-free code *)
T[n_, k_] = If[k==0,1,Binomial[n,k] Round[k!/E]];
Table[T[n, k],{n,0,12},{k,0,n}]//Flatten (* Manfred Boergens, Oct 25 2022 *)

from functools import cache
@cache
def T(n, k):  # (after Oliver Seipel)
    if k == 0: return 1
    if k == n: return (-1)**n + n * T(n-1, k-1)
    return (T(n-1, k) * n) // (n - k)
print([T(n, k) for n in range(11) for k in range(n+1)]) # Peter Luschny, Nov 30 2024

T(0, 0) = 1; d(0) = T(0, 0); for k = n, n-1, ..., 1, T(n, k) = c(n, k) d(n-k) where c(n, k) = n! / [(k!) (n-k)! ]; T(n, 0) = n! - [ T(n, n) + T(n, n-1) + ... + T(n, 1) ]; d(n) = T(n, 0).
T(n,k) = A008290(n,n-k). - Vladeta Jovovic, Sep 04 2006
Assuming a uniform distribution on S_n, the mean Hamming distance is n-1 and the variance is 1 (Diaconis, p. 117). - N. J. A. Sloane, Mar 02 2007
From Manfred Boergens, Oct 25 2022: (Start)
T(n, k) = (n!/(n-k)!)*Sum_{j=0..k} (-1)^j/j!.
T(n,0)=1; T(n, k) = C(n, k)*round(k!/e) = C(n,k)*A000166(k) = C(n, k)*floor(k!/e + 1/2) for k > 0. (End)
T(n, k) = (T(n-1, k)*n)/(n - k) for 0 < k < n, T(n, 0) = 1, and T(n, n) = (-1)^n + n*T(n-1, k-1). - Oliver Seipel, Nov 26 2024

More terms from Robert G. Wilson v, Nov 04 2004

cp's OEIS Frontend

User: Gerald P. Del Fiacco

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

BASIC

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions