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
KEYWORD
AUTHOR
STATUS
approved