login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A223911 Number of tiered orders on n nodes (corrected version of A006860). 2
1, 1, 3, 13, 111, 1381, 25623, 678133, 26169951, 1447456261, 114973232583, 13034314621813, 2103826463800911, 481932523110975301, 156356753093586913143, 71729530379673590609653, 46471511649877647638694591, 42487759521494442057018000901, 54781291469300608901184153800103 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..100 (terms n = 1..22 from Joerg Arndt)

D. Klarner, The number of tiered posets modulo six, Discrete Math., 62 (1986), 295-297.

FORMULA

a(n) = sum(all composition C of n, M(C) * prod(j=1..m-1, f(C[j]*C[j+1]) ) ) where m is the number of parts of the current composition P, f(i,j) = sum(k=0..i, (-1)^(i-k) * binomial(i,k) * (2^k-1)^j ), and M(C) is the multinomial coefficient n!/prod(j=1..m, C[j]! ); see Pari code.

Klarner incorrectly gives prod(j=1..m-1, f(C[j]*C[m]) ) in the formula for a(n).

Conjecture: a(n) ~ c * 2^(n^2/4 + 3*n/2) / sqrt(n), where c = EllipticTheta[3, 0, 1/2^(1/4)] / (sqrt(Pi) * 2^(1/4)) = 2.020039... (based on the numerical analysis of 600 terms). - Vaclav Kotesovec, Apr 10 2015

MAPLE

f:= (i, j)-> add((-1)^(i-k)*binomial(i, k) *(2^k-1)^j, k=0..i):

b:= proc(n, i) option remember;

      `if`(n=0, 1, add(b(n-j, j)/j!*f(i, j), j=1..n))

    end:

a:= n-> n!*b(n, 1):

seq(a(n), n=0..20);  # Alois P. Heinz, Jul 23 2013

MATHEMATICA

f[i_, j_] := Sum[(-1)^(i-k)*Binomial[i, k]*(2^k-1)^j, {k, 0, i}]; b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j]/j!*f[i, j], {j, 1, n}]]; a[n_] := n!*b[n, 1]; Table[a[n], {n, 0, 20}] (* Jean-Fran├žois Alcover, Apr 08 2015, after Alois P. Heinz *)

PROG

(PARI)

f(m, n) = sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n );

mn(n, V, m) = n! / prod(k=1, m, V[k]! ); /* multinomial of V[1..m] */

A223911(n)=

{

    my(m=n, C=vector(n, j, 1), z, t, ret);

    while ( 1,  /* for all compositions C[1..m] of n */

        t = mn(n, C, m) * prod(j=1, m-1, f(C[j], C[j+1]) );

        ret += t;

        if ( m<=1, break() ); /* last composition? */

        /* create next composition: */

        C[m-1] += 1;

        z = C[m];

        C[m] = 1;

        m += z - 2;

    );

    return(ret);

}

CROSSREFS

Sequence in context: A183604 A228563 A222863 * A006860 A181083 A090537

Adjacent sequences:  A223908 A223909 A223910 * A223912 A223913 A223914

KEYWORD

nonn

AUTHOR

Joerg Arndt, Mar 29 2013, using information provided by Joel B. Lewis, M. F. Hasler and Michel Marcus in A006860.

EXTENSIONS

Added a(0) = 1 by Alois P. Heinz, Jul 23 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 15 20:07 EST 2019. Contains 320138 sequences. (Running on oeis4.)