cp's OEIS Frontend

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

%I A139382 #67 May 07 2025 11:35:06
%S A139382 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 A139382 7870,2247,120,1,1,1093,34041,122861,77527,9807,247,1,1,3280,239380,
%U A139382 1876956,2526198,695368,41176,502,1,1,9841,1678940,28393720,80189094,46334382,5924720,169186,1013,1
%N A139382 Triangle read by rows, T(n,k) = (2^k-1) * T(n-1,k) + T(n-1,k-1).
%C A139382 Row sums = A135922 starting with offset 1: (1, 2, 6, 26, 158, 1330, ...).
%C A139382 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
%C A139382 T(n,k) is the number of naturally labeled posets on [n] with height at most one containing exactly k minimal elements.  See link by David Bevan and others below. - _Geoffrey Critzer_, May 03 2025
%H A139382 G. C. Greubel, <a href="/A139382/b139382.txt">Rows n = 1..100 of triangle, flattened</a>
%H A139382 David Bevan, Gi-Sang Cheon and Sergey Kitaev, <a href="https://arxiv.org/abs/2311.08023">On naturally labelled posets and permutations avoiding 12-34</a>, arXiv:2311.08023 [math.CO], 2023.
%H A139382 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 A139382 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 A139382 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 A139382 From _Werner Schulte_, Apr 02 2019: (Start)
%F A139382 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 A139382 Sum_{k>0} col(k,t) * (Product_{i=1..k-1} (1 - 2^i)) = t (empty product equals 1).
%F A139382 Sum_{k=1..n} (-1)^k * 2^binomial(k,2) * T(n,k) = (-1)^n for n > 0.
%F A139382 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 A139382 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 A139382 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 A139382 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 A139382 First few rows of the triangle are:
%e A139382   1;
%e A139382   1,   1;
%e A139382   1,   4,   1;
%e A139382   1,  13,  11,   1;
%e A139382   1,  40,  90,  26,   1;
%e A139382   1, 121, 670, 480,  57,   1;
%e A139382   ...
%e A139382 a(13) = T(5,3) = 90 = (2^3 - 1)*T(4,3) + T(4,2) = 7*11 + 13.
%p A139382 # Uses[qStirling2 from A333143]
%p A139382 seq(seq(qStirling2(n, k, 2), k=0..n), n=0..9); # _Peter Luschny_, Mar 10 2020
%p A139382 # Alternative.
%p A139382 A139382 := proc(n, k) if k = 1 then 1 elif k = n then 1 elif k < 1 then 0 else
%p A139382 (2^k - 1)*A139382(n-1, k) + A139382(n-1, k-1) fi end:
%p A139382 for n from 1 to 8 do seq(A139382(n, k), k = 1..n) od; # _Peter Luschny_, Jun 28 2022
%t A139382 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 A139382 (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 A139382 for(n=1,12, for(k=1,n, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Apr 02 2019
%o A139382 (Sage)
%o A139382 @CachedFunction
%o A139382 def T(n, k):
%o A139382    if (k==1): return 1
%o A139382    elif (k==n): return 1
%o A139382    else: return (2^k-1)*T(n-1, k) + T(n-1, k-1)
%o A139382 [[T(n, k) for k in (1..n)] for n in (1..12)] # _G. C. Greubel_, Apr 02 2019
%Y A139382 Cf. A008277, A135922, A333143.
%Y A139382 Cf. A000295 (2nd diagonal), A003462 (column 2), A016212 (column 3), A156823.
%K A139382 nonn,tabl
%O A139382 1,5
%A A139382 _Gary W. Adamson_, Apr 16 2008
%E A139382 More terms from _G. C. Greubel_, Apr 02 2019