login
Triangle read by rows, T(n,k) = (2^k-1) * T(n-1,k) + T(n-1,k-1).
8

%I #58 Sep 23 2024 10:12:00

%S 1,1,1,1,4,1,1,13,11,1,1,40,90,26,1,1,121,670,480,57,1,1,364,4811,

%T 7870,2247,120,1,1,1093,34041,122861,77527,9807,247,1,1,3280,239380,

%U 1876956,2526198,695368,41176,502,1,1,9841,1678940,28393720,80189094,46334382,5924720,169186,1013,1

%N Triangle read by rows, T(n,k) = (2^k-1) * T(n-1,k) + T(n-1,k-1).

%C Row sums = A135922 starting with offset 1: (1, 2, 6, 26, 158, 1330, ...).

%C 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

%H G. C. Greubel, <a href="/A139382/b139382.txt">Rows n = 1..100 of triangle, flattened</a>

%H Yue Cai, Richard Ehrenborg, and Margaret A. Readdy, <a href="https://arxiv.org/abs/1706.06623">q-Stirling numbers revisited</a>, arXiv:1706.06623 [math.CO], 2017.

%H Yue Cai, Richard Ehrenborg, and Margaret A. Readdy, <a href="https://doi.org/10.37236/6829">q-Stirling numbers revisited</a>, Electronic Journal of Combinatorics, 25 Issue 1 (2018), Paper #P1.37.

%F 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,...].

%F From _Werner Schulte_, Apr 02 2019: (Start)

%F 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.

%F Sum_{k>0} col(k,t) * (Product_{i=1..k-1} (1 - 2^i)) = t (empty product equals 1).

%F Sum_{k=1..n} (-1)^k * 2^binomial(k,2) * T(n,k) = (-1)^n for n > 0.

%F 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.

%F 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)

%F 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

%F 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

%e First few rows of the triangle are:

%e 1;

%e 1, 1;

%e 1, 4, 1;

%e 1, 13, 11, 1;

%e 1, 40, 90, 26, 1;

%e 1, 121, 670, 480, 57, 1;

%e ...

%e a(13) = T(5,3) = 90 = (2^3 - 1)*T(4,3) + T(4,2) = 7*11 + 13.

%p A139382 := proc(n, k) if k = 1 then 1 elif k = n then 1 elif k < 1 then 0 else

%p (2^k - 1)*A139382(n-1, k) + A139382(n-1, k-1) fi end:

%p for n from 1 to 8 do seq(A139382(n, k), k = 1..n) od; # _Peter Luschny_, Jun 28 2022

%t 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 *)

%o (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)))};

%o for(n=1,12, for(k=1,n, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Apr 02 2019

%o (Sage)

%o @CachedFunction

%o def T(n, k):

%o if (k==1): return 1

%o elif (k==n): return 1

%o else: return (2^k-1)*T(n-1, k) + T(n-1, k-1)

%o [[T(n, k) for k in (1..n)] for n in (1..12)] # _G. C. Greubel_, Apr 02 2019

%o (Sage)

%o # Alternative. Uses[qStirling2 from A333143]

%o seq(seq(qStirling2(n, k, 2), k=0..n), n=0..9); # _Peter Luschny_, Mar 10 2020

%Y Cf. A008277, A135922, A333143.

%Y Cf. A000295 (2nd diagonal), A003462 (column 2), A016212 (column 3), A156823.

%K nonn,tabl

%O 1,5

%A _Gary W. Adamson_, Apr 16 2008

%E More terms from _G. C. Greubel_, Apr 02 2019