OFFSET
0,5
COMMENTS
From Dennis P. Walsh, Apr 15 2013: (Start)
With m = floor(n/2), 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 two toys and, if child k gets no toys, then each child numbered higher than k also gets no toys.
a(n) = sum of n-th row of triangle A200091 for n >= 2. (End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..400
C. G. Bower, Transforms (2).
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see p. 245.
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.
Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
FORMULA
"AIJ" (ordered, indistinct, labeled) transform of 0, 1, 1, 1...
E.g.f.: 1/(2+x-exp(x)).
a(n) = n! * Sum_{k=1..n} Sum_{j=0..k} C(k,j) * Stirling2(n-k+j,j) * (j!/(n-k+j)!) *(-1)^(k-j); a(0)=1. - Vladimir Kruchinin, Feb 01 2011
a(n) ~ n! / ((r-1)*(r-2)^(n+1)), where r = -LambertW(-1,-exp(-2)) = 3.14619322062... - Vaclav Kotesovec, Oct 08 2013
a(0) = 1; a(n) = Sum_{k=2..n} binomial(n,k) * a(n-k). - Ilya Gutkovskiy, Feb 09 2020
a(n) = Sum_{s in S_n^0} Product_{i=1..n} binomial(i,s(i)-1), where s ranges over the set S_n^0 of derangements of [n], i.e., the permutations of [n] without fixed points. - Jose A. Rodriguez, Feb 02 2021
EXAMPLE
For n=5, a(5)=21 since there are 21 toy distributions satisfying the conditions above. Denoting a distribution by |kid_1 toys|kid_2 toys|, we have the distributions
|t1,t2,t3,t4,t5|_|, |t1,t2,t3|t4,t5|, |t1,t2,t4|t3,t5|, |t1,t2,t5|t3,t4|, |t1,t3,t4|t2,t5|, |t1,t3,t5|t2,t4|, |t1,t4,t5|t2,t3|, |t2,t3,t4|t1,t5|, |t2,t3,t5|t1,t4|, |t2,t4,t5|t1,t3|, |t3,t4,t5|t1,t2|, |t1,t2|t3,t4,t5|, |t1,t3|t2,t4,t5|, |t1,t4|t2,t3,t5|, |t1,t5|t2,t3,t4|, |t2,t3|t1,t4,t5|, |t2,t4|t1,t3,t5|, |t2,t5|t1,t3,t4|, |t3,t4|t1,t2,t5|, |t3,t5|t1,t2,t4|, and |t4,t5|,t1,t2,t3|. - Dennis P. Walsh, Apr 15 2013
MAPLE
spec := [ B, {B=Sequence(Set(Z, card>1))}, labeled ]; [seq(combstruct[count](spec, size=n), n=0..30)];
# second Maple program:
b:= proc(n) b(n):= `if`(n=0, 1, add(b(n-j)/j!, j=2..n)) end:
a:= n-> n!*b(n):
seq(a(n), n=0..25); # Alois P. Heinz, Jul 29 2014
MATHEMATICA
a[n_] := n! * Sum[ Binomial[k, j] * StirlingS2[n-k+j, j]*j! / (n-k+j)! * (-1)^(k-j), {k, 1, n}, {j, 0, k}]; a[0] = 1; Table[a[n], {n, 0, 22}] (* Jean-Fran�ois Alcover, Sep 05 2012, from given formula *)
PROG
(PARI) x='x+O('x^66); Vec(serlaplace( 1/(2+x-exp(x)) ) ) \\ Joerg Arndt, Apr 16 2013
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved