A135922 -id:A135922 - cp's OEIS frontend

A006116 Sum of Gaussian binomial coefficients [n,k] for q=2 and k=0..n.

1, 2, 5, 16, 67, 374, 2825, 29212, 417199, 8283458, 229755605, 8933488744, 488176700923, 37558989808526, 4073773336877345, 623476476706836148, 134732283882873635911, 41128995468748254231002, 17741753171749626840952685, 10817161765507572862559462656

Offset: 0

N. J. A. Sloane

Also number of distinct binary linear codes of length n and any dimension.
Equivalently, number of subgroups of the Abelian group (C_2)^n.
Let V_n be an n-dimensional vector space over a field with 2 elements. Let P(V_n) be the collection of all subspaces of V_n. Then a(n-1) is the number of times any given nonzero vector of V_n appears in P(V_n). - Geoffrey Critzer, Jun 05 2017
With V_n and P(V_n) as above, a(n) is also the cardinality of P(V_n). - Vaia Patta, Jun 25 2019

			O.g.f.: A(x) = 1/(1-x) + x/((1-x)*(1-2x)) + x^2/((1-x)*(1-2x)*(1-4x)) + x^3/((1-x)*(1-2x)*(1-4x)*(1-8x)) + ...
Also generated by iterated binomial transforms in the following way:
[1,2,5,16,67,374,2825,29212,...] = BINOMIAL([1,1,2,6,26,158,1330,...]); see A135922;
[1,2,6,26,158,1330,15414,245578,...] = BINOMIAL([1,1,3,13,83,749,...]);
[1,3,13,83,749,9363,160877,...] = BINOMIAL^2([1,1,5,33,317,4361,...]);
[1,5,33,317,4361,82789,2148561,...] = BINOMIAL^4([1,1,9,97,1433,...]);
[1,9,97,1433,30545,902601,...] = BINOMIAL^8([1,1,17,321,7601,252833,...]);
etc.

J. Goldman and G.-C. Rota, The number of subspaces of a vector space, pp. 75-83 of W. T. Tutte, editor, Recent Progress in Combinatorics. Academic Press, NY, 1969.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration. Wiley, NY, 1983, p. 99.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 698.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351.

Alois P. Heinz, Table of n, a(n) for n = 0..100
Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
S. Hitzemann and W. Hochstattler, On the combinatorics of Galois numbers, Discr. Math. 310 (2010) 3551-3557, Galois Numbers G_{n}^(2).
Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow, arXiv:2012.13570 [math.CO], 2020.
Vjekoslav Kovač and Hrvoje Šikić, Characterizations of democratic systems of translates on locally compact abelian groups, arXiv:1709.01747 [math.FA], 2017.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
D. Slepian, A class of binary signaling alphabets, Bell System Tech. J. 35 (1956), 203-234.
D. Slepian, Some further theory of group codes, Bell System Tech. J. 39 1960 1219-1252.
M. Sved, Gaussians and binomials, Ars. Combinatoria, 17A (1984), 325-351. (Annotated scanned copy)
Index entries for sequences related to binary linear codes

Cf. A006516. Row sums of A022166.

Cf. A005329, A083906. - Paul D. Hanna, Nov 29 2008

I:=[1,2]; [n le 2 select I[n] else 2*Self(n-1)+(2^(n-2)-1)*Self(n-2): n in [1..20]]; // Vincenzo Librandi, Aug 12 2014

gf:= m-> add(x^n/mul(1-2^k*x, k=0..n), n=0..m):
a:= n-> coeff(series(gf(n), x, n+1), x, n):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 24 2012
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      2^m*b(n-1, m)+b(n-1, m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 08 2021

faq[n_, q_] = Product[(1-q^(1+k))/(1-q), {k, 0, n-1}]; qbin[n_, m_, q_] = faq[n, q]/(faq[m, q]*faq[n-m, q]); a[n_] := Sum[qbin[n, k, 2], {k, 0, n}]; a /@ Range[0, 19] (* Jean-François Alcover, Jul 21 2011 *)
Flatten[{1, RecurrenceTable[{a[n]==2*a[n-1]+(2^(n-1)-1)*a[n-2], a[0]==1, a[1]==2}, a, {n,1,15}]}] (* Vaclav Kotesovec, Aug 21 2013 *)
QP = QPochhammer; a[n_] := Sum[QP[2, 2, n]/(QP[2, 2, k]*QP[2, 2, n-k]), {k, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 23 2015 *)
Table[Sum[QBinomial[n, k, 2], {k, 0, n}], {n, 0, 19}] (* Ivan Neretin, Mar 28 2016 *)

a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-2^j*x+x*O(x^n))), n) \\ Paul D. Hanna, Dec 06 2007

a(n,q=2)=sum(k=0,n,prod(i=1,n-k,(q^(i+k)-1)/(q^i-1))) \\ Paul D. Hanna, Nov 29 2008

O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - 2^k*x). - Paul D. Hanna, Dec 06 2007
From Paul D. Hanna, Nov 29 2008: (Start)
Coefficients of the square of the q-exponential of x evaluated at q=2, where the q-exponential of x = Sum_{n>=0} x^n/F(n) and F(n) = Product{i=1..n} (q^i-1)/(q-1) is the q-factorial of n.
G.f.: (Sum_{k=0..n} x^n/F(n))^2 = Sum_{k=0..n} a(n)*x^n/F(n) where F(n) = A005329(n) = Product{i=1..n} (2^i - 1).
a(n) = Sum_{k=0..n} F(n)/(F(k)*F(n-k)) where F(n)=A005329(n) is the 2-factorial of n.
a(n) = Sum_{k=0..n} Product_{i=1..n-k} (2^(i+k) - 1)/(2^i - 1).
a(n) = Sum_{k=0..A033638(n)} A083906(n,k)*2^k. (End)
G.f.: 1 + x*(G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-2^k*x)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 16 2013
a(n) = 2*a(n-1) + (2^(n-1)-1)*a(n-2). [Hitzemann and Hochstattler]. - R. J. Mathar, Aug 21 2013
a(n) ~ c * 2^(n^2/4), where c = EllipticTheta[3,0,1/2] / QPochhammer[1/2,1/2] = 7.3719688014613... if n is even and c = EllipticTheta[2,0,1/2] / QPochhammer[1/2,1/2] = 7.3719494907662... if n is odd. - Vaclav Kotesovec, Aug 21 2013

A323841 Erroneous version of: Number of Stanley graphs on n nodes.

Original entry on oeis.org

1, 1, 2, 6, 158, 1330, 15414, 245578, 5382862

Offset: 0

N. J. A. Sloane, Feb 04 2019

dead

For precise definition see Knuth (1997).
It appears that there might be a missing number (26) in this data list. Only when the sequence is 1, 1, 2, 6, 26, 158, 1330, 15414, 245578, 5382862 does it then match with A323842 via exp(t)*EGF(A323842). - Michael D. Weiner, Sep 23 2019
For correct version of this sequence see A135922. - Alois P. Heinz, Sep 24 2019

D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]

Cf. A135922, A323842, A323843.

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

Original entry on oeis.org

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

A323842 Number of n-node Stanley graphs without isolated nodes.

Original entry on oeis.org

1, 0, 1, 2, 11, 72, 677, 8686, 152191, 3632916, 118317913, 5271781946, 322549557299, 27208234437984, 3177021912874253, 515436469519284358, 116581257420399219175, 36866447823471507563436, 16339685138335030408029889, 10170100145132835334268145362

Offset: 0

N. J. A. Sloane, Feb 04 2019

nonn

For precise definition see Knuth (1997).

Also, the number of naturally labeled posets on [n] with height at most two and no isolated elements. - David Bevan, Nov 17 2023

Alois P. Heinz, Table of n, a(n) for n = 0..115
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997. [Annotated scanned copy, with permission]

Cf. A135922, A323841, A323843, A323502, A356111.

b:= proc(n) option remember; add(mul(
      (2^(i+k)-1)/(2^i-1), i=1..n-k), k=0..n)
    end:
g:= proc(n) option remember;
      add(b(n-j)*binomial(n, j)*(-1)^j, j=0..n)
    end:
a:= proc(n) option remember;
      add(g(n-j)*binomial(n, j)*(-1)^j, j=0..n)
    end:
seq(a(n), n=0..21);  # Alois P. Heinz, Sep 24 2019

b[n_] := b[n] = Sum[Product[(2^(i+k) - 1)/(2^i - 1), {i, n-k}], {k, 0, n}];
g[n_] := g[n] = Sum[b[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];
a[n_] := a[n] = Sum[g[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];
a /@ Range[0, 21] (* Jean-François Alcover, May 24 2020, after Alois P. Heinz *)

P(n, k, x):=if k<0 or n<0 then 0 else if k=0 then 1 else x*P(n, k-1, x)+
2^k*P(n-1, k, (x+1)/2);
a(n):=sum(P(n-k, k, -1), k, 0, n);
makelist(a(n), n, 0, 10);
/* Vladimir Kruchinin, Mar 08 2020 */

a(n) = Sum_{j=0..n} (-1)^j * C(n,j) * A135922(n-j). - Alois P. Heinz, Sep 24 2019
a(n) = Sum_{k=0..n} P(n-k, k, -1), where  P(n, k, x) = x*P(n, k-1, x) + 2^k*P(n-1, k, (x+1)/2). - Vladimir Kruchinin, Mar 09 2020
G.f.: g(1,0), where g(u,v) = 1 + x*((v-1)*g(u,v) + g(2*u,u+v)). - David Bevan, Jul 28 2022
G.f.: 1/(1+z) * Sum_{k>=0} (z^k / Prod_{i=2..k} (1 - (2^i-2)*z)). - David Bevan, Nov 17 2023; simplified on Jul 25 2024

More terms from Alois P. Heinz, Sep 24 2019

A323843 Number of n-node connected Stanley graphs.

Original entry on oeis.org

0, 1, 1, 2, 8, 52, 502, 6824, 127166, 3205924, 108975934, 5006366048, 312601245662, 26708244267148, 3142852107059758, 512229404374936616, 116165284523764481294, 36791597841822774872116, 16320947226945992981680606, 10163558457757761048966068912

Offset: 0

N. J. A. Sloane, Feb 04 2019

nonn

For precise definition see Knuth (1997).

Alois P. Heinz, Table of n, a(n) for n = 0..155
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997. [Annotated scanned copy, with permission]

Cf. A135922, A323841, A323842.

b:= proc(n) option remember; add(mul(
      (2^(i+k)-1)/(2^i-1), i=1..n-k), k=0..n)
    end:
p:= proc(n) option remember;
      add(b(n-j)*binomial(n, j)*(-1)^j, j=0..n)
    end:
a:= proc(n) option remember; `if`(n=0, 0, p(n)-add(
      binomial(n, j)*p(n-j)*a(j)*j, j=1..n-1)/n)
    end:
seq(a(n), n=0..21);  # Alois P. Heinz, Sep 24 2019

b[n_] := b[n] = Sum[Product[(2^(i+k) - 1)/(2^i - 1), {i, n-k}], {k, 0, n}];
p[n_] := p[n] = Sum[b[n-j] Binomial[n, j] (-1)^j, {j, 0, n}];
a[n_] := a[n] = If[n == 0, 0, p[n] - Sum[Binomial[n, j] p[n-j] a[j] j, {j, n-1}]/n];
a /@ Range[0, 21] (* Jean-François Alcover, May 24 2020, after Alois P. Heinz *)

More terms from Alois P. Heinz, Sep 24 2019

A113226 Number of permutations of [n] avoiding the pattern 12-34.

Original entry on oeis.org

1, 1, 2, 6, 23, 107, 585, 3669, 25932, 203768, 1761109, 16595757, 169287873, 1857903529, 21823488238, 273130320026, 3627845694283, 50962676849199, 754814462534449, 11754778469338581, 191998054346198680

Offset: 0

David Callan, Oct 19 2005

nonn

a(n) is the number of permutations on [n] that avoid the vincular pattern 12-34 (also the number that avoid 43-21).
a(n) is also the number of permutations on [n] that avoid the vincular pattern 12-43 (or 21-34 or 34-21 or 43-12) or 21-43 (or 34-12). - David Bevan, Nov 15 2023
a(n) is also the number of {3,2+2}-free naturally labeled posets. - David Bevan, Nov 15 2023

			523146 contains 2346 as a 12-34 pattern because the 23 and 46 are adjacent in the permutation and the reduced form of 2346 is 1234.

David Bevan, Table of n, a(n) for n = 0..471
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Cf. A135922 (3-free naturally labeled posets).

Clear[u, v, w]; w[0] = w[1] = 1; w[n_] /; n >= 2 := w[n] = u[n] + v[n];
v[n_] /; n >= 2 := v[n] = Sum[v[n, a], {a, 2, n}]; v[1, 1] = 1;
v[n_, a_] /; 2 <= a <= n :=
v[n, a] = Sum[u[n - 1, b], {b, a - 1}] + Sum[v[n - 1, b], {b, 2, a - 1}];
u[1] = 1; u[n_] /; n >= 2 := u[n] = Sum[u[n, a], {a, n - 1}]; u[1, 1] = 1;
u[n_, a_] /; a == n := 0; u[n_, a_] /; 1 <= a < n := u[n, a, n];
u[1, 1, k_] := 1; u[2, 1, k_] := 1; u[n_, a_, k_] /; a >= n := 0;
u[n_, a_, k_] /; 1 <= a < n && n >= 3 :=
u[n, a, k] = Sum[u[n, a, k, b], {b, a + 1, n}];
u[n_, a_, k_, b_] /; 1 <= a < b <= n && k >= b + 2 := u[n, a, b + 1, b];
u[n_, a_, k_, b_] /; 1 <= a < n && b == n && k == n + 1 := u[n, a, n, n];
u[n_, a_, k_, b_] /; 1 == a < b == n && k == 2 := 1;
u[n_, a_, k_, b_] /; 1 <= a < b <= n && k <= b :=
u[n, a, k, b] =
  Sum[Binomial[b - k - If[k <= a, 1, 0], j1] Binomial[
     k - 1 - If[a < k, 1, 0] - c, j2]*
    u[n - 2 - j1 - j2, c, k - If[a < k, 1, 0] - j2], {c,
    k - 1 - If[a < k, 1, 0]}, {j1, 0, b - k - If[k <= a, 1, 0]}, {j2, 0,
    k - 1 - If[a < k, 1, 0] - c}];
u[n_, a_, k_, b_] /; 1 <= a < b < n && k == b + 1 && {a, b} == {1, 2} := 1;
u[n_, a_, k_, b_] /; 1 <= a < b < n && k == b + 1 && {a, b} != {1, 2} :=
u[n, a, k, b] =
  Sum[Binomial[n - b, i] Binomial[b - 2 - c, j] u[n - 2 - i - j, c,
     b - 1 - j], {c, b - 2}, {i, 0, n - b}, {j, 0, b - 2 - c}]; Table[
w[n], {n, 0, 15}]

In the recurrence coded in Mathematica below, w[n] = # (12-34)-avoiding permutations on [n]; v[n, a] is the number that start with a descent and have first entry a; u[n, a, k, b] is the number that start with an ascent and that have (i) first entry a, (ii) other than a, all ascent initiators

A356111 The number of 1+1+1-free ordered posets of [n].

Original entry on oeis.org

1, 1, 2, 6, 23, 102, 497, 2586, 14127, 80146, 468688, 2810163, 17206549, 107261051, 679096359, 4358360362, 28309516828, 185862601727, 1232042778231, 8238155634738, 55521191613041, 376888928783870, 2575334987109807, 17704834935517727, 122401523831513816

Offset: 0

David Bevan, Jul 27 2022

nonn

A partial order R on [n] is ordered if xRy implies x < y; i.e., the natural order (<) is a linear extension of R. 1+1+1-free posets are those with width (longest antichain) at most 2.

			The six 1+1+1-free ordered posets of [3] are those with covering relations {(1,2)}, {(1,3)}, {(2,3)}, {(1,2), (1,3)}, {(1,2), (2,3)} and {(1,3), (2,3)}.

See A006455 for the number of all ordered posets on [n], and A135922 for the number of ordered posets on [n] with height at most two.

Cf. A001181.

Conjectured g.f.: 2 - 2*x/(B(x)-1+x), where B(x) is the o.g.f. for A001181. - Michael D. Weiner, Oct 04 2024

A228365 Inverse binomial transform of the Galois numbers G_(n)^{(3)} (A006117).

Original entry on oeis.org

1, 1, 3, 15, 129, 1833, 43347, 1705623, 112931553, 12639552945, 2413134909507, 788041911546303, 442817851480763169, 428369525248261655193, 716160018275094098267859, 2067365673240491189928496263, 10333740296321620864171488891201, 89302459853776656431139970491341025

Offset: 0

R. J. Mathar, Aug 21 2013

nonn

Analog of the inverse binomial transform of G_(n)^{(q)} with q=2, A135922.

A 2-multigraph is a labeled graph with no loops but with up to 2 edges joining any pair of vertices. a(n) is the number of 2-multigraphs on [n] such that no path of length two has vertices i,j,k (in that order) with iGeoffrey Critzer, May 05 2025

Alois P. Heinz, Table of n, a(n) for n = 0..91
R. P. Stanley and S. C. Locke, Graphs without increasing paths: Solution to Problem 10572, The American Mathematical Monthly, 106(2) (1999), 168.

Cf. A135922, A006117, A006116.

b:= proc(n) option remember; add(mul(
      (3^(i+k)-1)/(3^i-1), i=1..n-k), k=0..n)
    end:
a:= proc(n) option remember;
      add(b(n-j)*binomial(n, j)*(-1)^j, j=0..n)
    end:
seq(a(n), n=0..19);  # Alois P. Heinz, Sep 24 2019

Table[SeriesCoefficient[Sum[x^n/Product[(1-(3^k-1)*x),{k,0,n}],{n,0,nn}],{x,0,nn}] ,{nn,0,20}] (* Vaclav Kotesovec, Aug 23 2013 *)

a(n) ~ c * 3^(n^2/4), where c = EllipticTheta[3,0,1/3]/QPochhammer[1/3,1/3] = 3.019783845699... if n is even and c = EllipticTheta[2,0,1/3]/QPochhammer[1/3,1/3] = 3.01826904637117... if n is odd. - Vaclav Kotesovec, Aug 23 2013

A329154 Coefficients of polynomials related to the sum of Gaussian binomial coefficients for q = 2. Triangle read by rows, T(n,k) for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 6, 6, 3, 1, 26, 24, 12, 4, 1, 158, 130, 60, 20, 5, 1, 1330, 948, 390, 120, 30, 6, 1, 15414, 9310, 3318, 910, 210, 42, 7, 1, 245578, 123312, 37240, 8848, 1820, 336, 56, 8, 1, 5382862, 2210202, 554904, 111720, 19908, 3276, 504, 72, 9, 1

Offset: 0

Vladimir Kruchinin and Peter Luschny, Mar 08 2020

T(n,k) is the number of n X n matrices over F_2 in reduced row echelon form having exactly k zero-columns. Equivalently, T(n,k) is the number of subspaces of F_2^n that "involve" n-k coordinates. (For the definition of "involve" see the link below: D. E. Knuth, Letter to Daniel Ullman and others). - Geoffrey Critzer, May 03 2025

			Triangle starts:
[0] [1]
[1] [1,       1]
[2] [2,       2,       1]
[3] [6,       6,       3,      1]
[4] [26,      24,      12,     4,      1]
[5] [158,     130,     60,     20,     5,     1]
[6] [1330,    948,     390,    120,    30,    6,    1]
[7] [15414,   9310,    3318,   910,    210,   42,   7,   1]
[8] [245578,  123312,  37240,  8848,   1820,  336,  56,  8,  1]
[9] [5382862, 2210202, 554904, 111720, 19908, 3276, 504, 72, 9, 1]

D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]
R. P. Stanley and S. C. Locke, Graphs without increasing paths: Solution to Problem 10572, The American Mathematical Monthly, 106(2) (1999), 168.

Row sums: A006116, first column: A135922.

Cf. A022166, A323842, A323843.

T := (n, k) -> local j, m; pochhammer(n - k + 1, k)*add((-1)^j*add(product((2^(i + m) - 1)/(2^i - 1), i = 1..n-k-m-j), m = 0..n-k-j)*binomial(n - k, j), j = 0..n-k) / k!: for n from 0 to 9 do seq(T(n,k), k=0..n) od;  # Peter Luschny, Oct 08 2023

T[n_,k_]:= (Pochhammer[n-k+1,k]/(k!)*Sum[(-1)^j*Sum[Product[(2^(i+m)-1)/(2^i-1),{i,1,n-k-m-j}],{m,0,n-k-j}]*Binomial[n-k,j],{j,0,n-k}]); Flatten[Table[T[n,k],{n,0,9},{k,0,n}]] (* Detlef Meya, Oct 07 2023 *)

R = PolynomialRing(QQ, 'x')
x = R.gen()
@cached_function
def P(n, k, x):
    if k < 0 or n < 0: return R(0)
    if k == 0: return R(1)
    return x*P(n, k-1, x) + 2^k*P(n-1, k, (x+1)/2)
def row(n): return sum(P(n-k, k, x) for k in range(n+1)).coefficients()
print(flatten([row(n) for n in range(10)]))

Let P(n, k, x) = x*P(n, k-1, x) + 2^k*P(n-1, k, (x+1)/2) and Q(n, x) = Sum_{k=0..n} P(n-k, k, x) then T(n, k) = [x^k] Q(n, x).
T(n, k) = (1/k!) * Pochhammer(n-k+1, k) * Sum_{j=0..n-k}((-1)^j*Sum_{m=0..n-k-j} (Product_{i=1..n-k-m-j} ((2^(i+m)-1)/(2^i-1))) * binomial(n-k, j)). - Detlef Meya, Oct 07 2023
T(n,k) = binomial(n,k)*A135922(n-k). (see Stanley-Locke link above) - Geoffrey Critzer, May 03 2025
E.g.f.: exp(y x)*f(x) where f(x) is the e.g.f. for A135922. - Geoffrey Critzer, May 03 2025

A383655 Triangle read by rows: T(n,k) is the number of n-node Stanley graphs containing exactly k isolated points, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 11, 8, 6, 0, 1, 72, 55, 20, 10, 0, 1, 677, 432, 165, 40, 15, 0, 1, 8686, 4739, 1512, 385, 70, 21, 0, 1, 152191, 69488, 18956, 4032, 770, 112, 28, 0, 1, 3632916, 1369719, 312696, 56868, 9072, 1386, 168, 36, 0, 1, 118317913, 36329160, 6848595, 1042320, 142170, 18144, 2310, 240, 45, 0, 1

Offset: 0

Geoffrey Critzer, May 04 2025

For precise definition see the links: David Bevan and others (2023) or D.E. Knuth (1997).

			Triangle T(n,k) begins:
   1;
   0,  1;
   1,  0,  1;
   2,  3,  0,  1;
  11,  8,  6,  0, 1;
  72, 55, 20, 10, 0, 1;
  ...

David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission].

Cf. A323842 (column k=0), A135922 (row sums).

nn = 10; g[x_] :=Total[Table[Sum[QBinomial[n, k, 2] x^n/n!, {k, 0, n}], {n, 0, nn}]]; Table[(Range[0, nn]! CoefficientList[Series[Exp[y x] Exp[-x] g[x] Exp[-x], {x, 0, nn}], {x, y}])[[i, 1 ;; i]], {i, 1, nn + 1}] // Grid

E.g.f.: exp((y-1)*x)*f(x) where f(x) is the e.g.f. for A135922.

Showing 1-10 of 11 results. Next

cp's OEIS Frontend

A006116 Sum of Gaussian binomial coefficients [n,k] for q=2 and k=0..n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A323841 Erroneous version of: Number of Stanley graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A323842 Number of n-node Stanley graphs without isolated nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

Extensions

A323843 Number of n-node connected Stanley graphs.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A113226 Number of permutations of [n] avoiding the pattern 12-34.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A356111 The number of 1+1+1-free ordered posets of [n].

Views

Author

Keywords

Comments

Examples