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);
}
(PARI) \\ here f(m, n) is A218695.
f(m, n) = {sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n )}
seq(n)={my(N=matrix(n, n, i, j, f(i, j)), T=vector(n), v=vector(n+1)); v[1]=1; for(r=1, n, T[r]=vector(r, k, (r==k) + binomial(r, k)*sum(i=1, r-k, T[r-k][i]*N[i, k])); v[1+r]=vecsum(T[r])); v} \\ Andrew Howroyd, Mar 29 2023
CROSSREFS
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