A005321 Upper triangular n X n (0,1)-matrices with no zero rows or columns.

1, 1, 2, 10, 122, 3346, 196082, 23869210, 5939193962, 2992674197026, 3037348468846562, 6189980791404487210, 25285903982959247885402, 206838285372171652078912306, 3386147595754801373061066905042, 110909859519858523995273393471390010

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..80
• E. Andresen and K. Kjeldsen, On certain subgraphs of a complete transitively directed graph, Discrete Math. 14 (1976), no. 2, 103-119.
• William T. Dugan, On the f-vectors of flow polytopes for the complete graph, Sém. Lotharingien Comb., Proc. 36th Conf. Formal Power Series Alg. Comb. (2024) Vol. 91B, Art. No. 101. See p. 3.
• T. Lockman Greenough, Representation and enumeration of interval orders and semiorders, Ph.D. Thesis, Dartmouth, 1976.
• T. L. Greenough, Enumeration of interval orders without duplicated holdings, Preprint, circa 1976. [Annotated scanned copy]
• T. Lockman Greenough, Enumeration of interval orders without duplicated holdings, in Notices of the AMS, February 1976, page A-314.
• T. L. Greenough and K. P. Bogart, The Representation and Enumeration of Interval Orders, 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.
• Vít Jelínek, Counting Self-Dual Interval Orders, arXiv:1106.2261 [math.CO], 2011. See Corollary 2.4.
• Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614. See Corollary 2.4.
• J. Longyear, T. Trotter, N. J. A. Sloane, Correspondence
• Index entries for sequences related to binary matrices

Crossrefs

Cf. A022493, A138265, A289314, A289315.

Column sums of A137252.

Programs

Mathematica

max = 14; f[x_] := Sum[ x^n*Product[ (2^i-1) / (1+(2^i-1)*x), {i, 1, n}], {n, 0, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Nov 23 2011, after Vladeta Jovovic *)

PARI

a(n) = 1 + sum(k=2, n, binomial(n,k)*sum(i=2, k, (-1)^i*prod(j=i+1, k, 2^j - 1))); \\ Michel Marcus, Oct 13 2019

Formula

a(n) = Sum_{k=0..n} binomial(n,k)*A005327(k+1).

G.f.: Sum_{n >= 0} x^n*Product_{i = 1..n} ((2^i-1)/(1 + (2^i-1)*x)). - Vladeta Jovovic, Mar 10 2008

From Peter Bala, Jul 06 2017: (Start)

Two conjectural continued fractions for the o.g.f.:

1/(1 - x/(1 - x/(1 - 6*x/(1 - 9*x/(1 - 28*x/(1 - 49*x/(1 - ... - 2^(n-1)*(2^n - 1)*x/(1 - (2^n - 1)^2*x/(1 - ...)))))))));

1 + x/(1 - 2*x/(1 - 3*x/(1 - 12*x/(1 - 21*x/(1 - ... - 2^n*(2^n - 1)*x/(1 - (2^(n+1) - 1)*(2^n - 1)*x/(1 - ...))))))). Cf. A289314 and A289315. (End)

a(n) = (-1)^n*Sum_{k=0..n} qS2(n,k)*[k]!*(-1)^k, where qS2(n,k) is the triangle A139382, and [k]! is q-factorial, q=2. - Vladimir Kruchinin, Oct 10 2019

a(n) = 1 + Sum_{k=2..n} binomial(n,k)*Sum{i=2..k} (-1)^i*Product_{j=i+1..k} (2^j - 1). See Greenough. - Michel Marcus, Oct 13 2019

Extensions

More terms from Max Alekseyev, Apr 27 2010