# Combinations for a collection which should hold x items, where there are y types and z of each type

This is related to this question, but I plan on writing a more clear question, using smaller numbers for examples, and I want to understand how to approach the problem rather than having an answer for one case.

### Example

Let's say that you have three different types of items, for simplicity sake let's call the them a b c. You have three of each type. And you want to create a collection holding four items in total. So you have aaabbbccc and you should pick 4 of them.

9 nCr 4 is not the correct answer since it doesn't matter which a, which b or which c you pick. All that matters is how many. The number of possible combinations is 12, the possible combinations are: aaab, aaac, aabb, aabc, aacc, abbb, abbc, abcc, accc, bbbc, bbcc, bccc.

### My current approach

Since I am a programmer, I wrote a method in Java for determining this. It uses recursion to compute the correct number. So if you know programming, here is what I have done:

public int deckCombos(int cardsInDeck, int numCardTypes, int numOfEachType) {
if (cardsInDeck < 0)
return 0;
if (cardsInDeck == 1)
return numCardTypes;
if (numCardTypes == 1)
return numOfEachType >= cardsInDeck ? 1 : 0;

int result = 0;
for (int i = 0; i <= numOfEachType; i++) {
result += deckCombos(cardsInDeck - i, numCardTypes - 1, numOfEachType);
}
return result;
}


The problem of this approach is that when dealing with bigger numbers it gets slower, because of all the recursion.

### Other attempts at solving the general problem

There has to be a lot of combinatorics here. I figured that for the example above, there are 9 items in total and so there are 9! ways of ordering them. Since there are 3 of each type we can divide by 3! three times.

But then we should also pick 4 of them, but when dividing by 4! (because the order of the first four elements doesn't matter) and 5! (because the order of the last 5 elements doesn't matter).

The result then becomes 7/12 which is obviously wrong since 0.58333 combinations just doesn't make sense. I understand this is because when dividing by both 3! and 5!, some combinations are removed twice.

# The question

How can I calculate mathematically (or in a faster programmatically way) the number of combinations when wanting to choose x items in total when having y types of items and z items of each type?

You actually need partitions with the constraints: maximal number that can be used is $z$ and the number of the summands should be at most $y$.
So, $3$ summands ($y = 3$, corresponding to "a", "b", and "c"), all less than or equal to $3$ (because you have $z = 3$ of each) and the sum is $x=4$.