OFFSET
0,7
COMMENTS
The labeled case for at least k=2 elements per rank is given by A032032 = Partition n labeled elements into sets of sizes of at least 2 and order the sets. The unlabeled case for at least k=3 elements per rank is given by A000930 = A Lamé sequence of higher order. The unlabeled case for at least k=2 elements per rank is given by A000045 = Fibonacci numbers.
With m = floor(n/3), a(n) is the number of ways to distribute n different toys to m numbered children such that each child receiving a toy gets at least three toys and, if child k gets no toys, then each child numbered higher than k also gets no toys. Furthermore, a(n)= row sums of triangle A200092 for n>=3. - Dennis P. Walsh, Apr 15 2013
Row sums of triangle A200092. - Dennis P. Walsh, Apr 15 2013
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..400
Vladimir Kruchinin, D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and J. Int. Seq. 17 (2014) #14.1.1.
FORMULA
E.g.f.: 1-(z^2-2*exp(z)+2+2*z)/(4-2*exp(z)+2*z+z^2).
a(n) = n! * sum(m=1..n, sum(k=0..m, k!*(-1)^(m-k) *binomial(m,k) *sum(i=0..n-m, stirling2(i+k,k) *binomial(m-k,n-m-i) *2^(-n+m+i) /(i+k)!))); a(0)=1. - Vladimir Kruchinin, Feb 01 2011
a(n) ~ 2*n!/((2+r^2)*r^(n+1)), where r = 1.56811999239... is the root of the equation 4+2*r+r^2 = 2*exp(r). - Vaclav Kotesovec, Sep 29 2013
a(0) = 1; a(n) = Sum_{k=3..n} binomial(n,k) * a(n-k). - Ilya Gutkovskiy, Feb 09 2020
EXAMPLE
Let 1,2,3,4,5,6 denote six labeled elements. Let | denote a separation between two ranks. E.g., if elements 1,2 and 3 are on rank (also called level) one and elements 3,4 and 5 are on rank two, then we have the ranking 123|456.
For n=9 we have a(9)=2101 rankings. The order within a rank does not count. Six examples are: 123|456|789; 123456789; 12345|6789; 129|345678; 1235|46789; 789|123456.
MAPLE
seq (n! *coeff (series (1- (z^2-2*exp(z)+2+2*z) /(4-2*exp(z)+2*z+z^2), z=0, n+1), z, n), n=0..30);
with(combstruct): SeqSetL := [S, {S=Sequence(U), U=Set(Z, card >= 3)}, labeled]: seq(count(SeqSetL, size=j), j=0..23); # Zerinvary Lajos, Oct 19 2006
# third Maple program:
b:= proc(n) b(n):= `if`(n=0, 1, add(b(n-j)/j!, j=3..n)) end:
a:= n-> n!*b(n):
seq(a(n), n=0..30); # Alois P. Heinz, Jul 29 2014
MATHEMATICA
CoefficientList[Series[1-(x^2-2*E^x+2+2*x)/(4-2*E^x+2*x+x^2), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Sep 29 2013 *)
b[n_] := b[n] = If[n==0, 1, Sum[b[n-j]/j!, {j, 3, n}]]; a[n_] := n!*b[n]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)
PROG
(PARI) z='z+O('z^66); Vec(serlaplace( 1-(z^2-2*exp(z)+2+2*z) / (4-2*exp(z)+2*z+z^2) ) ) \\ Joerg Arndt, Apr 16 2013
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Wieder, Jan 01 2005
EXTENSIONS
a(0) changed to 1 at the suggestion of Zerinvary Lajos, Oct 26 2006
STATUS
approved