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

1, 1, 3, 12, 61, 380, 2815, 24213, 237348, 2612681, 31915787, 428481472, 6271362282, 99388642292, 1695614865711, 30984649882928, 603790447393402, 12498732438500663, 273902239550757626, 6334968666307580051, 154211723833861061644, 3941258052200287007636

Offset: 0

Author

Peter Bala, Mar 24 2009

Keywords

• easy
• nonn

Comments

There is a connection with the alternating series 1 - (1-x) + (1-x)(1-x^2) - (1-x)(1-x^2)(1-x^3) + .... Namely, if we replace x with 1/(1-x) in the partial sum 1 - (1-x) + (1-x)(1-x^2) - (1-x)(1-x^2)(1-x^3) + ... + (-1)^n(1-x)(1-x^2)...(1-x^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-(1-x)^(2*i-1))

F(x) = Sum_{n>=0} Product_{i=1..n} (1/(1-x)^i - 1)

F(x) = Sum_{n>=0} (1-x)^(n+1) Product_{i=1..n} (1-(1-x)^(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+(1-x)^i)).

(End)

From Vít Jelínek, Feb 12 2012: (Start)

a(n) has the following combinatorial interpretations:

(1) the number of upper-triangular 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 upper-triangular 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 upper-triangular 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)

Examples

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..200
• George E. Andrews, Vít Jelínek, On q-Series Identities Related to Interval Orders, arXiv:1309.6669 [math.CO], 2013.
• George E. Andrews, Vít Jelínek, On q-Series Identities Related to Interval Orders, European Journal of Combinatorics, Volume 39, July 2014, 178-187.
• Kathrin Bringmann, Yingkun Li, Robert C. Rhoades, Asymptotics for the number of row-Fishburn matrices, European Journal of Combinatorics, Volume 41, October 2014, Pages 183-196; preprint.
• Hsien-Kuei 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 self-dual interval orders, arXiv:1106.2261 [math.CO], 2011.
• 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.
• Sherry H. F. Yan and Yuexiao Xu, Self-dual interval orders and row-Fishburn matrices, Electronic Journal of Combinatorics, 19(2):P5 (2012).

Crossrefs

Cf. A022493, A138265, A158690, A179525.

Programs

Maple

g:=sum(product(1-(1-x)^(2*i-1), 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(1-1/(1-x)^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 *)

PARI

{a(n)=polcoeff(sum(m=0, n, prod(k=1, m, 1/(1-x)^k-1, 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 - (1-x)^(n-k+1)*(1-(1-x)^(n-k+2))*CF)); polcoeff(1/(1-x*CF), n, x)} /* Paul D. Hanna, Jan 29 2012 */

Formula

Sum_{n >= 0} Product_{i= 1..n} (1-(1-x)^(2*i-1)) = 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/(1-x)^k - 1].

G.f.: 1/(1 - (1-(1-x))/(1 - (1-x)*(1-(1-x)^2)/(1 - (1-x)^2*(1-(1-x)^3)/(1 - (1-x)^3*(1-(1-x)^4)/(1 - (1-x)^4*(1-(1-x)^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)