Combinatorial selection with constraints

Question

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?

kglr · Accepted Answer

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

Simon Woods · Answer

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

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

JimB · Answer

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, {"Onlynsing", "Sing &ndance", "Onlyndance"}},
  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 *)

Combinatorial selection with constraints

3 Answers

Add your own answers!

Ask a Question