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