|
| |
|
|
A059576
|
|
Summatory Pascal triangle T(n,k) (0 <= k <= n) read by rows. Top entry is 1. Each entry is the sum of the parallelogram above it.
|
|
9
|
|
|
|
1, 1, 1, 2, 3, 2, 4, 8, 8, 4, 8, 20, 26, 20, 8, 16, 48, 76, 76, 48, 16, 32, 112, 208, 252, 208, 112, 32, 64, 256, 544, 768, 768, 544, 256, 64, 128, 576, 1376, 2208, 2568, 2208, 1376, 576, 128, 256, 1280, 3392, 6080, 8016, 8016, 6080, 3392, 1280, 256
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
We may also relabel the entries as U(0,0), U(1,0), U(0,1), U(2,0), U(1,1), U(0,2), U(3,0), ...
From Jon Stadler (jstadler(AT)capital.edu), Apr 30 2003: (Start)
U(n,k) is the number of ways of writing the vector (n,k) as an ordered sum of vectors, equivalently, the number of paths from (0,0) to (n,k) in which steps may be taken from (i,j) to (p,q) provided (p,q) is to the right or above (i,j).
2*U(n,k) = Sum_{i<=n,j<=k} U(i,j).
U(n,k) = 2U(n-1,k) + Sum_{i<k} U(n,i).
U(n,k) = Sum_{j=0..n+k} C(n,j-k+1)*C(k,j-n+1)*2^j. (End)
U(n,k) = 0 if k < 0; else U(k,n) if k > n; else 1 if n <= 1; else 3 if n=2 and k=1; else 2U(n-1,k-1) + 2U(n-1,k) - 2U(n-2,k-1). - David W. Wilson
U(n,k) = binomial(n,n-k) * 2^(n-k) * hypergeom([-k,-k],[n+1-k],2) if n >= k. - Robert Israel, Jun 15 2011
T(n,k) is the number of 2-compositions of n having sum of the entries of the first row equal to k (0 <= k <= n). A 2-composition of n is a nonnegative matrix with two rows, such that each column has at least one nonzero entry and whose entries sum up to n. - Emeric Deutsch, Oct 12 2010
|
|
|
LINKS
|
Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, Combinatorial aspects of L-convex polyominoes, European Journal of Combinatorics, 28 (6) (2007), 1724-1741.
Index entries for triangles and arrays related to Pascal's triangle
|
|
|
FORMULA
|
G.f. U(z, w) = Sum_{n >= 0, k >= 0} U(n, k)*z^n*w^k = Sum{n >= 0, k >= 0} T(n, k)*z^(n-k)*w^k = (1-z)*(1-w)/(1 - 2*w - 2*z + 2*z*w).
Maple code gives another explicit formula for U(n, k).
T(n, k) = 2*(T(n-1, k-1) + T(n-1, k)) - (2 - 0^(n-2))*T(n-2, k-1) for n > 1 and 1 < k < n, T(n, 0) = T(n, n) = 2*T(n-1, 0) for n > 0, T(0, 0) = 1. - Reinhard Zumkeller, Dec 03 2004
From Emeric Deutsch, Oct 12 2010: (Start)
Sum_{k=0..n} k*T(n,k) = A181292(n).
T(n,k) = Sum_{j=0..min(k,n-k)} (-1)^j*2^(n-j-1)*binomial(k,j)*binomial(n-j,k) for (n,k) =/ (0,0).
G.f. = G(t,z) = (1-z)(1-tz)/(1 - 2z - 2tz + 2tz^2). (End)
|
|
|
EXAMPLE
|
Triangle begins
1;
1, 1;
2, 3, 2;
4, 8, 8, 4;
8, 20, 26, 20, 8;
...
T(5,2) is the sum of the elements above it in the parallelogram bordered by T(0,0), T(3,0), T(2,2) and T(5,2).
|
|
|
MAPLE
|
A059576 := proc(n, k) local b, t1; t1 := min(n+k-2, n, k); add( (-1)^b * 2^(n+k-b-2) * (n+k-b-2)! * (1/(b! * (n-b)! * (k-b)!)) * (-2 * n-2 * k+2 * k^2+b^2-3 * k * b+2 * n^2+5 * n * k-3 * n * b), b=0..t1); end;
T := proc (n, k) if k <= n then sum((-1)^j*2^(n-j-1)*binomial(k, j)*binomial(n-j, k), j = 0 .. min(k, n-k)) else end if end proc: 1; for n to 10 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form # Emeric Deutsch, Oct 12 2010
|
|
|
MATHEMATICA
|
t[0, 0] = 1; t[n_, k_] := 2^(n-k-1)*n!*Hypergeometric2F1[ -k, -k, -n, -1 ] / (k!*(n-k)!); Flatten[ Table[ t[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, Feb 01 2012, after Robert Israel *)
|
|
|
PROG
|
(Haskell)
a059576 n k = a059576_tabl !! n !! k
a059576_row n = a059576_tabl !! n
a059576_tabl = [1] : map fst (iterate f ([1, 1], [2, 3, 2])) where
f (us, vs) = (vs, map (* 2) ws) where
ws = zipWith (-) (zipWith (+) ([0] ++ vs) (vs ++ [0]))
([0] ++ us ++ [0])
-- Reinhard Zumkeller, Dec 03 2012
|
|
|
CROSSREFS
|
Cf. A035002, A059226, A008288, A059283.
First diagonals give A000079, A001792. T(2n, n) gives A052141. Row sums give A003480.
Sequence in context: A318176 A105070 A154578 * A274803 A274749 A247936
Adjacent sequences: A059573 A059574 A059575 * A059577 A059578 A059579
|
|
|
KEYWORD
|
easy,nonn,tabl,nice
|
|
|
AUTHOR
|
Floor van Lamoen, Jan 23 2001
|
|
|
EXTENSIONS
|
David W. Wilson's formula in the case k > n corrected by Robert Israel, Jun 15 2011
|
|
|
STATUS
|
approved
|
| |
|
|
