login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A038207 Triangle whose (i,j)-th entry is binomial(i,j)*2^(i-j). 95

%I #276 Apr 03 2023 18:11:57

%S 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,

%T 12,1,128,448,672,560,280,84,14,1,256,1024,1792,1792,1120,448,112,16,

%U 1,512,2304,4608,5376,4032,2016,672,144,18,1,1024,5120,11520,15360,13440,8064,3360,960,180,20,1

%N Triangle whose (i,j)-th entry is binomial(i,j)*2^(i-j).

%C This infinite matrix is the square of the Pascal matrix (A007318) whose rows are [ 1,0,... ], [ 1,1,0,... ], [ 1,2,1,0,... ], ...

%C As an upper right triangle, table rows give number of points, edges, faces, cubes,

%C 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 j-dimensional subspaces of an i-dimensional hypercube (see the Coxeter reference). - _Christof Weber_, May 08 2009

%C 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

%C Row sums are powers of 3 (A000244), antidiagonal sums are Pell numbers (A000129). - _Gerald McGarvey_, May 17 2005

%C Riordan array (1/(1-2x), x/(1-2x)). - _Paul Barry_, Jul 28 2005

%C T(n,k) is the number of elements of the Coxeter group B_n with descent set contained in {s_k}, 0<=k<=n-1. 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

%C 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

%C 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

%C 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

%C T(i,j) is the number of i-permutations 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

%C Triangle of coefficients in expansion of (2+x)^n. - _N-E. Fahssi_, Apr 13 2008

%C Sum of diagonals are Jacobsthal-numbers: A001045. - _Mark Dols_, Aug 31 2009

%C 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

%C Eigensequence of the triangle = A004211: (1, 3, 11, 49, 257, 1539, ...). - _Gary W. Adamson_, Feb 07 2010

%C f-vectors ("face"-vectors) for n-dimensional cubes [see e.g., Hoare]. (This is a restatement of Bottomley's above.) - _Tom Copeland_, Oct 19 2012

%C 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 Fokker-Planck equation as given in the Dattoli et al. ref. below. - _Tom Copeland_, Oct 26 2012

%C The matrix elements of the inverse are T^(-1)(n,k) = (-1)^(n+k)*T(n,k). - _R. J. Mathar_, Mar 12 2013

%C Unsigned diagonals of A133156 are rows of this array. - _Tom Copeland_, Oct 11 2014

%C Omitting the first row, this is the production matrix for A039683, where an equivalent differential operator can be found. - _Tom Copeland_, Oct 11 2016

%C 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^(n-k) ways to map the other (n-k) 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

%C 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

%C T(n,k) is the number of 2-compositions of n+1 with some zeros allowed that have k zeros; see the Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 16 2020

%C Also the convolution triangle of A000079. - _Peter Luschny_, Oct 09 2022

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 155.

%D H. S. M. Coxeter, Regular Polytopes, Dover Publications, New York (1973), p. 122.

%H T. D. Noe, <a href="/A038207/b038207.txt">Rows n=0..100 of triangle, flattened</a>

%H Peter Bala, <a href="/A081577/a081577.pdf">A note on the diagonals of a proper Riordan Array</a>

%H Paul Barry, <a href="https://arxiv.org/abs/1805.02274">On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays</a>, arXiv:1805.02274 [math.CO], 2018.

%H Jhon J. Bravo, Jose L. Herrera, and José L. Ramírez, <a href="https://www.emis.de/journals/JIS/VOL23/Bravo/bravo4.html">Combinatorial Interpretation of Generalized Pell Numbers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.2.1.

%H John Cartan, <a href="http://www.cartania.com/starmaze/triangle.html">Starmaze: Cartan's Triangle</a>.

%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2012/11/29/infinigens-the-pascal-pyramid-and-the-witt-and-virasoro-algebras/">Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras</a>.

%H B. N. Cyvin, J. Brunvoll, and S. J. Cyvin, <a href="http://match.pmf.kg.ac.rs/electronic_versions/Match34/match34_109-121.pdf">Isomer enumeration of unbranched catacondensed polygonal systems with pentagons and heptagons</a>, Match, No. 34 (Oct 1996), 109-121.

%H S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, <a href="https://hrcak.srce.hr/177109">Unbranched catacondensed polygonal systems containing hexagons and tetragons</a>, Croatica Chem. Acta, 69 (1996), 757-774.

%H S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, <a href="https://dx.doi.org/10.1016/0022-2860(95)09039-8">Isomer enumeration of some polygonal systems representing polycyclic conjugated hydrocarbons</a>, Journal of Molecular Structure 376 (1996), 495-505.

%H G. Dattoli, A. Mancho, M. Quattromini and A. Torre, <a href="http://dx.doi.org/10.1016/S0969-806X(00)00426-6">Exponential operators, generalized polynomials and evolution problems</a>, Radiation Physics and Chemistry 61 (2001), 99-108. [From _Tom Copeland_, Oct 25 2012]

%H Filippo Disanto, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Disanto/disanto5.html">Some Statistics on the Hypercubes of Catalan Permutations</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2.

%H Shishuo Fu and Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.

%H W. G. Harter, <a href="http://dx.doi.org/10.1063/1.1666574">Representations of multidimensional symmetries in networks</a>, J. Math. Phys., 15 (1974), 2016-2021.

%H Russell Jay Hendel, <a href="https://arxiv.org/abs/2107.03549">A Method for Uniformly Proving a Family of Identities</a>, arXiv:2107.03549 [math.CO], 2021.

%H Graham Hoare, <a href="http://www.jstor.org/stable/3618141">Hypercubes and Chebyshev</a>, Math. Gaz. 74 (470) (1990), 375-377.

%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.

%H Milan Janjić, <a href="https://arxiv.org/abs/1905.04465">On Restricted Ternary Words and Insets</a>, arXiv:1905.04465 [math.CO], 2019.

%H Marin Knežević, Vedran Krčadinac, and Lucija Relić, <a href="https://arxiv.org/abs/2012.15307">Matrix products of binomial coefficients and unsigned Stirling numbers</a>, arXiv:2012.15307 [math.CO], 2020.

%H Katarzyna Kril and Wojciech Mlotkowski, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p27">Permutations of Type B with Fixed Number of Descents and Minus Signs</a>, The Electronic Journal of Combinatorics, Vol. 26(1) (2019), Article P1.27.

%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

%H Thomas Selig and Haoyue Zhu, <a href="https://arxiv.org/abs/2303.15756">Complete non-ambiguous trees and associated permutations: connections through the Abelian sandpile model</a>, arXiv:2303.15756 [math.CO], 2023, see p. 27.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hypercube">Hypercube</a>.

%F T(n, k) = Sum_{i=0..n} binomial(n,i)*binomial(i,k).

%F T(n, k) = (-1)^k*A065109(n,k).

%F G.f.: 1/(1-2*z-t*z). - _Emeric Deutsch_, Nov 04 2007

%F Rows of the triangle are generated by taking successive iterates of (A135387)^n * [1, 0, 0, 0, ...]. - _Gary W. Adamson_, Dec 09 2007

%F 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

%F Sum_{k=0..n} T(n,k)*x^k = (2+x)^n. - _Philippe Deléham_, Dec 15 2009

%F n-th row is obtained by taking pairwise sums of triangle A112857 terms starting from the right. - _Gary W. Adamson_, Feb 06 2012

%F T(n,n) = 1 and T(n,k) = T(n-1,k-1) + 2*T(n-1,k) for k<n. - _Jon Perry_, Oct 11 2012

%F The e.g.f. for the n-th 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

%F From _Tom Copeland_, Oct 26 2012: (Start)

%F From the formalism of A132440 and A218272:

%F Let P and P^T be the Pascal matrix and its transpose and H= P^2= A038207.

%F Then with D the derivative operator,

%F exp(x*z/(1-2*z))/(1-2*z)= exp(2*z D_z z) e^(x*z)= exp(2*D_x (x D_x)) e^(z*x)

%F = (1 z z^2 z^3 ...) H (1 x x^2/2! x^3/3! ...)^T

%F = (1 x x^2/2! x^3/3! ...) H^T (1 z z^2 z^3 ...)^T

%F = Sum_{n>=0} z^n * 2^n Lag_n(-x/2)= exp[z*EF(.,x)], an o.g.f. for the f-vectors (rows) of A038207 where EF(n,x) is an e.g.f. for the n-th f-vector. (Lag_n(x) are the un-normalized Laguerre polynomials.)

%F Conversely,

%F exp(z*(2+x))= exp(2D_x) exp(x*z)= exp(2x) exp(x*z)

%F = (1 x x^2 x^3 ...) H^T (1 z z^2/2! z^3/3! ...)^T

%F = (1 z z^2/2! z^3/3! ...) H (1 x x^2 x^3 ...)^T

%F = exp(z*OF(.,x)), an e.g.f for the f-vectors of A038207 where

%F OF(n,x)= (2+x)^n is an o.g.f. for the n-th f-vector.

%F (End)

%F 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

%F A038207 = exp[M*B(.,2)] where M = A238385-I and (B(.,x))^n = B(n,x) are the Bell polynomials (cf. A008277). B(n,2) = A001861(n). - _Tom Copeland_, Apr 17 2014

%F T = (A007318)^2 = A112857*|A167374| = |A118801|*|A167374| = |A118801*A167374| = |P*A167374*P^(-1)*A167374| = |P*NpdP*A167374|. Cf. A118801. - _Tom Copeland_, Nov 17 2016

%F E.g.f. for the n-th 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

%F 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

%F From _Robert A. Russell_, Aug 05 2020: (Start)

%F G.f. for column k: x^k / (1-2*x)^(k+1).

%F E.g.f. for column k: exp(2*x) * x^k / k!. (End)

%F 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

%e Triangle begins with T(0,0):

%e 1;

%e 2, 1;

%e 4, 4, 1;

%e 8, 12, 6, 1;

%e 16, 32, 24, 8, 1;

%e 32, 80, 80, 40, 10, 1;

%e ... - corrected by _Clark Kimberling_, Aug 05 2011

%e Seen as an array read by descending antidiagonals:

%e [0] 1, 2, 4, 8, 16, 32, 64, 128, 256, ... [A000079]

%e [1] 1, 4, 12, 32, 80, 192, 448, 1024, 2304, ... [A001787]

%e [2] 1, 6, 24, 80, 240, 672, 1792, 4608, 11520, ... [A001788]

%e [3] 1, 8, 40, 160, 560, 1792, 5376, 15360, 42240, ... [A001789]

%e [4] 1, 10, 60, 280, 1120, 4032, 13440, 42240, 126720, ... [A003472]

%e [5] 1, 12, 84, 448, 2016, 8064, 29568, 101376, 329472, ... [A054849]

%e [6] 1, 14, 112, 672, 3360, 14784, 59136, 219648, 768768, ... [A002409]

%e [7] 1, 16, 144, 960, 5280, 25344, 109824, 439296, 1647360, ... [A054851]

%e [8] 1, 18, 180, 1320, 7920, 41184, 192192, 823680, 3294720, ... [A140325]

%e [9] 1, 20, 220, 1760, 11440, 64064, 320320, 1464320, 6223360, ... [A140354]

%p for i from 0 to 12 do seq(binomial(i, j)*2^(i-j), j = 0 .. i) end do; # yields sequence in triangular form - _Emeric Deutsch_, Nov 04 2007

%p # Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.

%p PMatrix(10, n -> 2^(n-1)); # _Peter Luschny_, Oct 09 2022

%t Table[CoefficientList[Expand[(y + x + x^2)^n], y] /. x -> 1, {n, 0,10}] // TableForm (* _Geoffrey Critzer_, Nov 20 2011 *)

%t Table[Binomial[n,k]2^(n-k),{n,0,10},{k,0,n}]//Flatten (* _Harvey P. Dale_, May 22 2020 *)

%o (PARI) {T(n, k) = polcoeff((x+2)^n, k)}; /* _Michael Somos_, Apr 27 2000 */

%o (Haskell)

%o a038207 n = a038207_list !! n

%o a038207_list = concat $ iterate ([2,1] *) [1]

%o instance Num a => Num [a] where

%o fromInteger k = [fromInteger k]

%o (p:ps) + (q:qs) = p + q : ps + qs

%o ps + qs = ps ++ qs

%o (p:ps) * qs'@(q:qs) = p * q : ps * qs' + [p] * qs

%o _ * _ = []

%o -- _Reinhard Zumkeller_, Apr 02 2011

%o (Haskell)

%o a038207' n k = a038207_tabl !! n !! k

%o a038207_row n = a038207_tabl !! n

%o a038207_tabl = iterate f [1] where

%o f row = zipWith (+) ([0] ++ row) (map (* 2) row ++ [0])

%o -- _Reinhard Zumkeller_, Feb 27 2013

%o (Sage)

%o def A038207_triangle(dim):

%o M = matrix(ZZ,dim,dim)

%o for n in range(dim): M[n,n] = 1

%o for n in (1..dim-1):

%o for k in (0..n-1):

%o M[n,k] = M[n-1,k-1]+2*M[n-1,k]

%o return M

%o A038207_triangle(9) # _Peter Luschny_, Sep 20 2012

%o (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

%o (GAP) Flat(List([0..15], n->List([0..n], k->Binomial(n, k)*2^(n-k)))); # _Stefano Spezia_, Nov 21 2018

%Y See A065109 for a signed version.

%Y Columns 0-10 are A000079, A001787, A001788(n-1), A001789, A003472, A054849, A002409(n-6), A054851, A140325(n-8), A140354(n-9), A172242.

%Y T(2n,n) gives A059304.

%Y Cf. A007318, A013609, A013610, A062715, A099089, A004211, A135387.

%Y Cf. A001861, A008277, A027465, A027466, A038231, A038243, A038255, A039683, A112857, A118801, A132440, A133156, A133314, A167374, A218272, A238385, A323939.

%K nonn,tabl,easy,nice

%O 0,2

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 04:13 EDT 2024. Contains 371235 sequences. (Running on oeis4.)