2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

This is not an answer, but it's a bit too long for a comment. Besides, maybe bumping on the front page helps you or this gives someone more competent an idea.

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$.

In your example above, the corresponding sums are

\begin{align*} x = 4 &= 3+1+0 = 3+0+1 = 2+2+0 = 2+1+1 = 2+0+2 = 1+3+0 \\ &= 1+2+1 = 1+1+2 = 1+0+3 = 0+3+1 = 0+2+2 = 0+1+3. \end{align*}

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$.

Unfortunately, I don't know enough combinatorics to tackle this. Try to start from the Wikipedia link above (especially a generating function and how to apply restrictions to it), and see if somebody has done something similar enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.