# Combinatorial selection with constraints

Five of the 10 actors can only sing, two can only dance, and three can both sing and dance. Now, how many kinds of selection methods are there to perform a program that requires two people to dance and two people to sing?

Select[Map[Flatten,
Subsets[Table[{"sing"}, 5]~Join~Table[{"dance"}, 2]~Join~
Table[{"sing", "dance"}, 3], {4}], {1}],
Count[#, "sing"] >= 2 && Count[#, "dance"] >= 2 &] // Length


The result of using the above method is 155, but the reference answer is 199(Binomial[3, 2] Binomial[3, 2] + Binomial[5, 1] Binomial[3, 1] Binomial[4, 2] + Binomial[5, 2] Binomial[5, 2]).

How can I list all the possible combinations correctly?

• When you ask these questions I think you need to be more specific. Some examples: Do you want exactly two people to dance and exactly two people to sing? Or is it at least two people to dance and at least two people to sing? Is there a restriction on the number of people in a program. Clearly one needs at least two people but do you need at least 4 people (two singers and two dancers)? – JimB Feb 19 at 17:53
• @JimB Your answer is also great. You don't have to delete your answer. I'll just choose someone else's answer. – A little mouse on the pampas Feb 21 at 1:34

lsts = Join[Thread[{Range[8], "sing"}], Thread[{Range[6, 10], "dance"}]];

Length @
Select[
Count[Last /@ #, "sing"] == 2 &&
Count[Last /@ #, "dance"] == 2 &&
CountDistinct[First /@ #] == 4 &] @
Subsets[lsts, {4}]

199

singerpairs = Subsets[Range[1, 8], {2}]
dancerpairs = Subsets[Range[6, 10], {2}]

Count[Union @@@ Tuples[{singerpairs, dancerpairs}], {_, _, _, _}]
(* 199 *)


I'm going to argue that the count of 155 is alternative number of unique 4-person ensembles such that at least 2 persons can sing and at least 2 persons can dance.

In short, the methods resulting in 199 ensembles have duplicates. For example, the ensemble {{4,7},{6,10}} is also included in the 199 as {{4,6},{7,10}}. Those two form an identical ensemble {4,6,7,10} and therefore should be counted only once. (Yes, this ignores the assignment of who is dancing and who is singing.)

To borrow heavily from @SimonWoods:

singerpairs = Subsets[Range[1, 8], {2}]
dancerpairs = Subsets[Range[6, 10], {2}]

ensembles = Select[Union @@@ Tuples[{singerpairs, dancerpairs}], Length[#] == 4 &];
Length @ %
(* 199 *)


But now the duplicates need to be removed:

ensembles = Sort[#] & /@ ensemble // DeleteDuplicates;
Length @ %
(* 155 *)


If listing ensembles is of interest and the total number of ensembles is manageable, then code variations of the above with the deleting of the duplicates is reasonable. If the number of ensembles is very large and only the total number of ensembles is needed, then a bit of thinking is needed to write down a formula for the total count.

Here there is just a small number of possible selections from each group (only sing, sing and dance, and only dance) that need enumerating:

counts = {{2, 2, 0}, {2, 1, 1}, {2, 0, 2}, {1, 3, 0}, {1, 2, 1}, {1, 1, 2}, {0, 3, 1}, {0, 2, 2}}
TableForm[counts, TableHeadings -> {None, {"Only\nsing", "Sing &\ndance", "Only\ndance"}},
TableAlignments -> Center]


Then applying the sum of the products of 3 binomial coefficients is needed:

Binomial[5, #[[1]]] Binomial[3, #[[2]]] Binomial[2, #[[3]]] & /@ counts // Total
(* 155 *)

• If you want only the unique ensembles, it's probably more efficient to create the length 4 subsets directly: Count[Subsets[{s, s, s, s, s, d, d, sd, sd, sd}, {4}], {OrderlessPatternSequence[s | sd, s | sd, d | sd, d | sd]}] – Simon Woods Feb 20 at 15:44
• Or more compactly, by ordering the input list to put all singers first: Count[Subsets[{s, s, s, s, s, sd, sd, sd, d, d}, {4}], Except /@ {d, d, s, s}] – Simon Woods Feb 20 at 15:57