In combination problems, when does distinguishability of objects matter?

Question

If I have $n$ objects, and asked the number of ways to choose $k$ of them, the answer is $\binom{n}{k}$ (example problem 1). Similarly if I have $n$ objects and asked to put $a$ in one bin, $b$ in another, and $c$ in another, I think the number of ways I can do this is $\frac{n!}{a!b!c!}$ (example problem 2). I'm sure but I don’t think the answer changes whether the objects are, say, all the same (color) or are partially or completely distinct, despite the fact that if the objects are identical the combinations “look” the same (unless there's some other way to tell the objects apart that isn't explicitly stated).

However, in a stars and bars problems, the objects are indistinguishable but the bins are, so in this case the distinguish-ability matters. How do I identify when having distinguishable objects matter and when not?

Answer 1

It always matters whether thinks are distinguishable. In your first example, if the $n$ items are identical there is only one way to select $k$ of them, not $n \choose k$. Similarly in your second example there would be only one way if the objects were identical. In a typical stars and bars problem the objects are not distinguishable, but if they were there would be many more ways to put them in the bins.

Sometimes it is difficult to determine whether the objects are distinguishable or not, but that is a different question.

Answer 2

It changes the answers if it matters. We care about distinguishable states in combinatorics. Here are just some of the possibilities for combinations.

1. combinations without repetition (distinguishable)
2. combinations with repetition (indistiguishable elements)
3. combinations with replacement (indistinguishable elements)
4. combinations without replacement(see 1 and 2)
5. combinations with restriction (ex. alice and bob next to each other in a class photo)

For permutations we have the nearly the same, and much more ( different answers though).

For the first above, think of three students Alice,Bob, and Charlie. Lets pick 2, we can pick any of the three for the first person and any of the remaining 2 for the second. We also don't care in this case (indeed most cases in combinations) about the order they are picked. So we get: $$\frac{3\cdot\not2}{\not2}=3$$ possible choices: $$\{(Alice,Bob),(Alice,Charlie),(Bob,Charlie)\}$$

For the second above, what if Charlie was a Bob, then the two Bob's can't be distinguished by name (Hello need for surnames and nicknames). In this case we have 2 choices total $$\{(Alice,Bob),(Bob,Bob)\}$$ We don't care about which Bob it is, we can't tell the difference. No name in each pair represents the same person twice, so Both Bob's are in the second one.

The third one above, is like drawing names but putting the names back each time a name is drawn. We care about how many times each name was drawn, not the order.

The fourth one above, has the first 2 as subtypes.

The fifth above, has better examples such as combinations with exactly 3 even numbers.