[Math] permutation combinations and other possibilities (e.g. pizza toppings)

combinationspermutationsprobability

it's been quite a few years since I studied probability and looking at my old notes, I can't figure a few things out and I have a few questions. I've looked at a few suggested answers but they don't answer my question in full, in particular because I'm looking for the formulae, not necessarily answer to the pizza question which is more of an example to demonstrate the issue.

INTRO and Background: I know that combinations the order does not matter, permutations do. But I want to know the name or formula for other possibilities, as my example of pizza toppings can hopefully illustrate:

If there are seven potential toppings, ABCDEFG (Artichoke, Bacon, Chicken, Dried tomatoes, Eggplant, Feta cheese, Green pepper) and I have a deal for two toppings and two toppings only (with no repetition allowed) then it's easy to calculate, as the first one can be any of the seven, and the second, any of the remaining six. That's 42 potential combinations…or rather, permutations. Since for combinations the order does not matter, it will be half of that, 21. I also have two formulae, using r and n, for calculating them, though I'm not sure how to write them down here. But those two formulae don't seem to be useful for the following extensions of the question.

Problem:

  1. But what formulae can I use if I could repeat any of the above toppings in my order? Like double cheese? Or double bacon?

  2. What if I were not limited by two toppings, but was given a coupon that said I could choose from potential pizzas with max of five toppings each (meaning one to five). This means I could order pizzas as variable as three cheese and two bacon, pizza with only a single topping of chicken, etc.

  3. Does the formula allow me to distinguish between topping repetition allowed/not allowed, the latter obviously won't affect the single topping combinations but will decrease the number of possibilities as we go up towards the five topping limit.

  4. Putting the issue of repetition aside for this question, what if order mattered? Again, obviously won't apply to one toppings, but for the second, you could put cheese first then the green pepper or vice versa, etc. And so I wonder if there is a formula that would take this into account.

Thank you for your help.

Best Answer

$0$. There are $^n\mathrm C_r$ ways to choose $r$ from $n$ distinct things; also written as $\binom n r$ or $\frac{n!}{r!~(n-r)!}$.

Here the count of ways to select $2$ from $7$ toppings is: $${^7\mathrm C_2}=\dbinom 72 = \dfrac{7!}{2!~5!} =\dfrac{7\cdot 6}{2\cdot 1}= 21$$

$1$. As above you wish to count ways to choose $2$ from $7$ toppings, but also $1$ from $7$ toppings twice.   However, we might also observe that this will be the seventh Triangular Number: $$\binom 72+\binom 71~=~\binom{7+1}2$$

$2$. The same principle applies; it will be the sum of the seventh $1$- to $5$-gonal numbers.

$3$. No, but if you have a way to count the prohibited combinations, you can subtract them.

$4$. If order matters, you are dealing with $m$-exponentials rather than $m$-gonal numbers.   For instance, the count of ways to select two from seven toppings with repetition when order matters is $7^2$.

Related Question