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

1, 0, 1, 1, 7, 21, 141, 743, 5699, 42241, 382153, 3586155, 38075247, 428102117, 5257446533, 68571316063, 959218642651, 14208251423433, 223310418094785, 3699854395380371, 64579372322979335, 1182959813115161773, 22708472725269799933, 455643187943171348103

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.

Index entries for related partition-counting sequences

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

Cf. A102233, A232475.

Cf. column k=2 of A245732.

Cf. A200091.

Sequence in context: A061961 A028248 A267609 * A084711 A183938 A060146

Adjacent sequences: A032029 A032030 A032031 * A032033 A032034 A032035

Keyword

nonn

Author

Christian G. Bower

Status

approved