A112626 Triangle read by rows: T(n,k) = Sum_{j=0..n} binomial(n, k+j)*2^(n-k-j).

1, 3, 1, 9, 5, 1, 27, 19, 7, 1, 81, 65, 33, 9, 1, 243, 211, 131, 51, 11, 1, 729, 665, 473, 233, 73, 13, 1, 2187, 2059, 1611, 939, 379, 99, 15, 1, 6561, 6305, 5281, 3489, 1697, 577, 129, 17, 1, 19683, 19171, 16867, 12259, 6883, 2851, 835, 163, 19, 1, 59049, 58025

Offset

0,2

Comments

T(n, 0) = A000244(n), T(n, 1) = A001047(n), T(n, 2) = A066810(n).

Column 0 is the row sums of A038207 starting at column 0, column 1 is the row sums of A038207 starting at column 1 etc. etc. Helpful suggestions related to Riordan arrays given by Paul Barry.

Riordan array ( 1/(1 - 3*x), x/(1 - 2*x) ). Matrix inverse is a signed version of A209149. - Peter Bala, Jul 17 2013

T(n,k) is the number of strings of length n over an alphabet of 3 letters that contain a given string of length k as a subsequence. - Robert Israel, Jan 14 2020

Links

G. C. Greubel, Rows n = 0..100 of triangle, flattened

Formula

T(n, k) = Sum_{j=0..n} binomial(n, k+j)*2^(n-k-j).

O.g.f. (by columns): x^k /((1-3*x)*(1-2*x)^k). - Frank Ruskey and class

T(n,k) = Sum_{j=k..n} binomial(n,j)*2^(n-j). - Ross La Haye, May 02 2006

Binomial transform (by columns) of A055248.

Example

Triangle begins as:
    1;
    3,   1;
    9,   5,   1;
   27,  19,   7,   1;
   81,  65,  33,   9,  1;
  243, 211, 131,  51, 11,  1;
  729, 665, 473, 233, 73, 13, 1...

Maple

seq(seq( add(binomial(n, j)*2^(n-j), j=k..n), k=0..n), n=0..10); # G. C. Greubel, Nov 18 2019

Mathematica

Flatten[Table[Sum[Binomial[n, k+m]*2^(n-k-m), {m, 0, n}], {n, 0, 10}, {k, 0, n}]]

Prog

(PARI) T(n, k) = sum(j=k, n, binomial(n, j)*2^(n-j)); \\ G. C. Greubel, Nov 18 2019
(Magma) [&+[Binomial(n, j)*2^(n-j): j in [k..n]]: k in [0..n], n in [0..10]]; // G. C. Greubel, Nov 18 2019
(Sage) [[sum(binomial(n, j)*2^(n-j) for j in (0..n)) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Nov 18 2019
(GAP) Flat(List([0..10], n-> List([0..n], k-> Sum([k..n], j-> Binomial(n, j)*2^(n-j)) ))); # G. C. Greubel, Nov 18 2019

Crossrefs

Row sums = n*3^(n-1) + 3^n = A006234(n+3) (Frank Ruskey and class).

Cf. A000244, A001047, A038207, A066810.

Cf. A209149 (unsigned matrix inverse).

Sequence in context: A371746 A005533 A331257 * A050155 A270236 A140714

Adjacent sequences: A112623 A112624 A112625 * A112627 A112628 A112629

Keyword

nonn,tabl

Author

Ross La Haye, Dec 26 2005

Extensions

More terms from Ross La Haye, Dec 31 2006

Status

approved