This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A059576 #102 Aug 05 2024 06:01:12
%S A059576 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,
%T A059576 208,112,32,64,256,544,768,768,544,256,64,128,576,1376,2208,2568,2208,
%U A059576 1376,576,128,256,1280,3392,6080,8016,8016,6080,3392,1280,256
%N 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.
%C A059576 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.]
%C A059576 From _Petros Hadjicostas_, Jul 16 2020: (Start)
%C A059576 We explain the parallelogram definition of T(n,k).
%C A059576 T(0,0) *
%C A059576 |\
%C A059576 | \
%C A059576 | * T(k,k)
%C A059576 T(n-k,0) * |
%C A059576 \ |
%C A059576 \|
%C A059576 * T(n,k)
%C A059576 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
%C A059576 {(i,j): a(1,0) + b(1,1), 0 <= a <= n-k, 0 <= b <= k} - {(n,k)}.
%C A059576 The parallelogram can sometimes be degenerate; e.g., when k = 0 or n = k. (End)
%C A059576 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
%C A059576 From _Michel Marcus_ and _Petros Hadjicostas_, Jul 16 2020: (Start)
%C A059576 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).
%C A059576 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.)
%C A059576 They also proved that, for (m,n) <> (1,1), A(m,n) = (2^(m-2)/(n-1)!) * Q_n(m) =
%C A059576 = (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)
%C A059576 With the square array notation of Petros Hadjicostas, Jul 16 2020 below, U(i,j) is the number of lattice paths from (0,0) to (i,j) whose steps move north or east or have positive slope. For example, representing a path by its successive lattice points rather than its steps, U(1,2) = 8 counts {(0,0),(1,2)}, {(0,0),(0,1),(1,2)}, {(0,0),(0,2),(1,2)}, {(0,0),(1,0),(1,2)}, {(0,0),(1,1),(1,2)}, {(0,0),(0,1),(0,2),(1,2)}, {(0,0),(0,1),(1,1),(1,2)}, {(0,0),(1,0),(1,1),(1,2)}. If north (vertical) steps are excluded, the resulting paths are counted by A049600. - _David Callan_, Nov 25 2021
%H A059576 Reinhard Zumkeller, <a href="/A059576/b059576.txt">Rows n = 0..120 of triangle, flattened</a>
%H A059576 G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.ejc.2006.06.020">Combinatorial aspects of L-convex polyominoes</a>, European Journal of Combinatorics, 28(6) (2007), 1724-1741; see Fig. 5, p. 1729.
%H A059576 Fang, E., Jenkins, J., Lee, Z., Li, D., Lu, E., Miller, S. J., ... & Siktar, J. (2019). <a href="https://arxiv.org/abs/1906.10645">Central Limit Theorems for Compound Paths on the 2-Dimensional Lattice</a>, arXiv preprint arXiv:1906.10645. Also Fib. Q., 58:1 (2020), 208-225.
%H A059576 Elina Robeva and Melinda Sun, <a href="https://arxiv.org/abs/2007.00877">Bimonotone Subdivisions of Point Configurations in the Plane</a>, arXiv:2007.00877 [math.CO], 2020.
%H A059576 <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>
%F A059576 T(n, n-1) = A001792(n-1).
%F A059576 T(2*n, n) = A052141(n).
%F A059576 Sum_{k=0..n} T(n, k) = A003480(n).
%F A059576 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).
%F A059576 Maple code gives another explicit formula for U(n, k).
%F A059576 From Jon Stadler (jstadler(AT)capital.edu), Apr 30 2003: (Start)
%F A059576 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).
%F A059576 2*U(n,k) = Sum_{i <= n, j <= k} U(i,j).
%F A059576 U(n,k) = 2*U(n-1,k) + Sum_{i < k} U(n,i).
%F A059576 U(n,k) = Sum_{j=0..n+k} C(n,j-k+1)*C(k,j-n+1)*2^j. (End)
%F A059576 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
%F A059576 From _Emeric Deutsch_, Oct 12 2010: (Start)
%F A059576 Sum_{k=0..n} k*T(n,k) = A181292(n).
%F A059576 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).
%F A059576 G.f.: G(t,z) = (1-z)*(1-t*z)/(1 - 2*z - 2*t*z + 2*t*z^2). (End)
%F A059576 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]
%F A059576 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]
%F A059576 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
%F A059576 T(n, k) = 2^(n - 1)*binomial(n, k)*hypergeom([-k, k - n], [-n], 1/2) = A059474(n, k)/2 for n >= 1. - _Peter Luschny_, Nov 26 2021
%F A059576 From _G. C. Greubel_, Sep 02 2022: (Start)
%F A059576 T(n, n-k) = T(n, k).
%F A059576 T(n, 0) = T(n, n) = A011782(n).
%F A059576 T(n, n-2) = 2*A049611(n-1), n >= 2.
%F A059576 T(n, n-3) = 4*A049612(n-2), n >= 3.
%F A059576 T(n, n-4) = 8*A055589(n-3), n >= 4.
%F A059576 T(n, n-5) = 16*A055852(n-4), n >= 5.
%F A059576 T(n, n-6) = 32*A055853(n-5), n >= 6.
%F A059576 Sum_{k=0..floor(n/2)} T(n, k) = A181306(n). (End)
%e A059576 Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins
%e A059576 [0] 1;
%e A059576 [1] 1, 1;
%e A059576 [2] 2, 3, 2;
%e A059576 [3] 4, 8, 8, 4;
%e A059576 [4] 8, 20, 26, 20, 8;
%e A059576 [5] 16, 48, 76, 76, 48, 16;
%e A059576 [6] 32, 112, 208, 252, 208, 112, 32;
%e A059576 ...
%e A059576 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
%e A059576 T(5,2) = Sum_{a=0..5-2, b=0..2, (a,b) <> (5-2,2)} T(a(1,0) + b(1,1)) =
%e A059576 = (1 + 1 + 2) + (1 + 3 + 8) + (2 + 8 + 26) + (4 + 20) = 76. [Edited by _Petros Hadjicostas_, Jul 16 2020]
%e A059576 From _Petros Hadjicostas_, Jul 16 2020: (Start)
%e A059576 Square array U(n,k) (with rows n >= 0 and columns k >= 0) begins
%e A059576 1, 1, 2, 4, 8, ...
%e A059576 1, 3, 8, 20, 48, ...
%e A059576 2, 8, 26, 76, 208, ...
%e A059576 4, 20, 76, 252, 768, ...
%e A059576 8, 48, 208, 768, 2568, ...
%e A059576 16, 112, 544, 2208, 8016, ...
%e A059576 ...
%e A059576 Consider the following 2-row grid with n = 3 points at the top and k = 2 points at the bottom:
%e A059576 A B C
%e A059576 *--*--*
%e A059576 | /
%e A059576 | /
%e A059576 *--*
%e A059576 D E
%e A059576 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).
%e A059576 These are the 2-compositions of n = 3 with sum of first row entries equal to k = 1:
%e A059576 [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)
%p A059576 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;
%p A059576 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
%p A059576 T := (n, k) -> `if`(n=0, 1, 2^(n-1)*binomial(n, k)*hypergeom([-k, k - n], [-n], 1/2)): seq(seq(simplify(T(n, k)), k=0..n), n=0..10); # _Peter Luschny_, Nov 26 2021
%t A059576 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_ *)
%o A059576 (Haskell)
%o A059576 a059576 n k = a059576_tabl !! n !! k
%o A059576 a059576_row n = a059576_tabl !! n
%o A059576 a059576_tabl = [1] : map fst (iterate f ([1,1], [2,3,2])) where
%o A059576 f (us, vs) = (vs, map (* 2) ws) where
%o A059576 ws = zipWith (-) (zipWith (+) ([0] ++ vs) (vs ++ [0]))
%o A059576 ([0] ++ us ++ [0])
%o A059576 -- _Reinhard Zumkeller_, Dec 03 2012
%o A059576 (Magma)
%o A059576 A011782:= func< n | n eq 0 select 1 else 2^(n-1) >;
%o A059576 function T(n,k) // T = A059576
%o A059576 if k eq 0 or k eq n then return A011782(n);
%o A059576 else return 2*T(n-1, k-1) + 2*T(n-1, k) - (2 - 0^(n-2))*T(n-2, k-1);
%o A059576 end if; return T;
%o A059576 end function;
%o A059576 [T(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Sep 02 2022
%o A059576 (SageMath)
%o A059576 def T(n,k): # T = A059576
%o A059576 if (k==0 or k==n): return 1 if (n==0) else 2^(n-1) # A011782
%o A059576 else: return 2*T(n-1, k-1) + 2*T(n-1, k) - (2 - 0^(n-2))*T(n-2, k-1)
%o A059576 flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # _G. C. Greubel_, Sep 02 2022
%Y A059576 Cf. A000079, A001792, A003480 (row sums), A052141 (main diagonal).
%Y A059576 Cf. A059474, A059473, A008288, A035002, A059226, A059283, A181292, A336244.
%Y A059576 Cf. A011782, A049611, A049612, A055589, A055852, A055853, A181306.
%K A059576 easy,nonn,tabl,nice
%O A059576 0,4
%A A059576 _Floor van Lamoen_, Jan 23 2001