A016212 -id:A016212 - cp's OEIS frontend

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

Gary W. Adamson, Apr 16 2008

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

			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.

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.

Cf. A008277, A135922, A333143.

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

# 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

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

{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

@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

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

More terms from G. C. Greubel, Apr 02 2019

A327751 Square array T(n,k), n>=0, k>=0, read by antidiagonals, where T(n,k) is the constant term in the expansion of (-1 + Product_{j=1..n} (1 + x_j + 1/x_j))^k.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 8, 0, 1, 0, 6, 24, 26, 0, 1, 0, 0, 216, 264, 80, 0, 1, 0, 20, 1200, 5646, 2160, 242, 0, 1, 0, 0, 8840, 101520, 121200, 16080, 728, 0, 1, 0, 70, 58800, 2103740, 6136800, 2410326, 115464, 2186, 0, 1

Offset: 0

Seiichi Manyama, Oct 30 2019

T(n,k) is the number of k-step closed walks (from origin to origin) in n-dimensional lattice, using steps (t_1,t_2, ... ,t_n) (t_j = -1, 1 or 0 for 1 <= j <= n) except for (0,0, ... ,0) (t_j = 0 for 1 <= j <= n).

			Square array begins:
   1, 0,   0,     0,       0,         0, ...
   1, 0,   2,     0,       6,         0, ...
   1, 0,   8,    24,     216,      1200, ...
   1, 0,  26,   264,    5646,    101520, ...
   1, 0,  80,  2160,  121200,   6136800, ...
   1, 0, 242, 16080, 2410326, 332810400, ...

Seiichi Manyama, Antidiagonals n = 0..93, flattened

Columns k=0-3 give A000012, A000004, A024023, 24*A016212(n-2).
Rows n=0-4 give A000007, A126869, A094061, A328874, A328875.
Main diagonal is A326920.
Cf. A002426, A328718.

T(n,k) = Sum_{j=0..k} (-1)^(k-j) * binomial(k,j) * A002426(j)^n.

A341590 a(n) = (Sum_{j=1..3} StirlingS1(3,j)*(2^j-1)^n)/3!.

Original entry on oeis.org

0, 0, 4, 44, 360, 2680, 19244, 136164, 957520, 6715760, 47049684, 329465884, 2306615480, 16147371240, 113034787324, 791253077204, 5538800238240, 38771687761120, 271402072608164, 1899815283098124, 13298709306209800

Offset: 0

Fabio Visonà, Feb 15 2021

Number of 3-element subsets of the powerset P([n]) such that their union is equal to the universe [n] = {1,2, ... ,n}.
StirlingS1(k,j) is a signed Stirling number of the first kind (cf. A048994).
In general, the number of k-element subsets of P([n]) such that their union is equal to [n] is (Sum_{j=0..k} StirlingS1(k,j)*(2^j-1)^n)/k!. That can be expressed also as (-1)^n*(Sum_{j=0..n} binomial(n,j)*(-1)^j*binomial(2^j,k)). See the below link to Mathematics Stack Exchange for proofs. The case k = 2 is A003462.

			For n = 2 and [n] = [2] = {1,2} the a(2) = 4 solutions are {{},{1},{2}}, {{},{1},{1,2}}, {{},{2},{1,2}}, {{1},{2},{1,2}}.

Fabio Visonà, Table of n, a(n) for n = 0..100
Mathematics Stack Exchange, Answer to question about tuples of distinct sets in P([n]) such that their union is equal to [n]
Index entries for linear recurrences with constant coefficients, signature (11,-31,21).

Cf. A003462, A016212, A048994.

LinearRecurrence[{11,-31,21},{0,0,4},30] (* Harvey P. Dale, Mar 02 2025 *)

a(n) = (Sum_{j=1..3} A048994(3,j)*(2^j-1)^n)/3!.
a(n) = (2 - 3^(1+n) + 7^n)/6.
a(n) = (-1)^n*(Sum_{j=0..n} binomial(n,j)*(-1)^j*binomial(2^j,3)).
G.f.: 4*x^2/(1 - 11*x + 31*x^2 - 21*x^3). - Stefano Spezia, Feb 15 2021
a(n) = 4 * A016212(n-2) for n >= 2. - Alois P. Heinz, Feb 15 2021

A109021 (27^n - 63^n + 4)/6.

Original entry on oeis.org

0, 0, 8, 88, 720, 5360, 38488, 272328, 1915040, 13431520, 94099368, 658931768, 4613230960, 32294742480, 226069574648, 1582506154408, 11077600476480, 77543375522240, 542804145216328, 3799630566196248, 26597418612419600, 186181944234074800, 1303273651479936408

Offset: 0

Alex Fink and R. K. Guy, Aug 18 2005

Number of incongruent integer-edged Heron triangles whose circumdiameter is the product of n distinct primes of shape 4k + 1 and which are not right-angled.

Index entries for linear recurrences with constant coefficients, signature (11, -31, 21).

Cf. A016212, A109020, A003462.

Table[(2*7^n-6*3^n+4)/6,{n,0,30}] (* or *) LinearRecurrence[{11,-31,21},{0,0,8},30] (* Harvey P. Dale, Jan 30 2013 *)

a(n) = 8*A016212(n-2).
(0)=0, a(1)=0, a(2)=8, a(n)=11*a(n-1)-31*a(n-2)+21*a(n-3). - Harvey P. Dale, Jan 30 2013
G.f.: -8*x^2 / ( (x-1)*(3*x-1)*(7*x-1) ). - R. J. Mathar, Feb 10 2016

A346796 Number of equivalence classes of triangles in an n-dimensional hypercube, equivalent up to translation of difference vectors corresponding to edges.

Original entry on oeis.org

0, 2, 22, 180, 1340, 9622, 68082, 478760, 3357880, 23524842, 164732942, 1153307740, 8073685620, 56517393662, 395626538602, 2769400119120, 19385843880560, 135701036304082, 949907641549062, 6649354653104900

Offset: 1

Henry L. Fleischmann, Aug 04 2021

Proved via a combinatorial argument.

			The 1-dimensional hypercube (vertices 0 and 1 on a line) has no triangles and thus no classes of triangle equivalent up to edge translation, so a(1)=0.
A square, the 2-dimensional hypercube, has two distinct right triangles up to edge translation, so a(2)=2.

Henry L. Fleischmann et al., Distinct Angle Problems and Variants, arXiv:2108.12015 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (11,-31,21).

Cf. A016212 (allowing flips as well as edge translations, up to offset).

def a(n): return (7**n - 3**(n+1) + 2)//12

a(n) = (7^n - 3^(n+1) + 2)/12.
a(n) = 2*A016212(n-2) for n >= 2.
G.f.: 2*x^2/(1 - 11*x + 31*x^2 - 21*x^3). - Stefano Spezia, Aug 04 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A327751 Square array T(n,k), n>=0, k>=0, read by antidiagonals, where T(n,k) is the constant term in the expansion of (-1 + Product_{j=1..n} (1 + x_j + 1/x_j))^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A341590 a(n) = (Sum_{j=1..3} StirlingS1(3,j)*(2^j-1)^n)/3!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A109021 (2*7^n - 6*3^n + 4)/6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A346796 Number of equivalence classes of triangles in an n-dimensional hypercube, equivalent up to translation of difference vectors corresponding to edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A109021 (27^n - 63^n + 4)/6.