OFFSET
0,4
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.
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)).
EXAMPLE
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
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
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
Werner Schulte, Oct 11 2020
STATUS
approved