A059797 Second in a series of arrays counting standard tableaux by partition type.

2, 5, 5, 9, 16, 9, 14, 35, 35, 14, 20, 64, 90, 64, 20, 27, 105, 189, 189, 105, 27, 35, 160, 350, 448, 350, 160, 35, 44, 231, 594, 924, 924, 594, 231, 44, 54, 320, 945, 1728, 2100, 1728, 945, 320, 54, 65, 429, 1430, 3003, 4290, 4290, 3003, 1430, 429, 65

Offset

0,1

Comments

The first array in the series is Pascal's triangle, A007318. The initial partition for each subsequent array in the series is chosen as described in A053445. When cells are squared, as in A008459, row sums yield 1, 2, 6, 24, ... (A000142). E.g., (1 + 16 + 36 + 16 + 1) + (25 + 25) = 70 + 50 = 120 using row five from A007318 and row two from this array.

Number of lattice paths from (0,0) to (n,k) in exactly n+k+2 steps. Moves allowed: (0,1), (0,-1), (-1,0) and (1,0). Paths must stay in Quadrant I but may touch the axes. - Juan Luis Vargas-Molina, Mar 03 2014

References

Stanton and White, Constructive Combinatorics, 1986, pp. 84, 91.

Links

Table of n, a(n) for n=0..54.

Cyann Donnot, Antoine Genitrini, Yassine Herida, Unranking Combinations Lexicographically: an efficient new strategy compared with others, hal-02462764 [cs] / [cs.DS] / [math] / [math.CO], 2020.

Antoine Genitrini and Martin Pépin, Lexicographic unranking of combinations revisited, hal-03040740v2 [cs.DM] [cs.DS] [math.CO], 2020.

Juan Luis Vargas-Molina, C++ Algorithm

Formula

T(row, col) = T(row-1, col-1) + T(row-1, col) + A007318(row+2, col+1). - Corrected by R. J. Mathar, Jan 27 2011

T(n,k) = (k+1)(n+k+4)FallingFactorial(n+k+2,n)/((n+1)!+n!) n,k >= 0. - Juan Luis Vargas-Molina, Mar 03 2014

Example

a(5) = 16 because we can write T(2,2) = T(1,2) + T(1,1) + A007318(4,2) = 5 + 5 + 6.
   2;
   5,   5;
   9,  16,   9;
  14,  35,  35,  14;
  20,  64,  90,  64,  20;
  27, 105, 189, 189, 105,  27;
T(n,k) as a grid for the first few lattice points. Where T(0,0)=2 since there are two ways to get to (0,0) with "0+0+2" steps under the move restrictions.
     k = 0  1   2   3    4    5
T(0,k) = 2  5   9   14   20   27
T(1,k) = 5  16  35  64   105  160
T(2,k) = 9  35  90  189  350  594
T(3,k) = 14 64  189 448  924  1728
T(4,k) = 20 105 350 924  2100 4290
T(5,k) = 27 160 594 1728 4290 9504
- Juan Luis Vargas-Molina, Mar 03 2014

Maple

A059797 := proc(n, k) option remember; if n <0 or k<0 or k>n then 0; else procname(n-1, k-1)+procname(n-1, k)+binomial(n+2, k+1) ; end if; end proc:
seq(seq( A059797(n, k), k=0..n), n=0..15) ; # R. J. Mathar, Jan 27 2011

Mathematica

t[n_, k_] /; (n < 0 || k < 0 || k > n) = 0; t[n_, k_] := t[n, k] = t[n - 1, k - 1] + t[n - 1, k] + Binomial[n + 2, k + 1]; Flatten[ Table[ t[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, Dec 20 2011, after R. J. Mathar *)
T[n_, k_] := (k + 1)(n + k +4) FactorialPower[k + n + 2, n]/(n! + (n + 1)!)
MatrixForm[Table[T[n, k], {n, 0, 10}, {k, 0, 10}]] (* Juan Luis Vargas-Molina, Mar 03 2014 *)

Crossrefs

Cf. A000041, A000142, A007318, A008459, A053445.

Sequence in context: A367642 A050175 A243333 * A173567 A288726 A344572

Adjacent sequences: A059794 A059795 A059796 * A059798 A059799 A059800

Keyword

nice,nonn,tabl

Author

Alford Arnold, Feb 22 2001

Status

approved