A013610 Triangle of coefficients in expansion of (1+3*x)^n.

1, 1, 3, 1, 6, 9, 1, 9, 27, 27, 1, 12, 54, 108, 81, 1, 15, 90, 270, 405, 243, 1, 18, 135, 540, 1215, 1458, 729, 1, 21, 189, 945, 2835, 5103, 5103, 2187, 1, 24, 252, 1512, 5670, 13608, 20412, 17496, 6561, 1, 27, 324, 2268, 10206, 30618, 61236, 78732, 59049, 19683

Offset

0,3

Comments

T(n,k) is the number of lattice paths from (0,0) to (n,k) with steps (1,0) and three 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

Rows of A027465 reversed. - Michael Somos, Feb 14 2002

T(n,k) equals the number of n-length words on {0,1,2,3} having n-k zeros. - Milan Janjic, Jul 24 2015

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

Links

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened

J. Goldman and J. Haglund, Generalized rook polynomials, J. Combin. Theory A91 (2000), 509-530, 1-rook coefficients on the 3xn board (all heights 3) with k rooks

Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.

Formula

G.f.: 1 / (1 - x*(1+3*y)).

Row sums are 4^n. - Joerg Arndt, Jul 01 2011

T(n,k) = 3^k*C(n,k) = Sum_{i=n-k..n} C(i,n-k)*C(n,i)*2^(n-i). - Mircea Merca, Apr 28 2012

From Peter Bala, Dec 22 2014: (Start)

Riordan array ( 1/(1 - x), 3*x/(1 - x) ).

exp(3*x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(3*x)*(1 + 9*x + 27*x^2/2! + 27*x^3/3!) = 1 + 12*x + 90*x^2/2! + 540*x^3/3! + 2835*x^4/4! + .... The same property holds more generally for Riordan arrays of the form ( f(x), 3*x/(1 - x) ). (End)

T(n,k) = Sum_{j=0..k} (-1)^(k-j) * binomial(n,k) * binomial(k,j) * 4^j. - Kolosov Petro, Jan 28 2019

Example

Triangle begins
  1;
  1,    3;
  1,    6,    9;
  1,    9,   27,   27;
  1,   12,   54,  108,   81;
  1,   15,   90,  270,  405,  243;
  1,   18,  135,  540, 1215, 1458,  729;
  1,   21,  189,  945, 2835, 5103, 5103, 2187;

Maple

T:= n-> (p-> seq(coeff(p, x, k), k=0..n))((1+3*x)^n):
seq(T(n), n=0..10);  # Alois P. Heinz, Jul 25 2015

Mathematica

t[n_, k_] := Binomial[n, k]*3^(n-k); Table[t[n, n-k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 05 2013 *)
BinomialROW[n_, k_, t_] := Sum[Binomial[n, k]*Binomial[k, j]*(-1)^(k - j)*t^j, {j, 0, k}]; Column[Table[BinomialROW[n, k, 4], {n, 0, 10}, {k, 0, n}], Center] (* Kolosov Petro, Jan 28 2019 *)

Prog

(PARI) {T(n, k) = polcoeff((1 + 3*x)^n, k)}; /* Michael Somos, Feb 14 2002 */
(PARI) /* same as in A092566 but use */
steps=[[1, 0], [1, 1], [1, 1], [1, 1]]; /* note triple [1, 1] */
/* Joerg Arndt, Jul 01 2011 */
(Haskell)
a013610 n k = a013610_tabl !! n !! k
a013610_row n = a013610_tabl !! n
a013610_tabl = iterate (\row ->
   zipWith (+) (map (* 1) (row ++ [0])) (map (* 3) ([0] ++ row))) [1]
-- Reinhard Zumkeller, May 26 2013
(Magma) [3^k*Binomial(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, May 19 2021
(Sage) flatten([[3^k*binomial(n, k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 19 2021

Crossrefs

Cf. A007318, A013609, A027465, etc.

Diagonals of the triangle: A000244 (k=n), A027471 (k=n-1), A027472 (k=n-2), A036216 (k=n-3), A036217 (k=n-4), A036219 (k=n-5), A036220 (k=n-6), A036221 (k=n-7), A036222 (k=n-8), A036223 (k=n-9), A172362 (k=n-10).

Sequence in context: A074475 A144877 A049410 * A008573 A089710 A065918

Adjacent sequences: A013607 A013608 A013609 * A013611 A013612 A013613

Keyword

tabl,nonn,easy

Author

N. J. A. Sloane

Status

approved