1
$\begingroup$

I'm studying Discrete and Combinatorial Mathematics by Grimaldi.

I'm currently reading the section on combinations with repetitions and solution technique consists in essence of mapping items to x's, and containers to bars.

An example to illustrate the technique: Three friends can choose from five flavours of ice cream. How many possible combinations could there be?

This problem can be represented with four bars and three stars:

For example, if two friends choose the first flavour and one chooses the fourth flavour, we have - xx|||x|.

Or if all three buy the fifth flavour - we have ||||xxx.

So the solution, to three friends buying five flavours is equivalent to the solution for the number of combinations of three stars and four bars which is clearly $\frac{7!}{3!\times 4!}$

As the textbook notes, this solution is only applicable for indistinct items going into distinct containers.

This idea of mapping the problem to symbols seems strange to me. It seems I could do an identical mapping in the case where both items and containers are distinct and get an incorrect result from it.

For example, instead of three students, we have Alex, Bob, and Chris who can choose from five flavours of ice cream. How many possible combinations could there be?

I know the correct answer is $5^3$.

But I could also do a mapping to the symbols - ||||ABC.

(E.g. AB|C||| = Alex and Bob have first flavour, Chris has second.)

The number of combinations of ABC|||| is $\frac{7!}{4!}$ which is not $= 5^3$.

Where is the mistake in my own mapping of distinct objects in distinct containers that is different to the textbook's correct mapping?

$\endgroup$
1
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Apr 8, 2023 at 18:05

1 Answer 1

3
$\begingroup$

The reason that your correspondence does not work is because the representation is not unique. For example, $A\,B\mid\, \mid C\mid \,\mid $ would represent the situation where both Alice and Bob pick the first flavor, and Charlie picks the third flavor. However, $B\,A\mid\, \mid C\mid \,\mid $ represents this same situation. Therefore, the number of sequences of $A,B,C$ and four bars does not count equal the number of ways for the three people to choose ice cream flavors.

This problem does not arise in the combinations-with-repetitions problem, because the $x$'s are all identical.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .