login
Upper triangular n X n (0,1)-matrices with no zero rows or columns.
(Formerly M1986)
17

%I M1986 #92 Jul 30 2024 09:44:56

%S 1,1,2,10,122,3346,196082,23869210,5939193962,2992674197026,

%T 3037348468846562,6189980791404487210,25285903982959247885402,

%U 206838285372171652078912306,3386147595754801373061066905042,110909859519858523995273393471390010

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

%D T. L. Greenough, Enumeration of interval orders without duplicated holdings, Preprint, circa 1976.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A005321/b005321.txt">Table of n, a(n) for n = 0..80</a>

%H E. Andresen and K. Kjeldsen, <a href="http://dx.doi.org/10.1016/0012-365X(76)90054-6">On certain subgraphs of a complete transitively directed graph</a>, Discrete Math. 14 (1976), no. 2, 103-119.

%H William T. Dugan, <a href="https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2024/101.pdf">On the f-vectors of flow polytopes for the complete graph</a>, Sém. Lotharingien Comb., Proc. 36th Conf. Formal Power Series Alg. Comb. (2024) Vol. 91B, Art. No. 101. See p. 3.

%H T. Lockman Greenough, <a href="http://libarchive.dartmouth.edu/cdm/ref/collection/dcdis/id/220358">Representation and enumeration of interval orders and semiorders</a>, Ph.D. Thesis, Dartmouth, 1976.

%H T. L. Greenough, <a href="/A005321/a005321_1.pdf">Enumeration of interval orders without duplicated holdings</a>, Preprint, circa 1976. [Annotated scanned copy]

%H T. Lockman Greenough, <a href="https://www.ams.org/journals/notices/197602/197602FullIssue.pdf">Enumeration of interval orders without duplicated holdings</a>, in Notices of the AMS, February 1976, page A-314.

%H T. L. Greenough and K. P. Bogart, <a href="/A005321/a005321.pdf">The Representation and Enumeration of Interval Orders</a>, Preprint, circa 1976. [Annotated scanned copy]

%H Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, <a href="https://arxiv.org/abs/2012.13570">Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow</a>, arXiv:2012.13570 [math.CO], 2020.

%H Vít Jelínek, <a href="https://arxiv.org/abs/1106.2261">Counting Self-Dual Interval Orders</a>, arXiv:1106.2261 [math.CO], 2011. See Corollary 2.4.

%H Vít Jelínek, <a href="http://dx.doi.org/10.1016/j.jcta.2011.11.010">Counting general and self-dual interval orders</a>, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614. See Corollary 2.4.

%H J. Longyear, T. Trotter, N. J. A. Sloane, <a href="/A005321/a005321_2.pdf">Correspondence</a>

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

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

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

%F From _Peter Bala_, Jul 06 2017: (Start)

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

%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 - ...)))))))));

%F 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)

%F 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

%F 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

%t 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_ *)

%o (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

%Y Cf. A022493, A138265, A289314, A289315.

%Y Column sums of A137252.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Max Alekseyev_, Apr 27 2010