OFFSET
0,3
COMMENTS
From Vít Jelínek, Feb 12 2012: (Start)
a(n) has the following combinatorial interpretations:
(1) the number of upper-triangular matrices over {0,1} having at least one '1'-entry in each row and having n '1'-entries in total. E.g., for n=2, this corresponds to these two matrices (with zeros represented as dots):
1. .1
.1 .1
(2) the number of upper-triangular matrices over {0,1} that are symmetric with respect to the northeast diagonal, have at least one '1'-entry in each row and column, have no '1'-entry on the northeast diagonal, and have 2n '1'-entries in total. For n=2, those are the two matrices
11. 1...
..1 .1..
..1 ..1.
...1
(3) the number of upper-triangular matrices over {0,1} that are symmetric with respect to the northeast diagonal, have at least one '1'-entry in each row and column, have at least one '1'-entry on the northeast diagonal, and have n '1'-entries on or above the northeast diagonal. For n=2, this corresponds to
11 1..
.1 .1.
..1
(End)
This is an example of Peter Bala's identity (cf. A158690):
Sum_{n>=0} Product_{k=1..n} (q^k - 1) = Sum_{n>=0} q^(-n^2) * Product_{k = 1..n} (q^(2*k-1) - 1) at q = 1 + x. See cross-references for other examples.
LINKS
Vaclav Kotesovec, Table of n, a(n) for n = 0..360
Kathrin Bringmann, Yingkun Li, Robert C. Rhoades, Asymptotics for the number of row-Fishburn matrices, European Journal of Combinatorics, vol.41, pp.183-196, (October-2014); preprint.
Stuart A. Hannah, Sieved Enumeration of Interval Orders and Other Fishburn Structures, arXiv:1502.05340 [math.CO], (18-February-2015).
Hsien-Kuei Hwang, Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.
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.
Sherry H. F. Yan and Yuexiao Xu, Self-dual interval orders and row-Fishburn matrices, arXiv:1111.4723 [math.CO], 2011.
FORMULA
G.f.: 1/(1 - ((1+x)-1)/((1+x) - ((1+x)^2-1)/((1+x)^2 - ((1+x)^3-1)/((1+x)^3 - ((1+x)^4-1)/((1+x)^4 - ((1+x)^5-1)/((1+x)^5 -...)))))), (continued fraction) [Paul D. Hanna, Jan 29 2012]
G.f.: Sum_{n>=0} q^(-n^2) * Product_{k=1..n} (q^(2*k-1) - 1) where q = 1+x. [Based on Peter Bala's identity in comments]
Conjecturally, a(n) is asymptotically c*n!*(12/Pi^2)^n, where c=6*sqrt(2)*exp(-Pi^2/24)/Pi^2. - Vít Jelínek, Feb 12 2012 [This is correct: see Hwang and Jin, Table 3, p. 26. - Peter Bala, Jan 31 2021]
G.f.: Q(0), where Q(k)= 1 - (1-(1+x)^(2*k+1))/(1 - (1-(1+x)^(2*k+2))/(1 - (1+x)^(2*k+2) - 1/Q(k+1))); (continued fraction). Conjecture. - Sergei N. Gladkovskii, May 13 2013
From Peter Bala, May 16 2017: (Start)
G.f.: A(x) = 1/2*( 1 + Sum_{n >= 0} (1 + x)^(n+1)*Product_{k = 1..n} ((1 + x)^k - 1) ).
Conjectural g.f.: Sum_{n >= 0} 1/(1 + x)^(n+1)*Product_{k = 1..n} (1 - 1/(1 + x)^(2*k)).
Conjectural g.f.: Sum_{n >= 0} (1 + x)^(2*n+1)*Product_{k = 1..2*n} (1 - (1 + x)^k). Cf. A158690, which has e.g.f. A(exp(x) - 1). (End)
EXAMPLE
G.f.: A(x) = 1 + x + 2*x^2 + 7*x^3 + 33*x^4 + 197*x^5 + 1419*x^6 +...
A(x) = 1 + ((1+x)-1) + ((1+x)-1)*((1+x)^2-1) + ((1+x)-1)*((1+x)^2-1)*((1+x)^3-1) +...
Let q = 1+x, then g.f. also equals:
A(x) = 1 + (q-1)/q + (q-1)*(q^3-1)/q^4 + (q-1)*(q^3-1)*(q^5-1)/q^9 + (q-1)*(q^3-1)*(q^5-1)*(q^7-1)/q^16 + (q-1)*(q^3-1)*(q^5-1)*(q^7-1)*(q^9-1)/q^25 +...
MATHEMATICA
a[ n_] := SeriesCoefficient[ Sum[ Product[ (1 + x)^j - 1, {j, k}], {k, 0, n}], {x, 0, n}]; (* Michael Somos, Jun 27 2017 *)
PROG
(PARI) {a(n) = polcoeff(sum(i=0, n, prod(j=1, i, (1+x)^j-1, 1+x*O(x^n))), n)};
for(n=0, 30, print1(a(n), ", "))
(PARI) /* G.f. as a continued fraction: */
{a(n) = local(CF=1+x*O(x)); for(k=0, n, CF=1/((1+x)^(n-k+1)-((1+x)^(n-k+2)-1)*CF)); polcoeff(1/(1-x*CF), n, x)}
for(n=0, 30, print1(a(n), ", "))
(PARI) {a(n) = local(A=1+x, q=(1+x +x*O(x^n))); A = sum(m=0, n, q^(-m^2)*prod(k=1, m, (q^(2*k-1)-1))); polcoeff(A, n)}
for(n=0, 30, print1(a(n), ", "))
(PARI) /* Sum_{n>=0} n!*Product_{k=0..n-1} [Integral (1+x)^k dx] */
{a(n) = my(A=1); A = sum(m=0, n, m! * prod(k=0, m-1, intformal((1+x)^k) +x*O(x^n)) ); polcoeff(A, n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Aug 16 2016
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Jul 17 2010
STATUS
approved