How many ways to arrange m chosen objects when there are n total objects, and some are indistinguishable?

Question

I have $n$ different types of objects, where each member of a type is indistinguishable from every other member.

There are $k_1$ of the first type, $k_2$ of the second type, and so on, up to $k_n$ of the $n$th type.

I want to choose only a few of these objects, call it $m$, where $m \le \sum\limits_{i=1}^{n}k_i$.

In the case where $m = \sum\limits_{i=1}^{n}k_i$, the formula is $\frac{m!}{k_1!k_2!...k_n!}$

What is the formula if I don't take all the objects? Rather, $m$ is strictly less than $\sum\limits_{i=1}^{n}k_i$

EDIT: I've tried to think of it in a straightforward way, like the derivation of the formula I gave. There's a nice explanation on another question here: Combination and permutation of indistinguishable objects.

But I always run into problems with the fact that the amount of each type is fixed and could not be used in its entirety. Most recently, I've been trying to think of it like putting $m$ objects in $n$ boxes, where the boxes have different maximum capacities. I keep getting stuck there too.

Answer 1

I have since taken a combinatorics course and decided to share what I learned.

You use generating functions. First, examine the case where the order the objects are chosen does not matter. If you have 3 red objects, 5 green objects, and 4 blue objects, we can represent the question as a polynomial, specifically

$(1+x+x^2+x^3)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4)$

where the first factor represents the red objects, the second represents the green, and the third represents the blue. After multiplying out the polynomial and combining like terms, simply look at the coefficient of the correct term. If you wanted to know how many ways to choose $n$ objects, you would look at the coefficient of the $x^n$ term. In this example, the expanded then simplified polynomial is

$1+3x+6x^2+10x^3+14x^4+17x^5+18x^6+17x^7+14x^8+10x^9+6x^{10}+3x^{11}+x^{12}$

So if we want to know how many ways to pick 6 objects where the order of the objects doesn't matter, we would look at the $x^6$ coefficient, which is 18 in this case.

Notice that the coefficient of $x^{12}$ is 1. This makes sense because choosing twelve chooses all the objects, and since order is irrelevant, only one way exists, i.e. choosing all of them. In general this method works because when you multiply the polynomial, you are getting all the possible ways to add up to each degree. So for $x^6$, we are seeing the instance where there are 3 reds, 3 greens, and 0 blues (multiply the $x^3$ term from the reds, the $x^3$ term from the greens, and the 1 term from the blues) which is added to the case where there are two of each (multiplying the $x^2$ term from each factor), which is added to all the other possible ways to add up to 6 using the numbers at hand.

For the general process asked for in the question, look for the coefficient of $x^m$ in the polynomial

$(1+x+x^2+...+x^{k_1})(1+x+x^2+...+x^{k_2})(1+x+x^2+...+x^{k_3})...(1+x+x^2+...+x^{k_n})$

For the case where order matters, which was what the question really asked for, you use an exponential generating function. The main difference is that every $x^n$ is divided by $n!$ (so each term looks like $\frac{x^n}{n!}$). You also look at the coefficient of $\frac{x^m}{m!}$It's just like the first example and the reasoning is similar. The $x^3$ term still represents the cases where 3 objects are chosen from that category, but now it has an extra bit attached that says how many different ways there are to order those three objects.

The first example rewritten for when order matters looks like this:

$(1+x+\frac{x^2}{2!}+\frac{x^3}{3!})(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!})(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!})$

So to be clear, the answer to how many ways there are to pick $m$ objects from this pool where the order matters is the coefficient of $\frac{x^m}{m!}$, which is just like asking for the coefficient of $x^m$ and multiplying it by $m!$.

Notice that the coefficient of $\frac{x^{12}}{12!}$ in this example is $\frac{12!}{3!5!4!}$, which corresponds to the formula posted in the question where $m=\sum_{i=1}^{n}k_i$.

For the general process asked for in the question, look for the coefficient of $x^m$ in the polynomial

$(1+x+\frac{x^2}{2!}+...+\frac{x^{k_1}}{k_1!})(1+x+\frac{x^2}{2!}+...+\frac{x^{k_2}}{k_2!})(1+x+\frac{x^2}{2!}+...+\frac{x^{k_3}}{k_3!})...(1+x+\frac{x^2}{2!}+...+\frac{x^{k_n}}{k_n!})$

and multiply the answer by $m!$

Answer 2

This may be a disappointing answer, but I don't believe that there's a better one. What you have to do is reduce this problem to the case where $m = \sum k_i$, although it will end up quite ugly.

For any given arrangement that we're counting, there will exist $(r_1,r_2,\ldots,r_n)$ s.t. we have precicely $r_i$ objects from type $i$. For any given choice of $(r_1,\ldots ,r_n)$, we know exactly how many arrangements we can have with $r_i$ objects of $i$: $\frac{m!}{r_1! r_2! \cdots r_n!}$. We have to then sum over all possible $(r_1,\ldots,r_n)$; that is, we need to count over all $(r_1,\ldots,r_n)$ where $r_i \geq k_i$ and $\sum r_i = m$. We thus have that the total number of arrangements is $$ \sum\limits_{\substack{r_1 + r_2 + \ldots + r_n = m \\ r_i \geq k_i}}^n \frac{m!}{r_1! r_2! \cdots r_n!}. $$

I don't think that this sum (or answer) can be simplified: in the case of $n = 2$, this reduces to a partial sum of binomial coefficients, which has no known (useful) closed form.