|
%I #100 Sep 02 2022 13:39:00
%S 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 208,112,32,64,256,544,768,768,544,256,64,128,576,1376,2208,2568,2208,
%U 1376,576,128,256,1280,3392,6080,8016,8016,6080,3392,1280,256
%N 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 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 From _Petros Hadjicostas_, Jul 16 2020: (Start)
%C We explain the parallelogram definition of T(n,k).
%C T(0,0) *
%C |\
%C | \
%C | * T(k,k)
%C T(n-k,0) * |
%C \ |
%C \|
%C * T(n,k)
%C 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 {(i,j): a(1,0) + b(1,1), 0 <= a <= n-k, 0 <= b <= k} - {(n,k)}.
%C The parallelogram can sometimes be degenerate; e.g., when k = 0 or n = k. (End)
%C 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 From _Michel Marcus_ and _Petros Hadjicostas_, Jul 16 2020: (Start)
%C 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 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 They also proved that, for (m,n) <> (1,1), A(m,n) = (2^(m-2)/(n-1)!) * Q_n(m) =
%C = (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 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
%D Fang, E., Jenkins, J., Lee, Z., Li, D., Lu, E., Miller, S. J., ... & Siktar, J. (2019). Central Limit Theorems for Compound Paths on the 2-Dimensional Lattice. arXiv preprint arXiv:1906.10645. Also Fib. Q., 58:1 (2020), 208-225.
%H Reinhard Zumkeller, <a href="/A059576/b059576.txt">Rows n = 0..120 of triangle, flattened</a>
%H 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 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 <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>
%F T(n, n-1) = A001792(n-1).
%F T(2*n, n) = A052141(n).
%F Sum_{k=0..n} T(n, k) = A003480(n).
%F 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 Maple code gives another explicit formula for U(n, k).
%F From Jon Stadler (jstadler(AT)capital.edu), Apr 30 2003: (Start)
%F 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 2*U(n,k) = Sum_{i <= n, j <= k} U(i,j).
%F U(n,k) = 2*U(n-1,k) + Sum_{i < k} U(n,i).
%F U(n,k) = Sum_{j=0..n+k} C(n,j-k+1)*C(k,j-n+1)*2^j. (End)
%F 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 From _Emeric Deutsch_, Oct 12 2010: (Start)
%F Sum_{k=0..n} k*T(n,k) = A181292(n).
%F 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 G.f.: G(t,z) = (1-z)*(1-t*z)/(1 - 2*z - 2*t*z + 2*t*z^2). (End)
%F 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 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 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 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 From _G. C. Greubel_, Sep 02 2022: (Start)
%F T(n, n-k) = T(n, k).
%F T(n, 0) = T(n, n) = A011782(n).
%F T(n, n-2) = 2*A049611(n-1), n >= 2.
%F T(n, n-3) = 4*A049612(n-2), n >= 3.
%F T(n, n-4) = 8*A055589(n-3), n >= 4.
%F T(n, n-5) = 16*A055852(n-4), n >= 5.
%F T(n, n-6) = 32*A055853(n-5), n >= 6.
%F Sum_{k=0..floor(n/2)} T(n, k) = A181306(n). (End)
%e Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins
%e [0] 1;
%e [1] 1, 1;
%e [2] 2, 3, 2;
%e [3] 4, 8, 8, 4;
%e [4] 8, 20, 26, 20, 8;
%e [5] 16, 48, 76, 76, 48, 16;
%e [6] 32, 112, 208, 252, 208, 112, 32;
%e ...
%e 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 T(5,2) = Sum_{a=0..5-2, b=0..2, (a,b) <> (5-2,2)} T(a(1,0) + b(1,1)) =
%e = (1 + 1 + 2) + (1 + 3 + 8) + (2 + 8 + 26) + (4 + 20) = 76. [Edited by _Petros Hadjicostas_, Jul 16 2020]
%e From _Petros Hadjicostas_, Jul 16 2020: (Start)
%e Square array U(n,k) (with rows n >= 0 and columns k >= 0) begins
%e 1, 1, 2, 4, 8, ...
%e 1, 3, 8, 20, 48, ...
%e 2, 8, 26, 76, 208, ...
%e 4, 20, 76, 252, 768, ...
%e 8, 48, 208, 768, 2568, ...
%e 16, 112, 544, 2208, 8016, ...
%e ...
%e Consider the following 2-row grid with n = 3 points at the top and k = 2 points at the bottom:
%e A B C
%e *--*--*
%e | /
%e | /
%e *--*
%e D E
%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).
%e These are the 2-compositions of n = 3 with sum of first row entries equal to k = 1:
%e [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 := 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 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 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 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 (Haskell)
%o a059576 n k = a059576_tabl !! n !! k
%o a059576_row n = a059576_tabl !! n
%o a059576_tabl = [1] : map fst (iterate f ([1,1], [2,3,2])) where
%o f (us, vs) = (vs, map (* 2) ws) where
%o ws = zipWith (-) (zipWith (+) ([0] ++ vs) (vs ++ [0]))
%o ([0] ++ us ++ [0])
%o -- _Reinhard Zumkeller_, Dec 03 2012
%o (Magma)
%o A011782:= func< n | n eq 0 select 1 else 2^(n-1) >;
%o function T(n,k) // T = A059576
%o if k eq 0 or k eq n then return A011782(n);
%o else return 2*T(n-1, k-1) + 2*T(n-1, k) - (2 - 0^(n-2))*T(n-2, k-1);
%o end if; return T;
%o end function;
%o [T(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Sep 02 2022
%o (SageMath)
%o def T(n,k): # T = A059576
%o if (k==0 or k==n): return 1 if (n==0) else 2^(n-1) # A011782
%o else: return 2*T(n-1, k-1) + 2*T(n-1, k) - (2 - 0^(n-2))*T(n-2, k-1)
%o flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # _G. C. Greubel_, Sep 02 2022
%Y Cf. A000079, A001792, A003480 (row sums), A052141 (main diagonal).
%Y Cf. A059474, A059473, A008288, A035002, A059226, A059283, A181292, A336244.
%Y Cf. A011782, A049611, A049612, A055589, A055852, A055853, A181306.
%K easy,nonn,tabl,nice
%O 0,4
%A _Floor van Lamoen_, Jan 23 2001
|
