A338131 Triangle read by rows, T(n, k) = k^(n - k) + Sum_{i = 1..n-k} k^(n - k - i)*2^(i - 1), for 0 <= k <= n.

1, 1, 1, 2, 2, 1, 4, 4, 3, 1, 8, 8, 8, 4, 1, 16, 16, 20, 14, 5, 1, 32, 32, 48, 46, 22, 6, 1, 64, 64, 112, 146, 92, 32, 7, 1, 128, 128, 256, 454, 376, 164, 44, 8, 1, 256, 256, 576, 1394, 1520, 828, 268, 58, 9, 1, 512, 512, 1280, 4246, 6112, 4156, 1616, 410, 74, 10, 1

Offset: 0

Author

Werner Schulte, Oct 11 2020

Keywords

• nonn
• easy
• tabl

Comments

This number triangle is case s = 2 of the triangles T(s; n,k) depending on some fixed integer s. Here are several (generalized) formulas and properties (attention: negative values are possible if s < 0):

(1) T(s; n,k) = k^(n-k) + Sum_{i=1..n-k} k^(n-k-i)*s^(i-1) for 0<=k<=n;

(2) T(s; n,n) = 1 for n >= 0, and T(s; n,n-1) = n for n > 0;

(3) T(s; n+1,k) = k * T(s; n,k) + s^(n-k) for 0<=k<=n;

(4) T(s; n,k) = (k+s) * T(s; n-1,k) - s*k * T(s; n-2,k) for 0<=k<=n-2;

(5) G.f. of column k: Sum_{n>=k} T(s; n,k)*t^n = ((1-(s-1)*t)/(1-s*t))

*(t^k/(1-k*t)) when t^k/(1-k*t) is g.f. of column k>=0 of A004248.

Examples

			The number triangle T(n, k) for 0 <= k <= n starts:
n\ k :    0     1      2      3      4      5      6     7    8    9   10
=========================================================================
   0 :    1
   1 :    1     1
   2 :    2     2      1
   3 :    4     4      3      1
   4 :    8     8      8      4      1
   5 :   16    16     20     14      5      1
   6 :   32    32     48     46     22      6      1
   7 :   64    64    112    146     92     32      7     1
   8 :  128   128    256    454    376    164     44     8    1
   9 :  256   256    576   1394   1520    828    268    58    9    1
  10 :  512   512   1280   4246   6112   4156   1616   410   74   10   1
		

Crossrefs

Cf. A004248.

For columns k = 0, 1, 2, 3, 4 see A011782, A000079, A001792, A027649, A010036 respectively.

Programs

Maple

T := proc(n, k) if k = 0 then `if`(n = 0, 1, 2^(n-1)) elif k = 2 then n*2^(n-3)
else (k^(n-k)*(1-k) + 2^(n-k))/(2-k) fi end:
seq(seq(T(n, k), k=0..n), n=0..10); # Peter Luschny, Oct 29 2020

PARI

T(n,k) = k^(n-k) + sum(i=1, n-k, k^(n-k-i) * 2^(i-1));
matrix(7,7, n, k, if(n>=k, T(n-1,k-1), 0)) \\ to see the triangle \\ Michel Marcus, Oct 12 2020

Formula

T(n,k) = ((k-1) * k^(n-k) - 2^(n-k)) / (k-2) if k <> 2, and T(n,2) = n * 2^(n-3) for n >= k.

T(n,n) = 1 for n >= 0, and T(n,n-1) = n for n > 0.

T(n+1,k) = k * T(n,k) + 2^(n-k) for 0 <= k <= n.

T(n,k) = (k+2) * T(n-1,k) - 2*k * T(n-2,k) for 0 <= k <= n-2.

T(n,k) = k * T(n-1,k) + T(n-1,k-1) - (k-1) * T(n-2,k-1) for 0 < k < n.

G.f. of column k >= 0: Sum_{n>=k} T(n,k) * t^n = ((1-t) / (1-2*t)) * (t^k / (1-k*t)) when t^k / (1-k*t) is g. f. of column k of A004248.

G.f.: Sum_{n>=0, k=0..n} T(n,k) * x^k * t^n = ((1-t) / (1-2*t)) * (Sum_{k>=0} (x*t)^k / (1-k*t)).