

A158691


The number of uppertriangular matrices with at least one nonzero entry in each row and whose entries sum to n.


8



1, 1, 3, 12, 61, 380, 2815, 24213, 237348, 2612681, 31915787, 428481472, 6271362282, 99388642292, 1695614865711, 30984649882928, 603790447393402, 12498732438500663, 273902239550757626, 6334968666307580051, 154211723833861061644, 3941258052200287007636
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

There is a connection with the alternating series 1  (1x) + (1x)(1x^2)  (1x)(1x^2)(1x^3) + .... Namely, if we replace x with 1/(1x) in the partial sum 1  (1x) + (1x)(1x^2)  (1x)(1x^2)(1x^3) + ... + (1)^n(1x)(1x^2)...(1x^n) and then expand about x = 0 we get a series whose first n+1 coefficients agree with the first n+1 terms of the present sequence.
From Vít Jelínek, Sep 04 2014: (Start)
The above remark, first conjectured by Bala, is a consequence of the identities satisfied by the generating function for a(n). More precisely, the generating function F(x)=Sum_{n>=0} a(n)x^n can be expressed by any of these three formulas:
F(x) = Sum_{n>=0} Product_{i=1..n} (1(1x)^(2*i1))
F(x) = Sum_{n>=0} Product_{i=1..n} (1/(1x)^i  1)
F(x) = Sum_{n>=0} (1x)^(n+1) Product_{i=1..n} (1(1x)^(2*i))
The first two formulas were conjectured to be equal by Bala. This was confirmed by Andrews and Jelínek, who also derived the third formula.
Bringmann, Li and Rhoades have independently derived the three formulas above, and additionaly, they proved that
F(x) = (1/2)*Sum_{n>=0} Product_{i=1..n} (1/(1+(1x)^i)).
(End)
From Vít Jelínek, Feb 12 2012: (Start)
a(n) has the following combinatorial interpretations:
(1) the number of uppertriangular nonnegative integer matrices with at least one positive entry in each row, whose entries sum to n. E.g., for n=2 this corresponds to these three matrices (with zeros represented as dots):
(2), (1.) and (.1)
(.1) (.1)
(2) the number of uppertriangular nonnegative matrices that are symmetric along the northeast diagonal, have no positive entry on the northeast diagonal, have at least one positive entry in every row and column, and their entries sum to 2n. These are the three such matrices with n=2:
(2.), (11.) and (1...)
(.2) (..1) (.1..)
(..1) (..1.)
(...1)
(3) the number of uppertriangular nonnegative matrices that are symmetric along the northeast diagonal, have at least one positive entry on the northeast diagonal, have at least one positive entry in every row and column, and their entries on or above the northeast diagonal sum to n. These are the three such matrices with n=2:
(2), (11) and (1..)
(.1) (.1.)
(..1)
(End)


LINKS

Table of n, a(n) for n=0..21.
George E. Andrews, Vít Jelínek, On qSeries Identities Related to Interval Orders, arXiv:1309.6669 [math.CO], 2013.
George E. Andrews, Vít Jelínek, On qSeries Identities Related to Interval Orders, European Journal of Combinatorics, Volume 39, July 2014, 178187.
Kathrin Bringmann, Yingkun Li, Robert C. Rhoades, Asymptotics for the number of rowFishburn matrices, European Journal of Combinatorics, Volume 41, October 2014, Pages 183196; preprint.
HsienKuei Hwang, Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.
Florian Ingels, Romain Azaïs, Enumeration of Unordered Forests, arXiv:2003.08144 [cs.DM], 2020.
Vít Jelínek, Counting selfdual interval orders, arXiv:1106.2261 [math.CO], 2011.
Vít Jelínek, Counting general and selfdual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599614.
Sherry H. F. Yan and Yuexiao Xu, Selfdual interval orders and rowFishburn matrices, arXiv:1111.4723 [math.CO], 2011.
Sherry H. F. Yan and Yuexiao Xu, Selfdual interval orders and rowFishburn matrices, Electronic Journal of Combinatorics, 19(2):P5 (2012).


FORMULA

Sum_{n >= 0} Product_{i= 1..n} (1(1x)^(2*i1)) = 1 + x + 3*x^2 + 12*x^3 + 61*x^4 + .... Compare with A022493, A138265 and A158690.
G.f.: Sum_{n>=0} Product_{k=1..n} [1/(1x)^k  1].
G.f.: 1/(1  (1(1x))/(1  (1x)*(1(1x)^2)/(1  (1x)^2*(1(1x)^3)/(1  (1x)^3*(1(1x)^4)/(1  (1x)^4*(1(1x)^5)/(1 ...)))))), a continued fraction.  Paul D. Hanna, Jan 29 2012
By results of Bringmann, Li and Rhoades, a(n) is asymptotically c*n!*(12/Pi^2)^n, with c=6*sqrt(2)*exp(Pi^2/24)/Pi^2, and the ratio a(n)/A179525(n) tends to exp(Pi^2/12).  Vít Jelínek, Sep 04 2014
From Peter Bala, May 16 2017: (Start)
G.f. 1/2*( 1 + Sum_{n >= 0} 1/(1  x)^((n+1)*(n+2)/2) * Product_{i = 1..n} (1  (1  x)^i) ).
Conjectural g.f.: Sum_{n >= 0} 1/(1  x)^((n+1)*(2*n+1)) * Product_{i = 1..2*n} ((1  x)^i  1). (End)


EXAMPLE

G.f.: A(x) = 1 + x + 3*x^2 + 12*x^3 + 61*x^4 + 380*x^5 + 2815*x^6 +...


MAPLE

g:=sum(product(1(1x)^(2*i1), i= 1..n), n = 0..20): gser:=series(g, x = 0, 20): seq(coeff(gser, x, n), n = 0..19); # by definition
g:=sum((1)^n*product(11/(1x)^i, i= 1..n), n = 0..20): gser:=series(g, x = 0, 20): seq(coeff(gser, x, n), n = 0..19);


MATHEMATICA

a[ n_] := SeriesCoefficient[ Sum[ Product[ 1  (1  x)^(2 i  1), {i, k}], {k, 0, n}], {x, 0, n}]; (* Michael Somos, Jun 27 2017 *)


PROG

(PARI) {a(n)=polcoeff(sum(m=0, n, prod(k=1, m, 1/(1x)^k1, 1+x*O(x^n))), n)} /* Paul D. Hanna, Jan 29 2012 */
(PARI) /* G.f. as a Continued Fraction: */
{a(n)=local(CF=1+x*O(x)); for(k=0, n, CF=1/(1  (1x)^(nk+1)*(1(1x)^(nk+2))*CF)); polcoeff(1/(1x*CF), n, x)} /* Paul D. Hanna, Jan 29 2012 */


CROSSREFS

Cf. A022493, A138265, A158690, A179525.
Sequence in context: A317169 A121694 A331616 * A038171 A258798 A074516
Adjacent sequences: A158688 A158689 A158690 * A158692 A158693 A158694


KEYWORD

easy,nonn


AUTHOR

Peter Bala, Mar 24 2009


STATUS

approved



