cp's OEIS Frontend

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

%I A013610 #65 Feb 23 2025 09:28:50
%S A013610 1,1,3,1,6,9,1,9,27,27,1,12,54,108,81,1,15,90,270,405,243,1,18,135,
%T A013610 540,1215,1458,729,1,21,189,945,2835,5103,5103,2187,1,24,252,1512,
%U A013610 5670,13608,20412,17496,6561,1,27,324,2268,10206,30618,61236,78732,59049,19683
%N A013610 Triangle of coefficients in expansion of (1+3*x)^n.
%C A013610 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
%C A013610 Rows of A027465 reversed. - _Michael Somos_, Feb 14 2002
%C A013610 T(n,k) equals the number of n-length words on {0,1,2,3} having n-k zeros. - _Milan Janjic_, Jul 24 2015
%C A013610 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
%H A013610 Reinhard Zumkeller, <a href="/A013610/b013610.txt">Rows n = 0..125 of triangle, flattened</a>
%H A013610 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 on the 3xn board (all heights 3) with k rooks
%H A013610 Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%F A013610 G.f.: 1 / (1 - x*(1+3*y)).
%F A013610 Row sums are 4^n. - _Joerg Arndt_, Jul 01 2011
%F A013610 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
%F A013610 From _Peter Bala_, Dec 22 2014: (Start)
%F A013610 Riordan array ( 1/(1 - x), 3*x/(1 - x) ).
%F A013610 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)
%F A013610 T(n,k) = Sum_{j=0..k} (-1)^(k-j) * binomial(n,k) * binomial(k,j) * 4^j. - _Kolosov Petro_, Jan 28 2019
%F A013610 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
%e A013610 Triangle begins
%e A013610   1;
%e A013610   1,    3;
%e A013610   1,    6,    9;
%e A013610   1,    9,   27,   27;
%e A013610   1,   12,   54,  108,   81;
%e A013610   1,   15,   90,  270,  405,  243;
%e A013610   1,   18,  135,  540, 1215, 1458,  729;
%e A013610   1,   21,  189,  945, 2835, 5103, 5103, 2187;
%p A013610 T:= n-> (p-> seq(coeff(p, x, k), k=0..n))((1+3*x)^n):
%p A013610 seq(T(n), n=0..10);  # _Alois P. Heinz_, Jul 25 2015
%t A013610 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 *)
%t A013610 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 A013610 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 *)
%o A013610 (PARI) {T(n, k) = polcoeff((1 + 3*x)^n, k)}; /* _Michael Somos_, Feb 14 2002 */
%o A013610 (PARI) /* same as in A092566 but use */
%o A013610 steps=[[1,0], [1,1], [1,1], [1,1]]; /* note triple [1,1] */
%o A013610 /* _Joerg Arndt_, Jul 01 2011 */
%o A013610 (Haskell)
%o A013610 a013610 n k = a013610_tabl !! n !! k
%o A013610 a013610_row n = a013610_tabl !! n
%o A013610 a013610_tabl = iterate (\row ->
%o A013610    zipWith (+) (map (* 1) (row ++ [0])) (map (* 3) ([0] ++ row))) [1]
%o A013610 -- _Reinhard Zumkeller_, May 26 2013
%o A013610 (Magma) [3^k*Binomial(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, May 19 2021
%o A013610 (Sage) flatten([[3^k*binomial(n,k) for k in (0..n)] for n in (0..12)]) # _G. C. Greubel_, May 19 2021
%Y A013610 Cf. A007318, A013609, A027465, etc.
%Y A013610 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).
%K A013610 tabl,nonn,easy
%O A013610 0,3
%A A013610 _N. J. A. Sloane_