|
|
A049600
|
|
Array T read by diagonals; T(i,j) is the number of paths from (0,0) to (i,j) consisting of nonvertical segments (x(k),y(k))-to-(x(k+1),y(k+1)) such that 0 = x(1) < x(2) < ... < x(n-1) < x(n)=i, 0 = y(1) <= y(2) <= ... <= y(n-1) <= y(n)=j, for i >= 0, j >= 0.
|
|
29
|
|
|
0, 0, 1, 0, 1, 2, 0, 1, 3, 4, 0, 1, 4, 8, 8, 0, 1, 5, 13, 20, 16, 0, 1, 6, 19, 38, 48, 32, 0, 1, 7, 26, 63, 104, 112, 64, 0, 1, 8, 34, 96, 192, 272, 256, 128, 0, 1, 9, 43, 138, 321, 552, 688, 576, 256, 0, 1, 10, 53, 190, 501, 1002, 1520, 1696, 1280, 512
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
[Hetyei] calls a variant of this array (omitting the initial row of zeros) the asymmetric Delannoy numbers and shows how they arise in certain lattice path enumeration problems and a face enumeration problem associated to Jacobi polynomials. - Peter Bala, Oct 29 2008
T(n+k,n) is the dot product of a vector from the n-th row of Pascal's triangle A007318 with a vector created by the first n+1 values evaluated from the cycle index of symmetry group S(k). Example: T(4+3,4) = T(7,4) = {1,4,6,4,1}.{1,4,10,20,35} = 192. - Richard Turk, Sep 21 2017
The formula T(n,k) = Sum_{r=0..n-1} C(k+r,r)*C(n-1,r) (Paul D. Hanna, Oct 06 2006) counts the paths of the title by number, r, of interior vertices in the path. - David Callan, Nov 25 2021
|
|
LINKS
|
R. Cori and G. Hetyei, How to count genus one partitions, FPSAC 2014, Chicago, Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France, 2014, 333-344.
Robert Cori and Gabor Hetyei, Genus one partitions, in 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, pp. 333-344, <hal-01207612>.
|
|
FORMULA
|
T(n,k) = Sum_{j=0..n-1} C(k+j,j)*C(n-1,j). - Paul D. Hanna, Oct 06 2006
T(i,j) = 2*T(i-1,j) + T(i,j-1) - T(i-1,j-1) with T(0,0)=1 and T(i,j)=0 if one of i,j<0. - Theodore Kolokolnikov, Jul 05 2010
O.g.f.: t*x/(1 - (2*t+1)*x + t*x^2) = t*x + (t + 2*t^2)*x^2 + (t + 3*t^2 + 4*t^3)*x^3 + .... Taking the row reverse of this triangle (with an additional column of 1's) gives A055587. - Peter Bala, Sep 10 2012
T(i,0) = 2^(i-1) and for j>0, T(i,j) = T(i,j-1) + Sum_{k=0..i-1} T(k,j). - Glen Whitney, Aug 17 2021
T(n, k) = JacobiP(k - 1, 0, 1 - 2*k + n, 3) for k >= 1. - Peter Luschny, Nov 25 2021
|
|
EXAMPLE
|
Diagonals (each starting on row 1): {0}; {0,1}; {0,1,2}; ...
Array begins:
0 0 0 0 0 0 0 0 0 0 0 ...
1 1 1 1 1 1 1 1 1 1 1 ...
2 3 4 5 6 7 8 9 10 11 12 ...
4 8 13 19 26 34 43 53 64 76 89 ...
8 20 38 63 96 138 190 253 328 416 518 ...
16 48 104 192 321 501 743 1059 1462 1966 2586 ...
32 112 272 552 1002 1683 2668 4043 5908 8378 11584 ...
64 256 688 1520 2972 5336 8989 14407 22180 33028 47818 ...
Triangle begins:
0;
0, 1;
0, 1, 2;
0, 1, 3, 4;
0, 1, 4, 8, 8;
0, 1, 5, 13, 20, 16;
0, 1, 6, 19, 38, 48, 32;
0, 1, 7, 26, 63, 104, 112, 64;
...
(1, 0, -1/2, 1/2, 0, 0, 0, ...) DELTA (0, 2, 0, 0, 0, ...) where DELTA is the operator defined in A084938 begins:
1;
1, 0;
1, 2, 0;
1, 3, 4, 0;
1, 4, 8, 8, 0;
1, 5, 13, 20, 16, 0;
1, 6, 19, 38, 48, 32, 0;
1, 7, 26, 63, 104, 112, 64, 0;
|
|
MAPLE
|
add(binomial(k+j, j)*binomial(n-1, j), j=0..n-1) ;
|
|
MATHEMATICA
|
t[n_, k_] := Hypergeometric2F1[ n-k+1, 1-k, 1, -1] // Floor; Table[t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 09 2013 *)
t[n_, k_] := Sum[LaguerreL[n-k, i, 0]* LaguerreL[k-i, i, 0], {i, 0, k}] //Floor; Table[t[n, k], {n, 0, 16}, {k, -1, n}] (* Richard Turk, Sep 08 2017 *)
T[n_, k_] := If[k == 0, 0, JacobiP[k - 1, 0, 1 - 2*k + n, 3]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Peter Luschny, Nov 25 2021 *)
|
|
PROG
|
(PARI) {A(i, j) = polcoeff( (x / (1 - 2*x)) * ((1 - x) / (1 - 2*x))^j + x * O(x^i), i)}; /* Michael Somos, Oct 01 2003 */
(PARI) T(n, k)=sum(j=0, n-1, binomial(k+j, j)*binomial(n-1, j)) \\ Paul D. Hanna, Oct 06 2006
(Haskell)
a049600 n k = a049600_tabl !! n !! k
a049600_row n = a049600_tabl !! n
a049600_tabl = [0] : map (0 :) a208341_tabl
|
|
CROSSREFS
|
Diagonal sums are even-indexed Fibonacci numbers. Alternating (+-) diagonal sums are signed Fibonacci numbers.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|