|
| |
|
|
A139382
|
|
Triangle read by rows, T(n,k) = (2^k-1) * T(n-1,k) + T(n-1,k-1).
|
|
8
|
|
|
|
1, 1, 1, 1, 4, 1, 1, 13, 11, 1, 1, 40, 90, 26, 1, 1, 121, 670, 480, 57, 1, 1, 364, 4811, 7870, 2247, 120, 1, 1, 1093, 34041, 122861, 77527, 9807, 247, 1, 1, 3280, 239380, 1876956, 2526198, 695368, 41176, 502, 1, 1, 9841, 1678940, 28393720, 80189094, 46334382, 5924720, 169186, 1013, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
Row sums = A135922 starting with offset 1: (1, 2, 6, 26, 158, 1330, ...).
This triangle is the q-analog of A008277 (Stirling numbers of the 2nd kind) for q=2 (see Cai et al. link). - Werner Schulte, Apr 04 2019
|
|
|
LINKS
|
Yue Cai, Richard Ehrenborg, and Margaret A. Readdy, q-Stirling numbers revisited, Electronic Journal of Combinatorics, 25 Issue 1 (2018), Paper #P1.37.
|
|
|
FORMULA
|
Triangle read by rows, T(n,k) = (2^k-1) * T(n-1,k) + T(n-1,k-1). Let X = an infinite bidiagonal matrix with (1,3,7,15,31...) in the main diagonal and (1,1,1,...) in the subdiagonal. n-th row of the triangle = X^n * [1,0,0,0,...].
G.f. of column k: col(k,t) = Sum_{n>=k} T(n,k)*t^n = t^k/Product_{i=1..k} (1 - (2^i-1)*t) for k > 0.
Sum_{k>0} col(k,t) * (Product_{i=1..k-1} (1 - 2^i)) = t (empty product equals 1).
Sum_{k=1..n} (-1)^k * 2^binomial(k,2) * T(n,k) = (-1)^n for n > 0.
An example for k=3: g.f. of column 3: col(3,t) = Sum_{n>=3} T(n,3) * t^n = 1*t^3 + 11*t^4 + 90*t^5 + 670*t^6 + ... = t^3 * (1 + 11*t + 90*t^2 + 670*t^3 + ...) = t^3 / Product_{i=1..3} (1 - (2^i - 1)*t) = t^3 / ((1 - t) * (1 - 3*t) * (1 - 7*t)) = t^3 / (1 - 11*t + 31*t^2 - 21*t^3). Perhaps the following recurrence formula is useful too: col(k,t) = col(k-1,t) * t / (1 - (2^k - 1)*t) for k > 1 with initial value col(1,t) = t / (1 - t). Finally: col(k,t) is the g.f. of column k.
With regard to the 2nd formula: We can it replace with the following formula: Sum_{k=1..n} T(n,k) * (Product_{i=1..k-1} (1-2^i)) = A000007(n-1) for n > 0 with empty product 1 (case k=1). Example for n=5: 1*1 + (-1)*40 + (-1)*(-3)*90 + (-1)*(-3)*(-7)*26 + (-1)*(-3)*(-7)*(-15)*1 = 0. (End)
T(n,k) = Sum_{j=k..n} (-1)^(n-j)*binomial(n,j)*qBinomial(j,k,2), where qBinomial(n,k,2) is A022166(n,k). - Fabian Pereyra, Jan 31 2024
|
|
|
EXAMPLE
|
First few rows of the triangle are:
1;
1, 1;
1, 4, 1;
1, 13, 11, 1;
1, 40, 90, 26, 1;
1, 121, 670, 480, 57, 1;
...
a(13) = T(5,3) = 90 = (2^3 - 1)*T(4,3) + T(4,2) = 7*11 + 13.
|
|
|
MAPLE
|
A139382 := proc(n, k) if k = 1 then 1 elif k = n then 1 elif k < 1 then 0 else
|
|
|
MATHEMATICA
|
T[1, 1]:= 1; T[n_, k_]:= T[n, k] = If[k > n || k < 1, 0, (2^k-1)*T[n-1, k] + T[n-1, k-1]]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] (* G. C. Greubel, Apr 02 2019 *)
|
|
|
PROG
|
(PARI) {T(n, k) = if(k<1 || k>n, 0, if(n==1 && k==1, 1, (2^k-1)*T(n-1, k) + T(n-1, k-1)))};
for(n=1, 12, for(k=1, n, print1(T(n, k), ", "))) \\ G. C. Greubel, Apr 02 2019
(Sage)
@CachedFunction
def T(n, k):
if (k==1): return 1
elif (k==n): return 1
else: return (2^k-1)*T(n-1, k) + T(n-1, k-1)
[[T(n, k) for k in (1..n)] for n in (1..12)] # G. C. Greubel, Apr 02 2019
# Alternative:
(Sage) # uses[qStirling2 from A333143]
seq(seq(qStirling2(n, k, 2), k=0..n), n=0..9); # Peter Luschny, Mar 10 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
