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 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.
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
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 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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Vladeta Jovovic, Mar 10 2008, Mar 11 2008
EXTENSIONS
More terms from Emeric Deutsch, Mar 23 2008
STATUS
approved