A138265 Number of upper triangular zero-one matrices with n ones and no zero rows or columns.
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
Offset: 0
Examples
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)
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..300
- G. E. Andrews and J. A. Sellers, Congruences for the Fishburn Numbers, arXiv preprint arXiv:1401.5345 [math.NT], 2014 (see final paragraph of text).
- George E. Andrews and Vít Jelínek, On q-Series Identities Related to Interval Orders, arXiv:1309.6669 [math.CO], 2013.
- George E. Andrews and Vít Jelínek, On q-Series Identities Related to Interval Orders, European Journal of Combinatorics, Volume 39, July 2014, 178-187.
- Graham Brightwell and Mitchel T. Keller, Asymptotic Enumeration of Labelled Interval Orders, arXiv 1111.6766 [math.CO], 2011.
- Kathrin Bringmann, Yingkun Li, and Robert C. Rhoades, Asymptotics for the number of row-Fishburn matrices, European Journal of Combinatorics, vol.41, pp.183-196, (October-2014); preprint.
- Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, A Combinatorial Study of Async/Await Processes, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.
- M. Dukes, S. Kitaev, J. Remmel, and E. Steingrímsson, Enumerating (2+2)-free posets by indistinguishable elements, arXiv:1006.2696 [math.CO], 2010.
- M. Dukes, S. Kitaev, J. Remmel, and 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.
- Ankush Goswami, Abhash Kumar Jha, Byungchan Kim, and Robert Osburn, Asymptotics and sign patterns for coefficients in expansions of Habiro elements, arXiv:2204.02628 [math.NT], 2022.
- Hsien-Kuei Hwang and Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.
- 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.
- V. Jelinek, Catalan pairs and Fishburn triples, Adv. Appl. Math. 70 (2015) 1-31
- 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.
Crossrefs
Programs
-
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 *) -
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 range(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 range(n+1)) [a(n) for n in range(33)] # Joerg Arndt, Feb 26 2014
Formula
G.f.: Sum_{n>=0} (Product_{i=1..n} 1-1/(1+x)^i).
G.f.: Sum_{n>=0} (1+x)^(n+1)*Product_{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 unlabeled interval order is rigid (See Brightwell-Keller; or Jelínek, Fact 5.2). (End)
Conjectural g.f.: 1 + Sum_{n >= 0} n/(1+x)^(n+1) * (Product_{i = 1..n} 1 - 1/(1+x)^i). Cf. A194530. - Peter Bala, Aug 21 2023
Extensions
More terms from Emeric Deutsch, Mar 23 2008
Comments