|
| |
|
|
A200091
|
|
The number of ways of putting n labeled items into k labeled boxes so that each box receives at least 2 objects.
|
|
7
|
|
|
|
1, 1, 1, 6, 1, 20, 1, 50, 90, 1, 112, 630, 1, 238, 2940, 2520, 1, 492, 11508, 30240, 1, 1002, 40950, 226800, 113400, 1, 2024, 137610, 1367520, 2079000, 1, 4070, 445896, 7271880, 22869000, 7484400, 1, 8164, 1410552, 35692800, 196396200, 194594400, 1, 16354
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,4
|
|
|
COMMENTS
|
Equivalently, the number of ordered set partitions of the set [n] into k blocks of size at least two. When the boxes are unlabeled or the set partitions unordered we obtain A008299.
The number of doubly-surjective functions f:[n]->[k], where a doubly-surjective function f has pre-image sets of size at least 2 for each element of the codomain. Also, the number of ways to distribute n different toys to k different children so that each child gets at least two toys. - Dennis P. Walsh, Apr 09 2013
T(n,k) is the number of chains 0 = x_0 < x_1 < ... < x_k = 1 in the Boolean lattice of rank n, such that x_i is not covered by x_(i+1) for all i. - Geoffrey Critzer, Jul 15 2018
|
|
|
REFERENCES
|
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, page 100-109.
|
|
|
LINKS
|
|
|
|
FORMULA
|
E.g.f. with additional 1: 1/(1-t*(exp(x)-1-x)) = 1 + t*x^2/2! + t*x^3/3! + (t+6*t^2)*x^4/4! + ....
Recurrence relation: T(n+1,k) = k*(T(n,k) + n*T(n-1,k-1)). T(n,k) = k!*A008299(n,k).
T(n,k+j) = Sum_{i=0..n} C(n,i)*T(i,k)*T(n-i,j). - Dennis P. Walsh, Apr 09 2013
T(n,k) = Sum_{j=0..k} (-1)^j*C(k,j)*(Sum_{i=0..j} C(j,i)*C(n,i)*i!*(k-j)^(n-i)) for 1 <= k <= n/2 and n >= 2. - Dennis P. Walsh, Apr 10 2013
T(n,k) = k!*Sum_{r=0..min(n,k)} binomial(n,r)*(-1)^r*Stirling2(n-r, k-r). - Marko Riedel, Mar 25, 2022
|
|
|
EXAMPLE
|
Table begins
n |k=1 2 3 4
----+-------------------
2 | 1
3 | 1
4 | 1 6
5 | 1 20
6 | 1 50 90
7 | 1 112 630
8 | 1 238 2940 2520
9 | 1 492 11508 30240
...
T(4,2) = 6: The arrangements of 4 objects into 2 boxes { } and [ ] so that each box contains at least 2 items are {1,2}[3,4], {1,3}[2,4], {2,3}[1,4] and the 3 other possibilities where the contents of a pair of boxes are swapped.
|
|
|
MAPLE
|
seq(seq(eval(diff((exp(x)-x-1)^k, x$n), x=0), k=1..floor(n/2)), n=2..20); # Dennis P. Walsh, Apr 09 2013
T := proc(n, k) local r; k!* add(binomial(n, r)*(-1)^r*Stirling2(n-r, k-r), r=0..min(n, k)); end; # Marko Riedel, Mar 25, 2022
|
|
|
MATHEMATICA
|
t[n_, k_] := k! * Sum[ (-1)^i*Binomial[n, i] * Sum[ (-1)^j*(k - i - j)^(n - i) / (j!*(k - i - j)!), {j, 0, k - i}], {i, 0, k}]; Table[ t[n, k], {n, 2, 14}, {k, 1, n/2}] // Flatten (* Jean-François Alcover, Apr 10 2013 *)
|
|
|
PROG
|
(GAP) Flat(List([2..14], n->List([1..Int(n/2)], k->Sum([0..k], j->(-1)^j*Binomial(k, j)*(Sum([0..j], i->Binomial(j, i)*(Binomial(n, i)*Factorial(i)*(k-j)^(n-i)))))))); # Muniru A Asiru, Jul 17 2018
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
