|
|
A047089
|
|
Array T read by antidiagonals: T(h,k)=number of paths consisting of steps from (0,0) to (h,k) such that each step has length 1 directed up or right and touches the line y=x/2 only at lattice points.
|
|
12
|
|
|
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 4, 3, 1, 1, 4, 7, 4, 4, 1, 1, 5, 11, 11, 8, 5, 1, 1, 6, 16, 22, 19, 13, 6, 1, 1, 7, 22, 38, 41, 19, 19, 7, 1, 1, 8, 29, 60, 79, 60, 38, 26, 8, 1, 1, 9, 37, 89, 139, 139, 98, 64, 34, 9, 1, 1, 10, 46, 126, 228, 278, 237, 98, 98, 43, 10, 1, 1, 11, 56, 172
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Comments from Timothy Y. Chow (tchow(AT)alum.mit.edu}, Nov 15 2006 on this sequence and A107027. "If you replace "the line y = x/2" with "the line y = x/(n-1)" in the definition of this sequence, then the formula for T(h,k) becomes (h+k choose k) - (n-1)*(h+k choose k-1).
"As for A107027, it has a combinatorial interpretation: T(n,k) is the number of paths of length n*k such that each step has length 1 directed up or right and touches the line y = x/(n-1) only at lattice points.
"To see this, let us avoid notational confusion by replacing the "k" in A047089 by "j". Then the formula above becomes (h+j choose j) - (n-1)*(h+j choose j-1).
"If we sum over all the points at a distance n*k from (0,0) - i.e. if we sum from j=0 to j=k and let h = n*k-j - then we get (n*k choose k) - (n-2) * sum_{j=0}^{k-1} (n*k choose j) This is equivalent to the formula you report for A107027."
|
|
LINKS
|
|
|
EXAMPLE
|
Diagonals (beginning on row 0): {1}; {1,1}; {1,1,1}; {1,2,2,1};...
|
|
PROG
|
(PARI) {T(n, k) = local(v); if( k<0 || k>n, 0, for(i=1, n+1, v=vector(i, j, if( j<2 || j>i-1, 1, v[j-1] + if( i%3 || i!=j+i\3, v[j])))); v[k+1])}; /* Michael Somos, Jan 28 2004 */
(PARI) {T(n, k) = if( k<0 || k>n, 0, if( n==0 && k==0, 1, T(n-1, k-1) + if( (n+1)%3 || n!=k+(n+1)\3, T(n-1, k))))}; /* Michael Somos, Jan 28 2004 */
|
|
CROSSREFS
|
See also the related array A107027.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
"Diagonals" in definition changed to "antidiagonals" by Michael Somos, Aug 19 2007
|
|
STATUS
|
approved
|
|
|
|