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

Author

N. J. A. Sloane

Keywords

• tabl
• nonn
• easy

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

Examples

			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;
		

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.

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).

Programs

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

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 *)
T[0, 0] := 1; T[n_, k_]/;0<=k<=n := T[n, k] = 3T[n-1, k-1]+T[n-1, k]; T[n_, k_] := 0; Flatten@Table[T[n, k], {n, 0, 7}, {k, 0, n}] (* Oliver Seipel, Jan 26 2025 *)

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 */

Sage

flatten([[3^k*binomial(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 19 2021

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

T(0,0)=1, T(n,k)=3*T(n-1,k-1)+T(n-1,k) for 0<=k<=n, T(n,k)=0 for k<0 or k>n. - Oliver Seipel, Feb 10 2025