A179525 - OEIS

%I #64 Jan 31 2021 08:43:06

%S 1,1,2,7,33,197,1419,11966,115575,1257718,15223822,202860828,

%T 2950665011,46516215168,790009447590,14379745626739,279256447482090,

%U 5763290215111558,125960271446527241,2906289188751628643,70594767279197608011,1800695322331687800336,48122711251655255426539,1344617808976210991187090,39206731897407002624384182,1190905492485213830900901986

%N G.f.: A(x) = Sum_{n>=0} Product_{k=1..n} ((1+x)^k - 1).

%C From _Vít Jelínek_, Feb 12 2012: (Start)

%C a(n) has the following combinatorial interpretations:

%C (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):

%C 1.  .1

%C .1  .1

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

%C 11.  1...

%C ..1  .1..

%C ..1  ..1.

%C      ...1

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

%C 11  1..

%C .1  .1.

%C     ..1

%C (End)

%C This is an example of Peter Bala's identity (cf. A158690):

%C 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.

%H Vaclav Kotesovec, <a href="/A179525/b179525.txt">Table of n, a(n) for n = 0..360</a>

%H Kathrin Bringmann, Yingkun Li, Robert C. Rhoades, <a href="https://doi.org/10.1016/j.ejc.2014.04.003">Asymptotics for the number of row-Fishburn matrices</a>, European Journal of Combinatorics, vol.41, pp.183-196, (October-2014); <a href="http://www.mi.uni-koeln.de/Bringmann/selfdual_rev7.pdf">preprint</a>.

%H Stuart A. Hannah, <a href="http://arxiv.org/abs/1502.05340">Sieved Enumeration of Interval Orders and Other Fishburn Structures</a>, arXiv:1502.05340 [math.CO], (18-February-2015).

%H Hsien-Kuei Hwang, Emma Yu Jin, <a href="https://arxiv.org/abs/1911.06690">Asymptotics and statistics on Fishburn matrices and their generalizations</a>, arXiv:1911.06690 [math.CO], 2019.

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

%H Sherry H. F. Yan and Yuexiao Xu, <a href="http://arxiv.org/abs/1111.4723">Self-dual interval orders and row-Fishburn matrices</a>, arXiv:1111.4723 [math.CO], 2011.

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

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

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

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

%F From _Peter Bala_, May 16 2017: (Start)

%F G.f.: A(x) = 1/2*( 1 + Sum_{n >= 0} (1 + x)^(n+1)*Product_{k = 1..n} ((1 + x)^k - 1) ).

%F Conjectural g.f.: Sum_{n >= 0} 1/(1 + x)^(n+1)*Product_{k = 1..n} (1 - 1/(1 + x)^(2*k)).

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

%e G.f.: A(x) = 1 + x + 2*x^2 + 7*x^3 + 33*x^4 + 197*x^5 + 1419*x^6 +...

%e A(x) = 1 + ((1+x)-1) + ((1+x)-1)*((1+x)^2-1) + ((1+x)-1)*((1+x)^2-1)*((1+x)^3-1) +...

%e Let q = 1+x, then g.f. also equals:

%e 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 +...

%t a[ n_] := SeriesCoefficient[ Sum[ Product[ (1 + x)^j - 1, {j, k}], {k, 0, n}], {x, 0, n}]; (* _Michael Somos_, Jun 27 2017 *)

%o (PARI) {a(n) = polcoeff(sum(i=0, n, prod(j=1, i, (1+x)^j-1, 1+x*O(x^n))), n)};

%o for(n=0, 30, print1(a(n), ", "))

%o (PARI) /* G.f. as a continued fraction: */

%o {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)}

%o for(n=0, 30, print1(a(n), ", "))

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

%o for(n=0, 30, print1(a(n), ", "))

%o (PARI) /* Sum_{n>=0} n!*Product_{k=0..n-1} [Integral (1+x)^k dx] */

%o {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)}

%o for(n=0, 30, print1(a(n), ", ")) \\ _Paul D. Hanna_, Aug 16 2016

%Y Cf. variants: A022493, A122400, A158691, A158690, A207386, A207397, A207433.

%Y Cf. A207434 (log).

%K nonn

%O 0,3

%A _Paul D. Hanna_, Jul 17 2010