

A038207


Triangle whose (i,j)th entry is binomial(i,j)*2^(ij).


95



1, 2, 1, 4, 4, 1, 8, 12, 6, 1, 16, 32, 24, 8, 1, 32, 80, 80, 40, 10, 1, 64, 192, 240, 160, 60, 12, 1, 128, 448, 672, 560, 280, 84, 14, 1, 256, 1024, 1792, 1792, 1120, 448, 112, 16, 1, 512, 2304, 4608, 5376, 4032, 2016, 672, 144, 18, 1, 1024, 5120, 11520, 15360, 13440, 8064, 3360, 960, 180, 20, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

This infinite matrix is the square of the Pascal matrix (A007318) whose rows are [ 1,0,... ], [ 1,1,0,... ], [ 1,2,1,0,... ], ...
As an upper right triangle, table rows give number of points, edges, faces, cubes,
4D hypercubes etc. in hypercubes of increasing dimension by column.  Henry Bottomley, Apr 14 2000. More precisely, the (i,j)th entry is the number of jdimensional subspaces of an idimensional hypercube (see the Coxeter reference).  Christof Weber, May 08 2009
Number of different partial sums of 1+[1,1,2]+[2,2,3]+[3,3,4]+[4,4,5]+... with entries that are zero removed.  Jon Perry, Jan 01 2004
Riordan array (1/(12x), x/(12x)).  Paul Barry, Jul 28 2005
T(n,k) is the number of elements of the Coxeter group B_n with descent set contained in {s_k}, 0<=k<=n1. For T(n,n), we interpret this as the number of elements of B_n with empty descent set (since s_n does not exist).  Elizabeth Morris (epmorris(AT)math.washington.edu), Mar 01 2006
Let S be a binary relation on the power set P(A) of a set A having n = A elements such that for every element x, y of P(A), xSy if x is a subset of y. Then T(n,k) = the number of elements (x,y) of S for which y has exactly k more elements than x.  Ross La Haye, Oct 12 2007
T(n,k) is number of paths in the first quadrant going from (0,0) to (n,k) using only steps B=(1,0) colored blue, R=(1,0) colored red and U=(1,1). Example: T(3,2)=6 because we have BUU, RUU, UBU, URU, UUB and UUR.  Emeric Deutsch, Nov 04 2007
T(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (0,1), and two kinds of step (1,0).  Joerg Arndt, Jul 01 2011
T(i,j) is the number of ipermutations of {1,2,3} containing j 1's. Example: T(2,1)=4 because we have 12, 13, 21 and 31; T(3,2)=6 because we have 112, 113, 121, 131, 211 and 311.  Zerinvary Lajos, Dec 21 2007
Triangle of coefficients in expansion of (2+x)^n.  NE. Fahssi, Apr 13 2008
Triangle T(n,k), read by rows, given by [2,0,0,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938.  Philippe Deléham, Dec 15 2009
fvectors ("face"vectors) for ndimensional cubes [see e.g., Hoare]. (This is a restatement of Bottomley's above.)  Tom Copeland, Oct 19 2012
With P = Pascal matrix, the sequence of matrices I, A007318, A038207, A027465, A038231, A038243, A038255, A027466 ... = P^0, P^1, P^2, ... are related by Copeland's formula below to the evolution at integral time steps n= 0, 1, 2, ... of an exponential distribution exp(x*z) governed by the FokkerPlanck equation as given in the Dattoli et al. ref. below.  Tom Copeland, Oct 26 2012
The matrix elements of the inverse are T^(1)(n,k) = (1)^(n+k)*T(n,k).  R. J. Mathar, Mar 12 2013
Omitting the first row, this is the production matrix for A039683, where an equivalent differential operator can be found.  Tom Copeland, Oct 11 2016
T(n,k) is the number of functions f:[n]>[3] with exactly k elements mapped to 3. Note that there are C(n,k) ways to choose the k elements mapped to 3, and there are 2^(nk) ways to map the other (nk) elements to {1,2}. Hence, by summing T(n,k) as k runs from 0 to n, we obtain 3^n = Sum_{k=0..n} T(n,k).  Dennis P. Walsh, Sep 26 2017
Since this array is the square of the Pascal lower triangular matrix, the row polynomials of this array are obtained as the umbral composition of the row polynomials P_n(x) of the Pascal matrix with themselves. E.g., P_3(P.(x)) = 1 P_3(x) + 3 P_2(x) + 3 P_1(x) + 1 = (x^3 + 3 x^2 + 3 x + 1) + 3 (x^2 + 2 x + 1) + 3 (x + 1) + 1 = x^3 + 6 x^2 + 12 x + 8.  Tom Copeland, Nov 12 2018
T(n,k) is the number of 2compositions of n+1 with some zeros allowed that have k zeros; see the Hopkins & Ouvry reference.  Brian Hopkins, Aug 16 2020


REFERENCES

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 155.
H. S. M. Coxeter, Regular Polytopes, Dover Publications, New York (1973), p. 122.


LINKS



FORMULA

T(n, k) = Sum_{i=0..n} binomial(n,i)*binomial(i,k).
Rows of the triangle are generated by taking successive iterates of (A135387)^n * [1, 0, 0, 0, ...].  Gary W. Adamson, Dec 09 2007
From the formalism of A133314, the e.g.f. for the row polynomials of A038207 is exp(x*t)*exp(2x). The e.g.f. for the row polynomials of the inverse matrix is exp(x*t)*exp(2x). p iterates of the matrix give the matrix with e.g.f. exp(x*t)*exp(p*2x). The results generalize for 2 replaced by any number.  Tom Copeland, Aug 18 2008
nth row is obtained by taking pairwise sums of triangle A112857 terms starting from the right.  Gary W. Adamson, Feb 06 2012
T(n,n) = 1 and T(n,k) = T(n1,k1) + 2*T(n1,k) for k<n.  Jon Perry, Oct 11 2012
The e.g.f. for the nth row is given by umbral composition of the normalized Laguerre polynomials A021009 as p(n,x) = L(n, L(.,x))/n! = 2^n L(n, x/2)/n!. E.g., L(2,x) = 2 4*x +x^2, so p(2,x)= (1/2)*L(2, L(.,x)) = (1/2)*(2*L(0,x) + 4*L(1,x) + L(2,x)) = (1/2)*(2 + 4*(1+x) + (2+4*x+x^2)) = 4 + 4*x + x^2/2.  Tom Copeland, Oct 20 2012
Let P and P^T be the Pascal matrix and its transpose and H= P^2= A038207.
Then with D the derivative operator,
exp(x*z/(12*z))/(12*z)= exp(2*z D_z z) e^(x*z)= exp(2*D_x (x D_x)) e^(z*x)
= (1 z z^2 z^3 ...) H (1 x x^2/2! x^3/3! ...)^T
= (1 x x^2/2! x^3/3! ...) H^T (1 z z^2 z^3 ...)^T
= Sum_{n>=0} z^n * 2^n Lag_n(x/2)= exp[z*EF(.,x)], an o.g.f. for the fvectors (rows) of A038207 where EF(n,x) is an e.g.f. for the nth fvector. (Lag_n(x) are the unnormalized Laguerre polynomials.)
Conversely,
exp(z*(2+x))= exp(2D_x) exp(x*z)= exp(2x) exp(x*z)
= (1 x x^2 x^3 ...) H^T (1 z z^2/2! z^3/3! ...)^T
= (1 z z^2/2! z^3/3! ...) H (1 x x^2 x^3 ...)^T
= exp(z*OF(.,x)), an e.g.f for the fvectors of A038207 where
OF(n,x)= (2+x)^n is an o.g.f. for the nth fvector.
(End)
G.f.: R(0)/2, where R(k) = 1 + 1/(1  (2*k+1+ (1+y))*x/((2*k+2+ (1+y))*x + 1/R(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Nov 09 2013
E.g.f. for the nth subdiagonal, n = 0,1,2,..., equals exp(x)*P(n,x), where P(n,x) is the polynomial 2^n*Sum_{k = 0..n} binomial(n,k)*x^k/k!. For example, the e.g.f. for the third subdiagonal is exp(x)*(8 + 24*x + 12*x^2 + 4*x^3/3) = 8 + 32*x + 80*x^2/2! + 160*x^3/3! + ....  Peter Bala, Mar 05 2017
T(3*k+2,k) = T(3*k+2,k+1), T(2*k+1,k) = 2*T(2*k+1,k+1).  Yuchun Ji, May 26 2020
G.f. for column k: x^k / (12*x)^(k+1).
E.g.f. for column k: exp(2*x) * x^k / k!. (End)
Also the array A(n, k) read by descending antidiagonals, where A(n, k) = (1)^n*Sum_{j= 0..n+k} binomial(n + k, j)*hypergeom([n, j+1], [1], 1).  Peter Luschny, Nov 09 2021


EXAMPLE

Triangle begins with T(0,0):
1;
2, 1;
4, 4, 1;
8, 12, 6, 1;
16, 32, 24, 8, 1;
32, 80, 80, 40, 10, 1;
Seen as an array read by descending antidiagonals:
[0] 1, 2, 4, 8, 16, 32, 64, 128, 256, ... [A000079]
[1] 1, 4, 12, 32, 80, 192, 448, 1024, 2304, ... [A001787]
[2] 1, 6, 24, 80, 240, 672, 1792, 4608, 11520, ... [A001788]
[3] 1, 8, 40, 160, 560, 1792, 5376, 15360, 42240, ... [A001789]
[4] 1, 10, 60, 280, 1120, 4032, 13440, 42240, 126720, ... [A003472]
[5] 1, 12, 84, 448, 2016, 8064, 29568, 101376, 329472, ... [A054849]
[6] 1, 14, 112, 672, 3360, 14784, 59136, 219648, 768768, ... [A002409]
[7] 1, 16, 144, 960, 5280, 25344, 109824, 439296, 1647360, ... [A054851]
[8] 1, 18, 180, 1320, 7920, 41184, 192192, 823680, 3294720, ... [A140325]
[9] 1, 20, 220, 1760, 11440, 64064, 320320, 1464320, 6223360, ... [A140354]


MAPLE

for i from 0 to 12 do seq(binomial(i, j)*2^(ij), j = 0 .. i) end do; # yields sequence in triangular form  Emeric Deutsch, Nov 04 2007
# Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.


MATHEMATICA

Table[CoefficientList[Expand[(y + x + x^2)^n], y] /. x > 1, {n, 0, 10}] // TableForm (* Geoffrey Critzer, Nov 20 2011 *)
Table[Binomial[n, k]2^(nk), {n, 0, 10}, {k, 0, n}]//Flatten (* Harvey P. Dale, May 22 2020 *)


PROG

(PARI) {T(n, k) = polcoeff((x+2)^n, k)}; /* Michael Somos, Apr 27 2000 */
(Haskell)
a038207 n = a038207_list !! n
a038207_list = concat $ iterate ([2, 1] *) [1]
instance Num a => Num [a] where
fromInteger k = [fromInteger k]
(p:ps) + (q:qs) = p + q : ps + qs
ps + qs = ps ++ qs
(p:ps) * qs'@(q:qs) = p * q : ps * qs' + [p] * qs
_ * _ = []
(Haskell)
a038207' n k = a038207_tabl !! n !! k
a038207_row n = a038207_tabl !! n
a038207_tabl = iterate f [1] where
f row = zipWith (+) ([0] ++ row) (map (* 2) row ++ [0])
(Sage)
M = matrix(ZZ, dim, dim)
for n in range(dim): M[n, n] = 1
for n in (1..dim1):
for k in (0..n1):
M[n, k] = M[n1, k1]+2*M[n1, k]
return M
(Magma) /* As triangle */ [[(&+[Binomial(n, i)*Binomial(i, k): i in [k..n]]): k in [0..n]]: n in [0..15]]; // Vincenzo Librandi, Nov 16 2018
(GAP) Flat(List([0..15], n>List([0..n], k>Binomial(n, k)*2^(nk)))); # Stefano Spezia, Nov 21 2018


CROSSREFS

Columns 010 are A000079, A001787, A001788(n1), A001789, A003472, A054849, A002409(n6), A054851, A140325(n8), A140354(n9), A172242.
Cf. A001861, A008277, A027465, A027466, A038231, A038243, A038255, A039683, A112857, A118801, A132440, A133156, A133314, A167374, A218272, A238385, A323939.


KEYWORD



AUTHOR



STATUS

approved



