Groups or combinations of permutations (i.e. make a pair of pairs) without repeat/using existing

Question

I am struggling to phrase this as much as I am in calculating it.

Alice
Bob
Carol
Dan

All the combinations of their groups, are 15, since I have 4 singles, 6 doubles, 4 triples and 1 quad. I care about the order (in my unique way), so my total is actually 32, since I have 4 singles, 12 doubles, 12 triples and 4 quads.

The math for this part, I have so far is (before optimizing):

${4\choose 1}*1+{4\choose 2}*2+{4\choose 3}*3+{4\choose 4}+4=32$

I am looking for how to generate a pair of pairs, i.e.:

(Alice + Bob) with (Carol + Dan)
(Alice + Carol) with (Bob + Dan)
(Alice + Dan) with (Bob + Carol)

Note that if Alice dances with Bob, she cannot also dance with Carol at the same time.

In these, the order does not matter. The total should be 3 new combinations, but since each has a permutation, each has a result of 4 permutations, so another 12 total.

The total here for a case of 4 people, are 44 potential groups, which include double pairs.

How to I get the total for 5 people / X people?

EDIT: Within my search for the "all possible combinations of all possible groups with leaders in each group" note that for 5 people, we also have:

"two pairs"
(A + B) with (C + D) and E 

and

"a pair and a triple"
(A + B + C) with (D + E)

Answer 1

Given $X\ge 2$ people, we can form $x=\lfloor X/2\rfloor$ pairs, so there are $x$ pair leaders. There are ${X\choose x}$ feasible sets of leaders. For each of these sets there are $(X-x)!$ feasible sets or pairs with given leaders. Indeed, let $l_1,\dots, l_x$ be the leaders. Then there is a bijective correspondence between permutations of non-leaders and feasible sets or pairs with given leaders. Namely, to a permutation $(n_1,\dots,n_{X-x})$ corresponds a set $(l_1,n_1),\dots, (l_x,n_x)$ of pairs.

Answer 2

For the case of one group, there's a nice general identity, $$ \sum_{k=1}^n k \binom{n}{k} = n2^{n-1}$$ which has a combinatorial proof: For the left-hand side, for group size $k$, choose $k$ of the $n$ people, then there are $k$ choices for the leader. For the right-hand side, first pick a leader among the $n$ people, then choose the (possibly empty) rest of the group from the other $n-1$ people; there are $2^{n-1}$ ways to do that. (If you don't know that last part, think of going down the list of the $n-1$ people are choosing in or out for each one, so that a (possibly empty) group comes from making $n-1$ binary decisions.) This matches your $4\cdot2^3 = 32$ count for one group-with-leader from four people.

For the rest, it seems you want to count multiple groups each with at least two dancers. (By the way, I think committees with chairs may be a preferable metaphor.) This gets trickier. For four people, that adds $$ \frac{2 \binom{4}{2} \cdot 2 \binom{2}{2}}{2} = 12$$ groups, as you worked out. Dividing by two occurs because the order of the pairs doesn't matter: $\{A,D\}, \{B, C\}$ and $\{B,C\}, \{A,D\}$, counted separately in $\binom{4}{2} \binom{2}{2}$, are indistinguishable in the application. (Putting in $\binom{2}{2}$ for counting the way to choose two of the remaining two people may seem pedantic, but you'll see next why I want to include it.)

For five people, two pairs works the same way: $$ \frac{2 \binom{5}{2} \cdot 2 \binom{3}{2}}{2} = 60.$$ For the other two-group possibility, a triple and a pair, it's $$ 3 \binom{5}{3} \cdot 2 \binom{2}{2} = 60.$$ Why is there no diving by 2 here? Because, unlike two pairs, a triple & a pair are distinguishable. This gives a grand total of $ 5\cdot2^4 + 60 + 60 = 200$ of your possible groups for five people.

For good measure, for six people, you can have one group; two pairs, a pair & a trio, a pair & a quad, two trios; and (if you want) three pairs (last term below) giving $$ 6\cdot2^5 + \frac{2 \binom{6}{2} \cdot 2 \binom{4}{2}}{2} + 3 \binom{6}{3} \cdot 2 \binom{3}{2} + 4 \binom{6}{4} \cdot 2 \binom{2}{2} + \frac{3 \binom{6}{3} \cdot 3 \binom{3}{3}}{2} + \frac{2 \binom{6}{2} \cdot 2 \binom{4}{2} \cdot 2 \binom{2}{2}}{6}$$
which works out to 1062. (The last term is divided by $3! = 6$ since the same three pairs arise six times.)