login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 10
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), ... [That is, T(n,k) = U(n-k, k) for 0 <= k <= n and U(m,s) = T(m+s, s) for m,s >= 0.]

From Petros Hadjicostas, Jul 16 2020: (Start)

We explain the parallelogram definition of T(n,k).

    T(0,0) *

           |\

           | \

           |  * T(k,k)

  T(n-k,0) *  |

            \ |

             \|

              * T(n,k)

The definition implies that T(n,k) is the sum of all T(i,j) such that (i,j) has integer coordinates over the set

{(i,j): a(1,0) + b(1,1), 0 <= a <= n-k, 0 <= b <= k} - {(n,k)}.

The parallelogram can sometimes be degenerate; e.g., when k = 0 or n = k. (End)

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

From Michel Marcus and Petros Hadjicostas, Jul 16 2020: (Start)

Robeva and Sun (2020) let A(m,n) = U(m-1, n-1) be the number of subdivisions of a 2-row grid with m points on the top and n points at the bottom (and such that the lower left point is the origin).

The authors proved that A(m,n) = 2*(A(m,n-1) + A(m-1,n) - A(m-1,n-1)) for m, n >= 2 (with (m,n) <> (2,2)), which is equivalent to a similar recurrence for U(n,k) given in the Formula section below. (They did not explicitly specify the value of A(1,1) = U(0,0) because they did not care about the number of subdivisions of a degenerate polygon with only one side.)

They also proved that, for (m,n) <> (1,1), A(m,n) = (2^(m-2)/(n-1)!) * Q_n(m) =

= (2^(m-2)/(n-1)!) * Sum_{k=1..n} A336244(n,k) * m^(n-k), where Q_n(m) is a polynomial in m of degree n-1. (End)

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; see Fig. 5, p. 1729.

Elina Robeva and Melinda Sun, Bimonotone Subdivisions of Point Configurations in the Plane, arXiv:2007.00877 [math.CO], 2020.

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).

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) = 2*U(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)

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; and 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-t*z)/(1 - 2*z - 2*t*z + 2*t*z^2). (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 2*U(n,k-1) + 2*U(n-1,k) - 2*U(n-1,k-1). - David W. Wilson; corrected in the case k > n by Robert Israel, Jun 15 2011 [Corrected by Petros Hadjicostas, Jul 16 2020]

U(n,k) = binomial(n,k) * 2^(n-1) * hypergeom([-k,-k], [n+1-k], 2) if n >= k >= 0 with (n,k) <> (0,0). - Robert Israel, Jun 15 2011 [Corrected by Petros Hadjicostas, Jul 16 2020]

U(n,k) = Sum_{0 <= i+j <= n+k-1} (-1)^j*C(i+j+1, j)*C(n+i, n)*C(k+i, k). - Masato Maruoka, Dec 10 2019

EXAMPLE

Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins

   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;

  ...

T(5,2) = 76 is the sum of the elements above it in the parallelogram bordered by T(0,0), T(5-2,0) = T(3,0), T(2,2) and T(5,2). We of course exclude T(5,2) from the summation. Thus

T(5,2) = Sum_{a=0..5-2, b=0..2, (a,b) <> (5-2,2)} T(a(1,0) + b(1,1)) =

= (1 + 1 + 2) + (1 + 3 + 8) + (2 + 8 + 26) + (4 + 20) = 76. [Edited by Petros Hadjicostas, Jul 16 2020]

From Petros Hadjicostas, Jul 16 2020: (Start)

Square array U(n,k) (with rows n >= 0 and columns k >= 0) begins

   1,   1,   2,    4,    8, ...

   1,   3,   8,   20,   48, ...

   2,   8,  26,   76,  208, ...

   4,  20,  76,  252,  768, ...

   8,  48, 208,  768, 2568, ...

  16, 112, 544, 2208, 8016, ...

  ...

Consider the following 2-row grid with n = 3 points at the top and k = 2 points at the bottom:

   A  B  C

   *--*--*

   |    /

   |   /

   *--*

   D  E

The sets of the dividing internal lines of the A(3,2) = U(3-1, 2-1) = 8 subdivisions of the above 2-row grid are as follows: { }, {DC}, {DB}, {EB}, {EA}, {DB, DC}, {DB, EB}, and {EA, EB}. See Robeva and Sun (2020).

These are the 2-compositions of n = 3 with sum of first row entries equal to k = 1:

[1; 2], [0,1; 2,0], [0,1; 1,1], [1,0; 0,2], [1,0; 1,1], [0,0,1; 1,1,0], [0,1,0; 1,0,1], and [1,0,0; 0,1,1]. We have T(3,2) = 8 such matrices. See Emeric Deutsch's contribution above. See also Section 2 in Castiglione et al. (2007). (End)

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 add((-1)^j*2^(n-j-1)*binomial(k, j)*binomial(n-j, k), j = 0 .. min(k, n-k)) fi 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. A008288, A035002, A059226, A059283, A181292, A336244.

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 03:34 EDT 2020. Contains 336436 sequences. (Running on oeis4.)