A006455 -id:A006455 - 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

A323502 Number of irreducible or connected partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x < y).

Original entry on oeis.org

1, 1, 1, 3, 18, 181, 2792, 62960, 2020256, 90847421, 5674075324, 489320844468, 57995151443168

Offset: 0

M. Farrokhi D. G., Jan 16 2019

a(n) is also the number of connected ordered bipartite Cohen-Macaulay graphs with 2n vertices.

			For n = 4 the a(4) = 18 solutions are given below. The partial order is assumed to be strict; for the non-strict case, the elements (1,1), (2,2), (3,3), (4,4) should be added to each list.
P1 = {(1,3), (2,3), (2,4)},
P2 = {(1,4), (2,4), (3,4)},
P3 = {(1,4), (2,3), (2,4)},
P4 = {(1,4), (2,3), (2,4), (3,4)},
P5 = {(1,2), (1,4), (3,4)},
P6 = {(1,2), (1,4), (2,4), (3,4)},
P7 = {(1,3), (1,4), (2,3)},
P8 = {(1,3), (1,4), (2,4)},
P9 = {(1,3), (1,4), (2,4), (3,4)},
P10 = {(1,3), (1,4), (2,3), (2,4)},
P11 = {(1,3), (1,4), (2,3), (2,4), (3,4)},
P12 = {(1,2), (1,3), (1,4)},
P13 = {(1,2), (1,3), (1,4), (3,4)},
P14 = {(1,2), (1,3), (1,4), (2,3)},
P15 = {(1,2), (1,3), (1,4), (2,4)},
P16 = {(1,2), (1,3), (1,4), (2,4), (3,4)},
P17 = {(1,2), (1,3), (1,4), (2,3), (2,4)},
P18 = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}.

M. Estrada and R. H. Villarreal, Cohen-Macaulay bipartite graphs, Arch. Math. (Basel) 68(2) (1997), 124-128.
J. Herzog and T. Hibi, Distributive lattices, bipartite graphs and Alexander duality, J. Algebraic Combin. 22(3) (2005), 289-302.
M. Mahmoudi and A. Mousivand, An alternative proof of a characterization of Cohen-Macaulay bipartite graphs, Abh. Math. Semin. Univ. Hambg. 80(1) (2010), 145-148.
R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66(3) (1990), 277-293.
R. H. Villarreal, Unmixed bipartite graphs, arXiv:math/0606479 [math.CO], 2006-2007; Rev. Colomb. Mat. 41(2) (2007), 393-395.
R. Zaare-Nahandi, Cohen-Macaulayness of bipartite graphs, revisited, Bull. Malays. Math. Sci. Soc. 38(4) (2015), 1601-1607.

Cf. A006455, A323658.

A006455 := [1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684];
a := function(n)
local b,i;
b:= [];
b[1] := 1;
for i in [2..n] do
    b[i] :=0;
    b[i] := A006455[i] - Sum(List(Partitions(i), P -> Factorial(i)/(Product(List(P, Factorial)) * Product(List(Collected(P), x -> Factorial(x[2])))) * Product(List(P), x -> b[x])));
od;
return b[n];
end;

A124777 Number of naturally labeled partially ordered sets associated with compositions in standard order.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 1, 11, 13, 8, 1, 4, 1, 1

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

The k-th term of the composition is the number of objects with rank k. The rank of an object is one more than the maximum rank of any smaller object in the ordering (1 for a minimal element), or equivalently the size of the largest chain of which the object is the maximal element.

			Composition number 11 is 2,1,1; there are 3 partial orders
associated with this (shown below); these can be naturally labeled
respectively in 1, 4 and 3 ways, so a(11) = 1+4+3 = 8.
..O..*O..*..O
..|..*|..*./|
..O..*O..*O.|
./.\.*|..*|.|
O...O*O.O*O.O
The table starts:
1
1
1 1
1 4 1 1

Cf. A066099, A124775, A124776, A011782 (row lengths), A006455 (row sums).

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

A213430 The number of n X n upper triangular (0,1)-matrices M with all diagonal entries 1 such that M = f(M^2) and sum(row 1) >= sum(row 2) >= ... >= sum(row n-1) >= sum(row n) = 1 and f maps any nonzero entry to 1.

Original entry on oeis.org

1, 2, 6, 26, 159, 1347, 15593, 244173, 5131436

Offset: 1

N. J. A. Sloane, Jun 11 2012

A006455 is equivalent to this sequence without the nonincreasing condition on the row sums. - Petros Hadjicostas, Jul 20 2024

Collected papers of Professor Hansraj Gupta. Edited by R. J. Hans-Gill and Madhu Raka. Ramanujan Mathematical Society Collected Works Series, 3. See pp. 554-564.
Hansraj Gupta, Number of topologies in a finite set, Research Bulletin of the Panjab University, Vol. 19 (1968), p. 240. MR0268836.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Hansraj Gupta, Number of topologies in a finite set, Research Bulletin of the Panjab University, Vol. 19 (1968), p. 240. MR0268836.
Sean A. Irvine, Java program
Wikipedia, Finite topological space.
zbMATH, Review of Gupta article.

Cf. A000798, A001035, A006455.

a(7) and new name from Petros Hadjicostas, Jul 20 2024

a(8)-a(9) from Sean A. Irvine, Jul 20 2024

A323658 Number of bipartite graphs associated with connected transitive oriented graphs.

Original entry on oeis.org

1, 1, 1, 2, 7, 25, 133, 854

Offset: 0

M. Farrokhi D. G., Jan 23 2019

Also the number of unlabeled connected Cohen-Macaulay bipartite graphs up to graph isomorphism.

If G is an oriented graph with vertex set {1,...,n}, then the associated bipartite graph is a bipartite graph B(G) with parts {a1,...,an} and {b1,...,bn} such that ai ~ bj if (i,j) is an edge in G.

			Example: For n = 4 the a(4) = 7 solutions are given by the edge sets
E1 = {(1,5), (1,7), (2,6), (2,7), (2,8), (3,7), (4,8)},
E2 = {(1,5), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},
E3 = {(1,5), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},
E4 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (4,8)},
E5 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},
E6 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},
E7 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)}.

M. Estrada and R. H. Villarreal, Cohen-Macaulay bipartite graphs, Arch. Math. (Basel) 68(2) (1997), 124-128.
J. Herzog and T. Hibi, Distributive lattices, bipartite graphs and Alexander duality, J. Algebraic Combin. 22(3) (2005), 289-302.
M. Mahmoudi and A. Mousivand, An alternative proof of a characterization of Cohen-Macaulay bipartite graphs, Abh. Math. Semin. Univ. Hambg. 80(1) (2010), 145-148.
R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66(3) (1990), 277-293.
R. H. Villarreal, Unmixed bipartite graphs, Rev. Colomb. Mat. 41(2) (2007), 393-395.
R. Zaare-Nahandi, Cohen-Macaulayness of bipartite graphs, revisited, Bull. Malays. Math. Sci. Soc. 38(4) (2015), 1601-1607.

Cf. A006455, A323502.

A336525 Total number of linear extensions of all n-element posets.

Original entry on oeis.org

1, 1, 3, 14, 96, 895, 11751, 214708, 5594463

Offset: 0

Richard Stanley, Jul 27 2020

Sum of e(P) over all nonisomorphic n-element posets, where e(P) is the number of linear extensions of P.

			There is one 3-element poset with 6 linear extensions, one with 3, two with 2, and one with 1, for a total of 14.

Cf. A006251, A080687, A248091, A301871, A336229, A006455.

A367494 Number of (2+2)-free naturally labeled posets on [n].

Original entry on oeis.org

1, 1, 2, 7, 37, 272, 2637, 32469, 493602, 9062503, 197409097, 5027822588, 147896295785, 4972353491993, 189357434418082, 8104194176872583, 387121098095180237, 20513320778472547576, 1199236185075846230469, 76970026071431034905229, 5399593095642890354948802

Offset: 0

David Bevan, Nov 20 2023

nonn

A partial order R is naturally labeled if xRy => x

A partial order is (2+2)-free if it does not contain an induced subposet that is isomorphic to the union of two disjoint 2-element chains.

			a(3) = A006455(3) = 7: {}, {1R2}, {1R3}, {2R3}, {1R2, 1R3}, {1R3, 2R3}, {1R2, 1R3, 2R3}.
a(4) = A006455(4) - 3 = 37: {1R2, 3R4}, {1R3, 2R4} and {1R4, 2R3} (trivially) contain a 2+2 subposet.

David Bevan, Gi-Sang Cheon, and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.

Cf. A006455 (naturally labeled posets), A113226 ({3,2+2}-free naturally labeled posets).

A383370 Number of partial orders on {1,2,...,n} that are contained in the usual linear order, whose dual is given by the relabelling k -> n+1-k.

Original entry on oeis.org

1, 1, 2, 3, 12, 25, 172, 482, 5318, 19675, 333768, 1609846, 40832554, 254370640, 9459449890, 75546875426, 4061670272088

Offset: 0

Ludovic Schwob, Apr 24 2025

a(n) is the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2, which are symmetric about the antidiagonal. These matrices can be seen as closed sets of inversions (pairs (i,j) with 1 <= i < j <= n). A set of inversions E is closed if for all i < j < k, if E contains (i,j) and (j,k) then it contains (i,k).

			The Boolean matrices corresponding to a(4) = 12:
  1 0 0 0    1 0 0 1    1 0 0 0    1 0 0 1
  0 1 0 0    0 1 0 0    0 1 1 0    0 1 1 0
  0 0 1 0    0 0 1 0    0 0 1 0    0 0 1 0
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
.
  1 0 1 0    1 0 1 1    1 0 1 0    1 0 1 1
  0 1 0 1    0 1 0 1    0 1 1 1    0 1 1 1
  0 0 1 0    0 0 1 0    0 0 1 0    0 0 1 0
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
.
  1 1 0 0    1 1 0 1    1 1 1 1    1 1 1 1
  0 1 0 0    0 1 0 0    0 1 0 1    0 1 1 1
  0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1

Cf. A006455, A037223.

def a(n):
    S = set()
    for P in Posets(n):
        if P.is_isomorphic(P.dual()):
            for l in P.linear_extensions():
                t = tuple(tuple(int(P.is_lequal(l[j],l[i])) for j in range(i)) for i in range(1,len(l)))
                if all(t[j][i]==t[n-i-2][n-j-2] for i in range((n-1)//2) for j in range(i,n-i-2)):
                    S.add(t)
    return len(S)

a(10)-a(16) from Christian Sievers, May 02 2025

Showing 1-9 of 9 results.

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

A323502 Number of irreducible or connected partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x < y).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

A124777 Number of naturally labeled partially ordered sets associated with compositions in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A213430 The number of n X n upper triangular (0,1)-matrices M with all diagonal entries 1 such that M = f(M^2) and sum(row 1) >= sum(row 2) >= ... >= sum(row n-1) >= sum(row n) = 1 and f maps any nonzero entry to 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A323658 Number of bipartite graphs associated with connected transitive oriented graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A336525 Total number of linear extensions of all n-element posets.

Views

Author

Keywords

Comments

Examples

Crossrefs

A367494 Number of (2+2)-free naturally labeled posets on [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A383370 Number of partial orders on {1,2,...,n} that are contained in the usual linear order, whose dual is given by the relabelling k -> n+1-k.

Views

Author

Keywords

Comments

Examples