login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A158691 The number of upper-triangular 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 - (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)

LINKS

Table of n, a(n) for n=0..21.

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

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)

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-(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 *)

PROG

(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 */

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 25 20:48 EST 2020. Contains 338627 sequences. (Running on oeis4.)