A323842 -id:A323842 - cp's OEIS frontend

A135922 Inverse binomial transform of A006116, which is the sum of Gaussian binomial coefficients [n,k] for q=2.

1, 1, 2, 6, 26, 158, 1330, 15414, 245578, 5382862, 162700898, 6801417318, 394502066810, 31849226170622, 3589334331706258, 566102993389615254, 125225331231990004138, 38920655753545108286254, 17021548688670112527781058, 10486973328106497739526535366

Offset: 0

Paul D. Hanna, Dec 06 2007

nonn

Let B = {v_1,v_2,...,v_n} be a basis for F_2^n.  a(n) is the number of subspaces of F_2^n that do not contain any of the vectors in B.  Moreover, for 1<=k<=n, let S be a size k subset of B. a(k) is the number of subspaces of F_2^n that do not contain any of the vectors in S but do contain all the vectors in B - S. - Geoffrey Critzer, May 03 2025
Also number of Stanley graphs on n nodes. For precise definition see Knuth (1997). - Alois P. Heinz, Sep 24 2019
Also the number of naturally labeled posets on [n] with height at most two. - David Bevan, Jul 28 2022; Nov 16 2023
Also the number of sign mappings X:([n] choose 2) -> {+,-} such that for any ordered 3-tuple aManfred Scheucher, Jan 05 2024

			O.g.f.: A(x) = 1 + x/(1-x) + x^2/((1-x)*(1-3x)) + x^3/((1-x)*(1-3x)*(1-7x)) + x^4/((1-x)*(1-3x)*(1-7x)*(1-15x)) + ...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 318.

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.
Lucas Gagnon, The combinatorics of normal subgroups in the unipotent upper triangular group, arXiv:2012.00108 [math.CO], 2020.
D. E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997 [Annotated scanned copy, with permission]
Zvi Rosen and Yan X. Zhang, Convex Neural Codes in Dimension 1, arXiv:1702.06907 [math.CO], 2017. Mentions this sequence.
R. P. Stanley, Problem 10572, The American Mathematical Monthly, 104(2) (1997), 168.
R. P. Stanley and S. C. Locke, Graphs without increasing paths: Solution to Problem 10572, The American Mathematical Monthly, 106(2) (1999), 168.

Cf. A006116, A323841, A323842, A323843, A139382, A006455, A356111.

b:= proc(n) option remember; add(mul(
      (2^(i+k)-1)/(2^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-(2^k-1)*x),{k,0,n}],{n,0,nn}],{x,0,nn}] ,{nn,0,20}] (* Vaclav Kotesovec, Aug 23 2013 *)
b[n_] := b[n] = Sum[Product[(2^(i+k)-1)/(2^i-1), {i, 1, n-k}], {k, 0, n}];
a[n_] := a[n] = Sum[(-1)^j b[n-j] Binomial[n, j], {j, 0, n}];
a /@ Range[0, 19] (* Jean-François Alcover, Mar 10 2020, after Alois P. Heinz *)

a(n)=polcoeff(sum(k=0, n, x^k/prod(j=0, k, 1-(2^j-1)*x+x*O(x^n))), n)

# After Vladimir Kruchinin.
def a(n):
    @cached_function
    def T(n, k):
        if k == 1 or k == n: return 1
        return (2^k-1)*T(n-1, k) + T(n-1, k-1)
    return sum(T(n, k) for k in (1..n)) if n > 0 else 1
print([a(n) for n in (0..19)]) # Peter Luschny, Feb 26 2020

O.g.f.: A(x) = Sum_{n>=0} x^n / Product_{k=0..n} (1 - (2^k-1)*x).
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-x*(2^k-1))/(1-x/(x-1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jan 16 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 23 2013
a(n) = Sum_{k=0..n} qStirling2(n,k), where qStirling2 is the triangle A139382. - Vladimir Kruchinin, Feb 26 2020
G.f.: f(1), where f(y) = 1 + x*((y-1)*f(y) + f(2*y)). - David Bevan, Jul 28 2022
E.g.f.:  exp(-x)*g(x) where g(x) is the e.g.f. for A006116. (given in D. E. Knuth link) - Geoffrey Critzer, May 03 2025

References for Stanley graphs added by David Bevan, Jul 24 2024

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.

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

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.

cp's OEIS Frontend

A135922 Inverse binomial transform of A006116, which is the sum of Gaussian binomial coefficients [n,k] for q=2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

A323843 Number of n-node connected Stanley graphs.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula