A005327 Certain subgraphs of a directed graph (inverse binomial transform of A005321).

1, 0, 1, 6, 91, 2820, 177661, 22562946, 5753551231, 2940064679040, 3007686166657921, 6156733583148764286, 25211824022994189751171, 206510050572345408251841660, 3383254158526734823389921915781

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

q-Subfactorial for q=2. - Vladimir Reshetnikov, Sep 12 2016

References

• T. L. Greenough, Enumeration of interval orders without duplicated holdings, Preprint, circa 1976.
• T. L. Greenough and T. Lockman, Representation and enumeration of interval orders and semiorders, Ph.D. Thesis, Dartmouth, 1976.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• G. C. Greubel, Table of n, a(n) for n = 1..50
• E. Andresen and K. Kjeldsen, On certain subgraphs of a complete transitively directed graph, Discrete Math. 14 (1976), no. 2, 103-119.
• T. L. Greenough, Enumeration of interval orders without duplicated holdings, Preprint, circa 1976. [Annotated scanned copy]
• 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.
• N. J. A. Sloane, Transforms
• Eric Weisstein's World of Mathematics, Subfactorial, q-Factorial, q-Analog.

Crossrefs

Cf. A002820, A005329, A005321.

Programs

Maple

p:=proc(n) if n=0 then 1 else product(2^i-1,i=1..n) fi end: a:=n->p(n-1)*sum((-1)^j/p(j),j=0..n-1): seq(a(n),n=1..17); # Emeric Deutsch, Jan 23 2005

Mathematica

a[1] = 1; a[n_] := a[n] = (2^(n-1)-1)*a[n-1] + (-1)^(n-1); Array[a, 15] (* Jean-François Alcover, Apr 05 2016, after Max Alekseyev *)
With[{q = 2}, Table[QFactorial[n, q] Sum[(-1)^k/QFactorial[k, q], {k, 0, n}], {n, 0, 20}]] (* Vladimir Reshetnikov, Sep 12 2016 *)

Formula

For n>1, a(n) = (2^(n-1)-1)*a(n-1) + (-1)^(n-1). - Max Alekseyev, Feb 23 2012

a(n) = p(n-1)*sum((-1)^j/p(j), j=0..n-1), where p(0) = 1, p(k) = product(2^i-1, i=1..k) for k>0. - Emeric Deutsch, Jan 23 2005

a(n) ~ A048651^2 * 2^(n*(n-1)/2). - Vaclav Kotesovec, Oct 09 2019

Extensions

More terms from Max Alekseyev, Apr 27 2010