%I #104 Aug 23 2023 08:35:47

%S 1,1,1,2,5,16,61,271,1372,7795,49093,339386,2554596,20794982,

%T 182010945,1704439030,17003262470,180011279335,2015683264820,

%U 23801055350435,295563725628564,3850618520827590,52514066450469255,748191494586458700,11115833059268126770

%N Number of upper triangular zero-one matrices with n ones and no zero rows or columns.

%C Row sums of A193357.

%C 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.]

%C 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]

%H Alois P. Heinz, <a href="/A138265/b138265.txt">Table of n, a(n) for n = 0..300</a>

%H G. E. Andrews and J. A. Sellers, <a href="http://arxiv.org/abs/1401.5345">Congruences for the Fishburn Numbers</a>, arXiv preprint arXiv:1401.5345 [math.NT], 2014 (see final paragraph of text).

%H George E. Andrews and Vít Jelínek, <a href="http://arxiv.org/abs/1309.6669">On q-Series Identities Related to Interval Orders</a>, arXiv:1309.6669 [math.CO], 2013.

%H George E. Andrews and Vít Jelínek, <a href="http://dx.doi.org/10.1016/j.ejc.2014.01.003">On q-Series Identities Related to Interval Orders</a>, European Journal of Combinatorics, Volume 39, July 2014, 178-187.

%H Graham Brightwell and Mitchel T. Keller, <a href="http://arxiv.org/abs/1111.6766">Asymptotic Enumeration of Labelled Interval Orders</a>, arXiv 1111.6766 [math.CO], 2011.

%H Kathrin Bringmann, Yingkun Li, and Robert C. Rhoades, <a href="http://dx.doi.org/10.1016/j.ejc.2014.04.003">Asymptotics for the number of row-Fishburn matrices</a>, European Journal of Combinatorics, vol.41, pp.183-196, (October-2014); <a href="http://www.mi.uni-koeln.de/Bringmann/selfdual_rev7.pdf">preprint</a>.

%H Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, <a href="https://www.researchgate.net/publication/363253998_A_Combinatorial_Study_of_AsyncAwait_Processes">A Combinatorial Study of Async/Await Processes</a>, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.

%H M. Dukes, S. Kitaev, J. Remmel, and E. Steingrímsson, <a href="http://arxiv.org/abs/1006.2696">Enumerating (2+2)-free posets by indistinguishable elements</a>, arXiv:1006.2696 [math.CO], 2010.

%H M. Dukes, S. Kitaev, J. Remmel, and E. Steingrímsson, <a href="http://dx.doi.org/10.4310/JOC.2011.v2.n1.a6">Enumerating (2+2)-free posets by indistinguishable elements</a>, Journal of Combinatorics, Volume 2, Issue 1, 2011, pp. 139-163.

%H F. Garvan, <a href="http://arxiv.org/abs/1406.5611">Congruences and relations for the r-Fishburn numbers</a>, arXiv:1406.5611 [math.NT], 2014.

%H Ankush Goswami, Abhash Kumar Jha, Byungchan Kim, and Robert Osburn, <a href="https://arxiv.org/abs/2204.02628">Asymptotics and sign patterns for coefficients in expansions of Habiro elements</a>, arXiv:2204.02628 [math.NT], 2022.

%H Hsien-Kuei Hwang and Emma Yu Jin, <a href="https://arxiv.org/abs/1911.06690">Asymptotics and statistics on Fishburn matrices and their generalizations</a>, arXiv:1911.06690 [math.CO], 2019.

%H V. Jelínek, <a href="http://arxiv.org/abs/1106.2261">Counting self-dual interval orders</a>, arXiv:1106.2261 [math.CO], 2011.

%H V. Jelínek, <a href="http://dx.doi.org/10.1016/j.jcta.2011.11.010">Counting general and self-dual interval orders</a>, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614.

%H V. Jelinek, <a href="https://doi.org/10.1016/j.aam.2015.06.007">Catalan pairs and Fishburn triples</a>, Adv. Appl. Math. 70 (2015) 1-31

%H Soheir Mohamed Khamis, <a href="http://dx.doi.org/10.1007/s11083-011-9213-5">Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height</a>, Order (journal), published on-line, 2011.

%H Yan X. Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015.

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

%F 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

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

%F 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

%F 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

%F From _Vít Jelínek_, Sep 04 2014: (Start)

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

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

%F 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)

%F 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

%e From _Joerg Arndt_, Nov 05 2012: (Start)

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

%e 1 . . . 1 1 . 1 . 1 1 1 . 1 . .

%e . 1 . . . . 1 . 1 . . 1 . . 1 1

%e . . 1 . . . 1 . . 1 . . 1 . . 1

%e . . . 1

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

%e [ 1] [ . 1 . 1 . ]

%e [ 2] [ . 1 . 1 2 ]

%e [ 3] [ . 1 . 1 3 ]

%e [ 4] [ . 1 . 2 . ]

%e [ 5] [ . 1 . 2 1 ]

%e [ 6] [ . 1 . 2 3 ]

%e [ 7] [ . 1 2 . 1 ]

%e [ 8] [ . 1 2 . 2 ]

%e [ 9] [ . 1 2 . 3 ]

%e [10] [ . 1 2 1 . ]

%e [11] [ . 1 2 1 2 ]

%e [12] [ . 1 2 1 3 ]

%e [13] [ . 1 2 3 . ]

%e [14] [ . 1 2 3 1 ]

%e [15] [ . 1 2 3 2 ]

%e [16] [ . 1 2 3 4 ]

%e (End)

%p 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

%p # second Maple program:

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

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

%p end:

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

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 09 2012, Jan 14 2015

%t 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_ *)

%o (Sage) # Adaptation of the Maple program by _Alois P. Heinz_:

%o @CachedFunction

%o def b(n, i, t):

%o if n<1: return 1

%o return sum(b(n-1, j, t+(j>i)) for j in range(t+2))

%o def a(n):

%o if n<1: return 1

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

%o [a(n) for n in range(33)]

%o # _Joerg Arndt_, Feb 26 2014

%Y Cf. A005321, A104602, A135588, A193548, A194530.

%Y Column k=0 of A242153.

%Y Column k=1 of A264909.

%Y Row sums of A137252.

%K easy,nonn

%O 0,4

%A _Vladeta Jovovic_, Mar 10 2008, Mar 11 2008

%E More terms from _Emeric Deutsch_, Mar 23 2008