%I #78 Nov 17 2023 07:34:52

%S 1,0,1,1,7,21,141,743,5699,42241,382153,3586155,38075247,428102117,

%T 5257446533,68571316063,959218642651,14208251423433,223310418094785,

%U 3699854395380371,64579372322979335,1182959813115161773,22708472725269799933,455643187943171348103

%N Number of ways to partition n labeled elements into sets of sizes of at least 2 and order the sets.

%C From _Dennis P. Walsh_, Apr 15 2013: (Start)

%C 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.

%C a(n) = sum of n-th row of triangle A200091 for n >= 2. (End)

%H Alois P. Heinz, <a href="/A032032/b032032.txt">Table of n, a(n) for n = 0..400</a>

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see p. 245.

%H I. Mezo, <a href="http://arxiv.org/abs/1308.1637">Periodicity of the last digits of some combinatorial sequences</a>, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezo/mezo19.html">J. Int. Seq. 17 (2014) #14.1.1</a>.

%H Robert A. Proctor, <a href="https://arxiv.org/abs/math/0606404">Let's Expand Rota's Twelvefold Way For Counting Partitions!</a>, arXiv:math/0606404 [math.CO], 2006-2007.

%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>

%F "AIJ" (ordered, indistinct, labeled) transform of 0, 1, 1, 1...

%F E.g.f.: 1/(2+x-exp(x)).

%F 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

%F a(n) ~ n! / ((r-1)*(r-2)^(n+1)), where r = -LambertW(-1,-exp(-2)) = 3.14619322062... - _Vaclav Kotesovec_, Oct 08 2013

%F a(0) = 1; a(n) = Sum_{k=2..n} binomial(n,k) * a(n-k). - _Ilya Gutkovskiy_, Feb 09 2020

%F 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

%e 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

%e |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

%p spec := [ B, {B=Sequence(Set(Z,card>1))}, labeled ]; [seq(combstruct[count](spec, size=n), n=0..30)];

%p # second Maple program:

%p b:= proc(n) b(n):= `if`(n=0, 1, add(b(n-j)/j!, j=2..n)) end:

%p a:= n-> n!*b(n):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Jul 29 2014

%t 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 *)

%o (PARI) x='x+O('x^66); Vec(serlaplace( 1/(2+x-exp(x)) ) ) \\ _Joerg Arndt_, Apr 16 2013

%Y Cf. A102233, A232475.

%Y Cf. column k=2 of A245732.

%Y Cf. A200091.

%K nonn

%O 0,5

%A _Christian G. Bower_