Problem
I have eight objects {a,b,c,d,e,f,g,h} that I wish to place into some number of bins, such that:
- every bin has at least two objects
- all the objects are in a bin
Furthermore, within each bin, the order of the objects matters e.g. {a,b,c} and {a,c,b} are two different assignments. However, circular permutations are not distinct, e.g. {a,b,c} and {c,a,b} should be considered one assignment.
How many ways may this be done?
My reasoning so far
First off I want to say I'm approaching this in a naive way with only a little knowledge of combinatorics.
There are 7 possible groups of bins (i.e. 4 bins of two, 1 bin of eight etc.):
[2,2,2,2], [2,2,4], [2,3,3], [2,6], [4,4], [5,3], and [8] in this notation I just made up.
Starting from the largest bin in each group, there are $8 \choose k$ ways to select the objects to go inside the bin, where $k$ is the size of the bin. There are additionally $(k-1)!$ ways to arrange the objects such that circular permutations are correctly treated.
This process is repeated for the remaining bins using ${{8- \sum_{i=1}^{j-1} k_{i}} \choose k_j} (k_j-1)!$, where $k_j$ is the size of the $j^{th}$ bin. All of the numbers are multiplied together to get the total number of assignments for each group. Symbolically,
$$ \prod_{m=1}^n {{8- \sum_{i=1}^{j-1} k_{m,i}} \choose k_{m,j}} (k_{m,j} – 1)! $$
where $n$ is the number of bins in a particular group.
After doing the computations and summed across all the groups I came up with 20,888 different ways to solve the task. Have I done this correctly? I've started to second guess myself.
Thank you
Edit: Thinking about it some more I believe I also need to divide by the multiplicities in each group of bins.
Best Answer
As stated by the commenter my solution is simply the number of derangements of size 8, which is 14833. This corresponds with the result I obtained from applying my formula naively. Thanks, I learned something new from this problem.