|
| |
|
|
A105306
|
|
Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having the top of the rightmost column at height k.
|
|
8
|
|
|
|
1, 1, 1, 2, 2, 1, 4, 5, 3, 1, 8, 12, 9, 4, 1, 16, 28, 25, 14, 5, 1, 32, 64, 66, 44, 20, 6, 1, 64, 144, 168, 129, 70, 27, 7, 1, 128, 320, 416, 360, 225, 104, 35, 8, 1, 256, 704, 1008, 968, 681, 363, 147, 44, 9, 1, 512, 1536, 2400, 2528, 1970, 1182, 553, 200, 54, 10, 1, 1024
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Let A be the array
1, 0, 0, 0, 0, 0, ...
0, 1, 0, 0, 0, 0, ...
1, 0, 1, 0, 0, 0, ...
0, 2, 0, 1, 0, 0, ...
1, 0, 3, 0, 1, 0, ...
0, 3, 0, 4, 0, 1, ...
...
where columns are bin(n,k) with alternating zeros. (Row sums = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...(Fibonacci numbers).) Let P = infinite lower triangular Pascal triangle matrix (A007318). Form P * A: this gives the rows of the present sequence. [Comment corrected by Philippe Deléham, Dec 09 2008] (End)
T(n,k) is the number of nondecreasing Dyck paths of semilength n, having height of rightmost peak equal to k. Example: T(4,1)=4 because we have UDUDUDUD, UDUUDDUD, UUDDUDUD and UUUDDDUD, where U=(1,1) and D=(1,-1). Sum of row n = Fibonacci(2n-1) (A001519). Basically the same as A062110.
T(n,k) is the number of permutations of [n] with length n-k that avoid the patterns 321 and 3412. - Bridget Tenner, Sep 28 2005
T(2*n-1,n)/n = A001003(n-1) (little Schroeder numbers). Proof with Lagrange inversion of inverse of g.f. of A001003.
Row sums = odd-indexed Fibonacci numbers.
T(n,k) is the number of ideals in the fence Z(2n-1) with n-k elements of rank 0. - Emanuele Munarini, Mar 22 2011
Triangle T(n,k), 1 <= k <= n, read by rows, given by (0,1,1,0,0,0,0,0,0,0,...) DELTA (1,0,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 30 2011
T(n,k) is the number of permutations of [n] for which k is equal to both the length and reflection length. - Bridget Tenner, Feb 22 2012
|
|
|
REFERENCES
|
V. E. Hoggatt, Jr. and Marjorie Bicknell, editors: "A Primer for the Fibonacci Numbers", 1970, p. 87.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = sum(binomial(k+j, k-1)*binomial(n-k-1, j), j=0..n-k-1) (0<=k<=n). (This appears to be incorrect. - Emanuele Munarini, Mar 22 2011)
G.f.: t*z*(1-z)/(1 - 2*z - t*z*(1-z)).
T(n,k) = Sum_{i=0..n-k} binomial(k+1,i)*binomial(n-i,k)*(-1)^i*2^(n-k-i).
T(n,k) = Sum_{i=0..n-k} binomial(k+1,i)*M(i,n-k-i)*2^(n-k-i), where M(n,k) = n*(n+1)*(n+2)*...*(n+k-1)/k!. (End)
T(n,k) = 2*T(n-1,k) + T(n-1,k-1) - T(n-2,k-1), T(0,0) = T(1,0) = T(1,1) = 1, T(n,k) = 0 if k>n or if k<0. - Philippe Deléham, Oct 30 2013
|
|
|
EXAMPLE
|
Triangle begins:
1;
1, 1;
2, 2, 1;
4, 5, 3, 1;
8, 12, 9, 4, 1;
16, 28 25, 14, 5, 1;
32, 64, 66, 44, 20, 6, 1;
64, 144, 168, 129, 70, 27, 7, 1;
...
Production matrix is
1, 1;
1, 1, 1;
0, 1, 1, 1;
-1, 0, 1, 1, 1;
0, -1, 0, 1, 1, 1;
2, 0, -1, 0, 1, 1, 1;
0, 2, 0, -1, 0, 1, 1, 1;
-5, 0, 2, 0, -1, 0, 1, 1, 1;
0, -5, 0, 2, 0, -1, 0, 1, 1, 1;
14, 0, -5, 0, 2, 0, -1, 0, 1, 1, 1; (End)
|
|
|
MAPLE
|
T:=proc(n, k) if k<n-1 then sum(binomial(k+j, k-1)*binomial(n-k-1, j), j=0..n-k-1) elif k=n-1 then n-1 elif k=n then 1 else 0 fi end: for n from 1 to 12 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
|
|
|
MATHEMATICA
|
t[n_, k_] := 2^(n-2*k-1)*Binomial[n, k]*Hypergeometric2F1[-k-1, -k, -n, -1]; t[n_, n_] = 1; Table[t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 28 2014 *)
|
|
|
PROG
|
(Maxima) create_list(sum(binomial(k+1, i)*binomial(n-i, k)*(-1)^i*2^(n-k-i), i, 0, n-k), n, 0, 8, k, 0, n); /* Emanuele Munarini, Mar 22 2011 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
