How to compute number of combinations with placement restrictions There are five buckets labeled 0 (AC), 1 (AB), 2 (AC), 3 (BC), 4 (BC), as well as four marbles of type A, A, C, C. Marbles may only fit in a bucket that includes it's type (i.e. A can go into AC or AB, but not into BC). Each bucket can only hold 1 marble.
In how many different ways can I place the marbles in the buckets?
I solved this problem manually by listing all the possible combinations (7):
0-A, 1-A, 2-C, 3-C
0-A, 1-A, 3-C, 4-C
0-A, 1-A, 2-C, 4-C
0-A, 2-A, 3-C, 4-C
1-A, 2-A, 0-C, 3-C
1-A, 2-A, 0-C, 4-C
1-A, 2-A, 3-C, 4-C
How can I mathematically (perhaps using combinatorics) arrive at this answer? I have to deal with considerably more complex problems where listing out the solutions is not feasible.
 A: The interlocking conditions make this hard to do systematically.  I would start with the As.  If they go in bins $0,2$, the Cs only have one choice.  If they go in bin $1$ and either of the others ($2$ ways) the Cs have ${3 \choose 2}=3$ choices, so the total is $1 \cdot 1 + 2 \cdot 3=7$
A: There are two generic ways to do this.  Dynamic programming, and Inclusion-Exclusion.  If you have several of these to do, I would personally take the programming approach because I know how to.
Dynamic programming would require that you write a program that walks through the buckets and produces.  For each bucket you would construct a data structure from the vector of remaining marbles to how many ways you could have arrived at it.  The answer for no remaining marbles at the end is your answer.
The equivalent to dynamic programming can also be done with a top-down recursive function with memoization to speed it up.  This may be easier if you know how to program but haven't done dynamic programming before.
As for https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle the approach is to count the number of ways to place with possibly multiple, subtract off ways to place with at least one bucket with 2, add ways to place with at least 2 buckets, subtract ones with at least 3, and so on.  In this case:


*

*possibly multiple: ${3\choose 2} {4 \choose 2} = 18$ (put 2 A's in 3 buckets, 2 C's in 4 buckets)

*at least 1: ${2 \choose 1} {2 \choose 1} {3 \choose 1} = 12$ (choose the multiple bucket, place remaining A in choice of 2 places, remaining C in choice of 3 places)

*At least 2: ${2 \choose 2} {1 \choose 0} {2 \choose 0} = 1$ (choose both multiple buckets, place no remaining A's and B's anywhere.

*All higher terms: there is no way to generate more collisions than 2, so they are all 0.


So we get $18 - 12 + 1 = 7$.
Note that as you get to more complex cases, inclusion-exclusion will have more and more terms.  In fact in general you'd want a program to figure it out...which is why I'd write the program first. :-)
