login
Triangle of coefficients in expansion of (1+2*x)^n.
57

%I #158 Nov 01 2024 23:53:05

%S 1,1,2,1,4,4,1,6,12,8,1,8,24,32,16,1,10,40,80,80,32,1,12,60,160,240,

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

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

%N Triangle of coefficients in expansion of (1+2*x)^n.

%C T(n,k) is the number of lattice paths from (0,0) to (n,k) with steps (1,0) and two kinds of steps (1,1). The number of paths with steps (1,0) and s kinds of steps (1,1) corresponds to the expansion of (1+s*x)^n. - _Joerg Arndt_, Jul 01 2011

%C Also sum of rows in A046816. - _Lior Manor_, Apr 24 2004

%C Also square array of unsigned coefficients of Chebyshev polynomials of second kind. - _Philippe Deléham_, Aug 12 2005

%C The rows give the number of k-simplices in the n-cube. For example, 1, 6, 12, 8 shows that the 3-cube has 1 volume, 6 faces, 12 edges and 8 vertices. - _Joshua Zucker_, Jun 05 2006

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

%C With offset [1,1] the triangle with doubled numbers, 2*a(n,m), enumerates sequences of length m with nonzero integer entries n_i satisfying sum(|n_i|) <= n. Example n=4, m=2: [1,3], [3,1], [2,2] each in 2^2=4 signed versions: 2*a(4,2) = 2*6 = 12. The Sum over m (row sums of 2*a(n,m)) gives 2*3^(n-1), n >= 1. See the W. Lang comment and a K. A. Meissner reference under A024023. - _Wolfdieter Lang_, Jan 21 2008

%C n-th row of the triangle = leftmost column of nonzero terms of X^n, where X = an infinite bidiagonal matrix with (1,1,1,...) in the main diagonal and (2,2,2,...) in the subdiagonal. - _Gary W. Adamson_, Jul 19 2008

%C Numerators of a matrix square-root of Pascal's triangle A007318, where the denominators for the n-th row are set to 2^n. - _Gerald McGarvey_, Aug 20 2009

%C From _Johannes W. Meijer_, Sep 22 2010: (Start)

%C The triangle sums (see A180662 for their definitions) link the Pell-Jacobsthal triangle, whose mirror image is A038207, with twenty-four different sequences; see the crossrefs.

%C This triangle may very well be called the Pell-Jacobsthal triangle in view of the fact that A000129 (Kn21) are the Pell numbers and A001045 (Kn11) the Jacobsthal numbers.

%C (End)

%C T(n,k) equals the number of n-length words on {0,1,2} having n-k zeros. - _Milan Janjic_, Jul 24 2015

%C T(n-1,k-1) is the number of 2-compositions of n with zeros having k positive parts; see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 16 2020

%C T(n,k) is the number of chains 0=x_0<x_1<...<x_k=1 in the butterfly poset of rank n. Cf. Ehrenborg and Readdy link. - _Geoffrey Critzer_, Oct 01 2022

%C Excluding the initial 1, T(n,k) is the number of k-faces of a regular n-cross polytope. See A038207 for n-cube and A135278 for n-simplex. - _Mohammed Yaseen_, Jan 14 2023

%D B. N. Cyvin et al., Isomer enumeration of unbranched catacondensed polygonal systems with pentagons and heptagons, Match, No. 34 (Oct 1996), pp. 109-121.

%D G. Hotz, Zur Reduktion von Schaltkreispolynomen im Hinblick auf eine Verwendung in Rechenautomaten, El. Datenverarbeitung, Folge 5 (1960), pp. 21-27.

%H T. D. Noe, <a href="/A013609/b013609.txt">Rows n=0..50 of triangle, flattened</a>

%H Feryal Alayont and Evan Henning, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Alayont/ala4.html">Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.

%H H. J. Brothers, Pascal's Prism: Supplementary Material, <a href="http://www.brotherstechnology.com/docs/Pascal%27s_Prism_%28supplement%29.pdf">PDF version</a>.

%H John Cartan, <a href="http://www.cartania.com/starmaze/glossary.html#cartan">Cartan's triangle</a> shows the relationship to the n-cube.

%H R. Ehrenborg and M. Readdy, <a href="http://www.http://www.ms.uky.edu/~jrge/Papers/Eulerian_binomial_old_old.pdf">Characterization of the factorial functions of Eulerian binomial and Sheffer posets</a>

%H J. Goldman and J. Haglund, <a href="http://dx.doi.org/10.1006/jcta.2000.3113">Generalized rook polynomials</a>, J. Combin. Theory A91 (2000), 509-530, 1-rook coefficients of k rooks on the 2xn board, all heights 2.

%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 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 D. A. Zaitsev, <a href="https://doi.org/10.1016/j.tcs.2016.11.002">A generalized neighborhood for cellular automata</a>, Theoretical Computer Science, 666 (2017), 21-35.

%F G.f.: 1 / (1 - x*(1+2*y)).

%F T(n,k) = 2^k*binomial(n,k).

%F T(n,k) = 2*T(n-1,k-1) + T(n-1,k). - _Jon Perry_, Nov 22 2005

%F Row sums are 3^n = A000244(n). - _Joerg Arndt_, Jul 01 2011

%F T(n,k) = Sum_{i=n-k..n} C(i,n-k)*C(n,i). - _Mircea Merca_, Apr 28 2012

%F E.g.f.: exp(2*y*x + x). - _Geoffrey Critzer_, Nov 12 2012

%F Riordan array (x/(1 - x), 2*x/(1 - x)). Exp(2*x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(2*x)*(1 + 6*x + 12*x^2/2! + 8*x^3/3!) = 1 + 8*x + 40*x^2/2! + 160*x^3/3! + 560*x^4/4! + .... The same property holds more generally for Riordan arrays of the form (f(x), 2*x/(1 - x)). - _Peter Bala_, Dec 21 2014

%F T(n,k) = Sum_{j=0..k} (-1)^(k-j) * binomial(n,k) * binomial(k,j) * 3^j. - _Kolosov Petro_, Jan 28 2019

%F T(n,k) = 2*(n+1-k)*T(n,k-1)/k, T(n,0) = 1. - _Alexander R. Povolotsky_, Oct 08 2023

%F For n >= 1, GCD(T(n,1), ..., T(n,n)) = GCD(T(n,1),T(n,n)) = GCD(2*n,2^n) = A171977(n). - _Pontus von Brömssen_, Nov 01 2024

%e Triangle begins:

%e 1;

%e 1, 2;

%e 1, 4, 4;

%e 1, 6, 12, 8;

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

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

%e 1, 12, 60, 160, 240, 192, 64;

%e 1, 14, 84, 280, 560, 672, 448, 128;

%e 1, 16, 112, 448, 1120, 1792, 1792, 1024, 256;

%e 1, 18, 144, 672, 2016, 4032, 5376, 4608, 2304, 512;

%e 1, 20, 180, 960, 3360, 8064, 13440, 15360, 11520, 5120, 1024;

%e 1, 22, 220, 1320, 5280, 14784, 29568, 42240, 42240, 28160, 11264, 2048;

%e 1, 24, 264, 1760, 7920, 25344, 59136, 101376, 126720, 112640, 67584, 24576, 4096;

%e From _Peter Bala_, Apr 20 2012: (Start)

%e The triangle can be written as the matrix product A038207*(signed version of A013609).

%e |.1................||.1..................|

%e |.2...1............||-1...2..............|

%e |.4...4...1........||.1..-4...4..........|

%e |.8..12...6...1....||-1...6...-12...8....|

%e |16..32..24...8...1||.1..-8....24.-32..16|

%e |..................||....................|

%e (End)

%p bin2:=proc(n,k) option remember; if k<0 or k>n then 0 elif k=0 then 1 else 2*bin2(n-1,k-1)+bin2(n-1,k); fi; end; # _N. J. A. Sloane_, Jun 01 2009

%t Flatten[Table[CoefficientList[(1 + 2*x)^n, x], {n, 0, 10}]][[1 ;; 59]] (* _Jean-François Alcover_, May 17 2011 *)

%t BinomialROW[n_, k_, t_] := Sum[Binomial[n, k]*Binomial[k, j]*(-1)^(k - j)*t^j, {j, 0, k}]; Column[Table[BinomialROW[n, k, 3], {n, 0, 10}, {k, 0, n}], Center] (* _Kolosov Petro_, Jan 28 2019 *)

%o (Haskell)

%o a013609 n = a013609_list !! n

%o a013609_list = concat $ iterate ([1,2] *) [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 a013609 n k = a013609_tabl !! n !! k

%o a013609_row n = a013609_tabl !! n

%o a013609_tabl = iterate (\row -> zipWith (+) ([0] ++ row) $

%o zipWith (+) ([0] ++ row) (row ++ [0])) [1]

%o -- _Reinhard Zumkeller_, Jul 22 2013, Feb 27 2013

%o (PARI) /* same as in A092566 but use */

%o steps=[[1,0], [1,1], [1,1]]; /* note double [1,1] */

%o /* _Joerg Arndt_, Jul 01 2011 */

%o (Maxima) a(n,k):=coeff(expand((1+2*x)^n),x^k);

%o create_list(a(n,k),n,0,6,k,0,n); /* _Emanuele Munarini_, Nov 21 2012 */

%o (Magma) [2^k*Binomial(n,k): k in [0..n], n in [0..15]]; // _G. C. Greubel_, Sep 17 2021

%o (Sage) flatten([[2^k*binomial(n,k) for k in (0..n)] for n in (0..15)]) # _G. C. Greubel_, Sep 17 2021

%Y Cf. A007318, A013610, etc.

%Y Appears in A167580 and A167591. - _Johannes W. Meijer_, Nov 23 2009

%Y From _Johannes W. Meijer_, Sep 22 2010: (Start)

%Y Triangle sums (see the comments): A000244 (Row1); A000012 (Row2); A001045 (Kn11); A026644 (Kn12); 4*A011377 (Kn13); A000129 (Kn21); A094706 (Kn22); A099625 (Kn23); A001653 (Kn3); A007583 (Kn4); A046717 (Fi1); A007051 (Fi2); A077949 (Ca1); A008998 (Ca2); A180675 (Ca3); A092467 (Ca4); A052942 (Gi1); A008999 (Gi2); A180676 (Gi3); A180677 (Gi4); A140413 (Ze1); A180678 (Ze2); A097117 (Ze3); A055588 (Ze4).

%Y (End)

%Y Cf. A024023, A038207, A046816, A105728, A115068, A135278, A171977, A180662.

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

%K tabl,nonn,easy,nice,changed

%O 0,3

%A _N. J. A. Sloane_