A079144 Number of labeled interval orders on n elements: (2+2)-free posets.

1, 1, 3, 19, 207, 3451, 81663, 2602699, 107477247, 5581680571, 356046745023, 27365431508779, 2494237642655487, 266005087863259291, 32815976815540917183, 4636895313201764853259, 743988605732990946684927

Offset

0,3

Comments

From Peter Bala, Dec 26 2021: (Start)

We make the following conjectures:

1) Taking the sequence modulo an integer k gives an eventually periodic sequence with period dividing phi(k). For example, the sequence taken modulo 8 begins [1, 1, 3, 3, 7, 3, 7, 3, 7, ...] and appears to have a pre-period of length 3 and a period of length 2 = (1/2)*phi(8).

2) Let i >= 0 and define a_i(n) = a(n+i). Then for each i the Gauss congruences a_i(n*p^k) == a_i(n*p^(k-1)) ( mod p^k ) hold for all prime p and positive integers n and k. If true, then for each i the expansion of exp( Sum_{n >= 1} a_i(n)*x^n/n ) has integer coefficients. (End)

Links

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

Peter Bala, Some S-fractions related to the expansions of sin(ax)/cos(bx) and cos(ax)/cos(bx)

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

Anders Claesson, Mark Dukes and Martina Kubitzke, Partition and composition matrices, arXiv:1006.1312 [math.CO], 2010-2011.

Hsien-Kuei Hwang and Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.

Don Zagier, Vassiliev invariants and a strange identity related to the Dedekind eta-function, Topology, vol.40, pp.945-960 (2001); see p. 952.

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

Formula

a(n) = (1/(24^n))*Sum_{k=0..n} binomial(n, k)*A002439(k). Zagier 2001, p. 954.

G.f.: Sum(Product(1-exp(-k*x),k = 1 .. n),n = 0 .. infinity). a(n) = Sum_{k=0..n} k!*Stirling2(n,k)*A138265(k). - Vladeta Jovovic, Mar 11 2008

From Peter Bala, Mar 19 2009: (Start)

Conjectural form for the o.g.f. as a continued fraction:

1/(1-x/(1-2*x/(1-5*x/(1-7*x/(1-12*x/(1-15*x/(1- ...))))))) = 1 + x + 3*x^2 + 19*x^3 + 207*x^4 + ..., where the sequence [1,2,5,7,12,15,..] is the sequence of generalized pentagonal numbers A001318. Compare with the continued fraction form of the o.g.f. of A002105. (End)

E.g.f.: 1+(exp(x)-1)/(G(0)+1-exp(x)), where G(k)= 2*exp(x*(k+1))-1-exp(x*(k+1))*(exp(x*(k+2))-1)/G(k+1); (continued fraction, Euler's kind, 1-step). - Sergei N. Gladkovskii, Jan 06 2012

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

From Peter Bala, May 11 2017: (Start)

For a proof of above conjectural continued fraction representation of the o.g.f. see the Bala link.

G.f.: 1/(1 + x - 2*x/(1 - 1*x/(1 + x - 7*x/(1 - 5*x/(1 + x - 15*x/(1 - 12*x/(1 + x - 26*x/(1 - 22*x/(1 + x - ...))))))))), where the sequence of unsigned partial numerators [2, 1, 7, 5, 15, 12, ...] is obtained from A001318 by swapping adjacent terms.

E.g.f.: F(q) = Sum_{n >= 0} q^(n+1)*Product_{i = 1..n} (1 - q^i)^2 at q = exp(t). Note that F(q) at q = 1/(1 - t) is a g.f. for unlabeled interval orders A022493, and at q = 1 - t gives a g.f. for A138265. (End)

From Peter Bala, Dec 26 2021: (Start)

a(6*n + 5) == 0 (mod 7); a(10*n + 7) == 0 (mod 11);

a(12*n + 11) == 0 (mod 13); a(16*n + 5) == a(16*n + 8) == 0 (mod 17);

a(18*n + 3) == 0 (mod 19); a(22*n + 4) == 0 (mod 23). (End)

Example

1 + x + 3*x^2 + 19*x^3 + 207*x^4 + 3451*x^5 + 81663*x^6 + 2602699*x^7 + ...

Maple

A002439 := proc(n) option remember; if n = 0 then 1; else (-4)^n-add((-9)^k*binomial(2*n+1, 2*k)*procname(n-k), k=1..n+1) ; end if; end proc:
seq(1/(24^n)*add(binomial(n, k)*A002439(k), k = 0..n), n = 0..20); # Peter Bala, Dec 26 2021

Mathematica

nmax=20; rk=Rest[CoefficientList[Series[Sum[Product[1-1/(1+x)^j, {j, 1, n}], {n, 0, nmax}], {x, 0, nmax}], x]]; Flatten[{1, Table[Sum[rk[[k]] * k! * StirlingS2[n, k], {k, 1, n}], {n, 1, nmax}]}] (* Vaclav Kotesovec, May 03 2014 *)

Prog

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( subst( sum( i=0, n, prod( j=1, i, 1 - (1 - x + O(x^(n - i + 2)))^j )), x, 1 - exp( -x + x * O(x^n))), n))} /* Michael Somos, Apr 01 2012 */

Crossrefs

Cf. A022493 (unlabeled interval orders).

Cf. A002439 (Glaisher's T numbers), A002114 (Glaisher's H numbers).

Cf. A001318, A138265.

Sequence in context: A052886 A180563 A294330 * A345218 A049056 A204262

Adjacent sequences: A079141 A079142 A079143 * A079145 A079146 A079147

Keyword

nonn,easy

Author

Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2002

Status

approved