A200092 The number of ways of putting n labeled items into k labeled boxes so that each box receives at least 3 objects.

1, 1, 1, 1, 20, 1, 70, 1, 182, 1, 420, 1680, 1, 912, 12600, 1, 1914, 62370, 1, 3938, 256410, 369600, 1, 8008, 949806, 4804800, 1, 16172, 3297294, 38678640, 1, 32526, 10966956, 248047800, 168168000

Offset

3,5

Comments

Equivalently, the number of ordered set partitions of the set [n] into k blocks of size at least three. When the boxes are unlabeled we obtain A059022.

Links

Table of n, a(n) for n=3..37.

Formula

E.g.f. with additional constant 1: 1/(1 - t*(exp(x) - 1 - x - x^2/2!)) = 1 + t*x^3/3! + t*x^4/4! + t*x^5/5! + (t+20*t^2)*x^6/6! + ....

Recurrence relation: T(n+1,k) = k*(T(n,k) + n*(n-1)/2*T(n-2,k-1)). T(n,k) = k!*A059022(n,k).

Example

Table begins
  n\k |  1     2       3
  ----+-----------------
   3  |  1
   4  |  1
   5  |  1
   6  |  1    20
   7  |  1    70
   8  |  1   182
   9  |  1   420    1680
  10  |  1   912   12600
  11  |  1  1914   62370
  ...
T(6,2) = 20: The arrangements of 6 objects into 2 boxes { } and [ ] so that each box contains at least 3 items are {1,2,3}[4,5,6], {1,2,4}[3,5,6], {1,2,5}[3,4,6], {1,2,6}[3,4,5], {1,3,4}[2,5,6], {1,3,5}[2,4,6], {1,3,6}[2,4,5], {1,4,5}[2,3,6], {1,4,6}[2,3,5], {1,5,6}[2,3,4] and the 10 other possibilities where the contents of a pair of boxes are swapped.

Crossrefs

Cf. A019538, A059022, A200091.

Sequence in context: A141589 A162153 A040419 * A164812 A332258 A327023

Adjacent sequences: A200089 A200090 A200091 * A200093 A200094 A200095

Keyword

nonn,easy,tabf

Author

Peter Bala, Dec 04 2011

Status

approved