login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A138265 Number of upper triangular zero-one matrices with n ones and no zero rows or columns. 12
1, 1, 1, 2, 5, 16, 61, 271, 1372, 7795, 49093, 339386, 2554596, 20794982, 182010945, 1704439030, 17003262470, 180011279335, 2015683264820, 23801055350435, 295563725628564, 3850618520827590, 52514066450469255, 748191494586458700, 11115833059268126770 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Row sums of A193357.

This is also the number of rigid unlabeled interval orders with n points (see Brightwell-Keller, Theorem 2; or Dukes-Kitaev-Remmel-Steingrímsson, Theorem 8). - N. J. A. Sloane, Dec 04 2011  [Corrected by Vít Jelínek, Sep 04 2014.]

Number of length-n ascent sequences without flat steps (i.e., no two adjacent digits are equal).  An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(k)>=0 and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) gives the number of ascents of its argument. [Joerg Arndt, Nov 05 2012]

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..300

G. E. Andrews, J. A. Sellers, Congruences for the Fishburn Numbers, arXiv preprint arXiv:1401.5345 [math.NT], 2014 (see final paragraph of text).

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.

Graham Brightwell, Mitchel T. Keller, Asymptotic Enumeration of Labelled Interval Orders, arXiv 1111.6766 [math.CO], 2011.

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.

M. Dukes, S. Kitaev, J. Remmel, E. Steingrímsson, Enumerating (2+2)-free posets by indistinguishable elements, arXiv:1006.2696 [math.CO], 2010.

M. Dukes, S. Kitaev, J. Remmel, E. Steingrímsson, Enumerating (2+2)-free posets by indistinguishable elements, Journal of Combinatorics, Volume 2, Issue 1, 2011, pp. 139-163.

F. Garvan, Congruences and relations for the r-Fishburn numbers, arXiv:1406.5611 [math.NT], 2014.

V. Jelínek, Counting self-dual interval orders, arXiv:1106.2261 [math.CO], 2011.

V. Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614.

Soheir Mohamed Khamis, Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height, Order (journal), published on-line, 2011.

Yan X Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318 [math.CO], 2015.

FORMULA

G.f.: Sum_{n>=0} (Prod_{i=1..n} 1-1/(1+x)^i).

G.f.: Sum_{n>=0} (1+x)^(n+1)*Prod_{i=1..n} (1-(1+x)^i)^2. Proved by Bringmann-Li-Rhoades, and by Andrews-Jelínek. - Vít Jelínek, Sep 04 2014

a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k)*A079144(k). a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n-1,k-1)*A022493(k).

G.f.: B(x/(1+x)) where B(x) is the g.f. of A022493; g.f.: Q(0,u) where u=x/(1+x), Q(k,u) = 1 + (1 - (1-x)^(2*k+1))/(1 - (1-(1-x)^(2*k+2))/(1 -(1-x)^(2*k+2) + 1/Q(k+1,u) )); (continued fraction). - Sergei N. Gladkovskii, Oct 03 2013

Asymptotics (Brightwell and Keller, 2011): a(n) ~ 12*sqrt(3)/(exp(Pi^2/12)*Pi^(5/2)) * n!*sqrt(n)*(6/Pi^2)^n. - Vaclav Kotesovec, May 03 2014

From Vít Jelínek, Sep 04 2014: (Start)

For each m, a(5m+4) mod 5 = 0. Conjectured by Andrews-Sellers, and proved by Garvan (see Remark 1.4(ii) in Garvan's paper).

For each m, a(5m+1) mod 5 = a(5m+2) mod 5 = 3*a(5m+3) mod 5. Proved by Garvan (see (1.17) in Garvan's paper).

The limit a(n)/A022493(n) is equal to exp(-Pi^2/6). This corresponds to the asymptotic probability that a random unlabelled interval order is rigid (See Brightwell-Keller; or Jelínek, Fact 5.2).

(End)

EXAMPLE

From Joerg Arndt, Nov 05 2012: (Start)

The a(4) = 5 such matrices with 4 ones are (dots for zeros):

1 . . .      1 1 .      1 . 1      1 1 .      1 . .

. 1 . .      . . 1      . 1 .      . 1 .      . 1 1

. . 1 .      . . 1      . . 1      . . 1      . . 1

. . . 1

The a(5)=16 ascent sequences without flat steps are (dots for zeros):

[ 1]   [ . 1 . 1 . ]

[ 2]   [ . 1 . 1 2 ]

[ 3]   [ . 1 . 1 3 ]

[ 4]   [ . 1 . 2 . ]

[ 5]   [ . 1 . 2 1 ]

[ 6]   [ . 1 . 2 3 ]

[ 7]   [ . 1 2 . 1 ]

[ 8]   [ . 1 2 . 2 ]

[ 9]   [ . 1 2 . 3 ]

[10]   [ . 1 2 1 . ]

[11]   [ . 1 2 1 2 ]

[12]   [ . 1 2 1 3 ]

[13]   [ . 1 2 3 . ]

[14]   [ . 1 2 3 1 ]

[15]   [ . 1 2 3 2 ]

[16]   [ . 1 2 3 4 ]

(End)

MAPLE

g:=sum(product(1-1/(1+x)^i, i=1..n), n=0..35): gser:=series(g, x=0, 30): seq(coeff(gser, x, n), n=0..22);  # Emeric Deutsch, Mar 23 2008

# second Maple program:

b:= proc(n, i, t) option remember; `if`(n<1, 1, add(

     `if`(i=j, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+1))

    end:

a:= n-> b(n-1, 0$2):

seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2012, Jan 14 2015

MATHEMATICA

max = 25; g = Sum[Product[1 - 1/(1 - x)^i, {i, 1, n}], {n, 0, max}]; gser = Series[g, {x, 0, max}]; a[n_] := SeriesCoefficient[gser, {x, 0, n}]; Table[a[n] // Abs, {n, 0, max-1}] (* Jean-François Alcover, Jan 24 2014, after Emeric Deutsch *)

PROG

(Sage) # Adaptation of the Maple program by Alois P. Heinz:

@CachedFunction

def b(n, i, t):

    if n<1: return 1

    return sum( b(n-1, j, t+(j>i)) for j in xrange (0, t+2) )

def a(n):

    if n<1: return 1

    return sum( (-1)^(n-k)*binomial(n-1, k-1)*b(k-1, 0, 0) for k in xrange(0, n+1) )

v138265=[a(n) for n in xrange(0, 33)]

print v138265

# Joerg Arndt, Feb 26 2014

CROSSREFS

Cf. A005321, A104602, A135588, A193548.

Column k=0 of A242153.

Column k=1 of A264909.

Sequence in context: A009736 A104858 A178123 * A275711 A163747 A000111

Adjacent sequences:  A138262 A138263 A138264 * A138266 A138267 A138268

KEYWORD

easy,nonn

AUTHOR

Vladeta Jovovic, Mar 10 2008, Mar 11 2008

EXTENSIONS

More terms from Emeric Deutsch, Mar 23 2008

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 23 02:54 EDT 2017. Contains 288633 sequences.