A139382 Triangle read by rows, T(n,k) = (2^k-1) * T(n-1,k) + T(n-1,k-1).
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
Offset: 1
Examples
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.
Links
- G. C. Greubel, Rows n = 1..100 of triangle, flattened
- David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
- Yue Cai, Richard Ehrenborg, and Margaret A. Readdy, q-Stirling numbers revisited, arXiv:1706.06623 [math.CO], 2017.
- Yue Cai, Richard Ehrenborg, and Margaret A. Readdy, q-Stirling numbers revisited, Electronic Journal of Combinatorics, 25 Issue 1 (2018), Paper #P1.37.
Crossrefs
Programs
-
Maple
# Uses[qStirling2 from A333143] seq(seq(qStirling2(n, k, 2), k=0..n), n=0..9); # Peter Luschny, Mar 10 2020 # Alternative. A139382 := proc(n, k) if k = 1 then 1 elif k = n then 1 elif k < 1 then 0 else (2^k - 1)*A139382(n-1, k) + A139382(n-1, k-1) fi end: for n from 1 to 8 do seq(A139382(n, k), k = 1..n) od; # Peter Luschny, Jun 28 2022
-
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 *) -
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
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,...].
From Werner Schulte, Apr 02 2019: (Start)
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) = (1/(2^binomial(k,2)*A005329(k))) * Sum_{j=0..k} (-1)^(k-j)*2^binomial(k-j,2)*A022166(k,j)*(2^j-1)^n. - Fabian Pereyra, Jan 27 2024
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
Extensions
More terms from G. C. Greubel, Apr 02 2019
Comments