Enumerate the possible combinations

Question

We have three windows of opportunity, say W1, W2, W3. And we have 4 competitors, say, C1, C2, C3, C4.

Each competitor wants to be allocated at least two windows (so will get either 2 or all 3). Each window can be allocated to any number of competitors (so, from 1 to 4; or even 0 to 4 if that makes much difference).

The question is to enumerate all possible allocations of the windows to the competitors, if I do not want to differentiate amongst the windows themselves. (so, e.g., the allocation [(C1,C2,C3); (C2,C3,C4); (C3,C4,C1)] is considered identical to the allocation [(C2,C3,C4); (C3,C4,C1); (C1,C2,C3)])

If I did want to distinguish amongst the windows, it should be easy to list all combinations: Basically each competitor can be placed in 4 ways (it can go in 2 of the 3 windows (3C2=3 ways), or in all 3 windows (1 way)), so total combinations should be 256. But how to enumerate the "unique" ones here (which do not distinguish amongst the windows) without doing it manually by comparing ?

Answer 1

• If all three windows are the same then everybody must be in all three windows, so $1$ undistinguished-windows possibility and $1$ distinguished-windows possibility

• If two of the windows are the same then everybody must be in those two windows but not all will be in the other window, so $2^4-1=15$ undistinguished-windows possibilities and ${3\choose 2}\times 15 = 45$ distinguished-windows possibilities

• For all three windows different there are $256-1-45=210$ distinguished-windows possibilities and so $\frac{210}{3!} =35$ undistinguished-windows possibilities

That gives $1+15+35=51$ undistinguished-windows possibilities in total

---

Added: We could have counted these $35$ for all three windows different from the bottom up:

• If each number appears two times then the window sizes will be $4+3+1$ with ${4 \choose 1}=4$ ways of choosing the one, or $4+2+2$ with ${4 \choose 2}/2!=3$ ways of choosing the pairs, or $3+3+2$ with ${4 \choose 2}=6$ ways of choosing the pairs, so $4+3+6=13$ ways

• If one number appears three times and the others twice then the window sizes will be $4+3+2$ with ${4 \choose 1}{3 \choose 2}=12$ ways of choosing the one appearing three times and splitting the others, or $3+3+3$ with ${4 \choose 1}=4$ ways of choosing the one appearing three times, so $12+4=16$ ways

• If two numbers appear three times and the others twice then the window sizes will be $4+3+3$ with ${4 \choose 2}=6$ ways of choosing the two appearing three times

and $13+16+6=35$ as calculated earlier.

Whether this is easier than a full enumeration is another question. That enumeration of $51$ could have been:

1234    1234    1234

1234    1234    123
1234    1234    124
1234    1234    12
1234    1234    134
1234    1234    13
1234    1234    14
1234    1234    1
1234    1234    234
1234    1234    23
1234    1234    24
1234    1234    2
1234    1234    34
1234    1234    3
1234    1234    4
1234    1234    -

1234    123     4
1234    124     3
1234    134     2
1234    234     1
1234    12      34
1234    13      24
1234    14      23
123     124     34
123     134     24
123     234     14
124     134     23
124     234     13
134     234     12

1234    123     14
1234    124     13
1234    134     12
1234    123     24
1234    124     23
1234    234     12
1234    123     34
1234    134     23
1234    234     13
1234    124     34
1234    134     24
1234    234     14
123     124     134
123     124     234
123     134     234
124     134     234

1234    123     124
1234    123     134
1234    124     134
1234    123     234
1234    124     234
1234    134     234

Answer 2

Well, if we don't distinguish between "types" of window, each competitor can have either 2 or 3 allotted windows, which is exactly two choices, so the number of possible outcomes is $2^4 = 16$.