4-7. Four ways of selecting items

Four ways of selecting items

Say someone is given a bag containing three condiments:

• A: pepper
• B: salt
• C: sugar

In how many ways can they select two sweets? We can follow different principles.

• Order matters means whether we count $AB$ and $BA$ as different elements.
• Repetition allowed means whether we allow elements to pair with themselves, e.g. $AA$, $BB$, $CC$.

Header	Order matters?	Repetition allowed?	Result
A	✅	❌	AB, AC, BA, BC, CA, CB
B	✅	✅	AA, AB, AC, BA, BB, BC, CA, CB, CC
C	❌	❌	AB, AC, BC
D	❌	✅	AA, AB, AC, BB, BC, CC

In summary:

	Order matters permutations	Order doesn’t matter combinations
Repetitions not allowed	$\boxed{n\cdot (n-1)\cdot ...\cdot (n-k+1)}$ $\text{or }\boxed{k!}\text{ if }k=n$	$\left(\begin{array}{c}n\\ k\end{array}\right)$
Repetitions allowed	$n^k$	$\left(\begin{array}{c}k+n-1\\ n-1\end{array}\right)=\left(\begin{array}{c}k+n-1\\ k\end{array}\right)$

Where $n$ is the total number of items, $k$ is the number of items we want to select.

Order matters, repetition not allowed

Order matters, repetition not allowed

How many ways can we select $k$ persons from a group of $n$ people to stand in line for a photo shoot? There are:

• $n$ ways to select the first person
• $n-1$ ways to select the second person
• and so on until the $n-(k-1)$ ways to select the $k$th person

So, using the product rule, we find that:

$$\begin{array}{rl}\boxed{n\cdot (n-1)\cdot ...\cdot (n-k+1)}& =\frac{n\cdot (n-1)\cdot ...\cdot (n-k)\cdot ...\cdot 2\cdot 1}{1\cdot 2\cdot ...\cdot (n-k)}\\ & =\frac{n!}{(n-k)!}\end{array}$$

There is a special case when $k=n$:

$$\begin{array}{rl}\frac{k!}{(k-k)!}& =\frac{k!}{0!}\\ & =\frac{k!}{0}\\ & =\boxed{k!}\end{array}$$Link to original

Order matters, repetition allowed

Order matters, repetition allowed

How many words of length $k$ can be formed from the letters of an $n$ letter alphabet?

• There are $n$ ways to select the first letter.
• $n$ ways to select the second.
• $n$ ways to select the $k$th letter.

So by the product rule, the overall number is:

$$\stackrel{k}{\overbrace{n\cdot n\cdot ...\cdot n}}=n^k$$Link to original

Order does not matter, repetition not allowed

Order does not matter, repetition not allowed

How many ways can we select $k$ persons from a group of $n$ people if the order of selection does not matter?

• As seen before, if the order of selection matters, there are $\frac{n!}{(n-k)!}$ ways.
• But then for each set $A$ of $k$ people, we counted the the people in $A$ the number of ways $k$ persons can be ordered. ($k!$)
• So, if the selection order does not matter, then the number of ways is: $$\begin{array}{rl}\frac{\frac{n!}{(n-k)!}}{k!}& =\frac{n!}{(n-k)!\cdot k!}\\ & =\left(\begin{array}{c}n\\ k\end{array}\right)\text{ or }{}_n{C}_k\end{array}$$ This leaves us with the binomial coefficient equation.

Link to original

Order does not matter, repetition allowed

Order does not matter, repetition allowed

Given we have an unlimited supply of $3$ types of fruit:

• A: apples
• O: oranges
• P: peaches

How many ways are there to select $4$ pieces of fruit, if the order of selection does not matter, only the type of fruit / not the individual piece matters?

We could consider a box which can store 4 pieces of fruit, the box can have 3 compartments, each can store one of 3 types of fruit. Compartments are divided by 2 movable dividers that can be shifted depending on how many types of each fruit we want to store. For example:

• 2 apples, 1 orange, 1 peach: $\boxed{AA|O|P}$
• 4 oranges: $\boxed{|OOOO|}$
• 1 apple, 3 peaches: $\boxed{A||PPP}$
• 4 apples: $\boxed{AAAA||}$

So if we have to choose $k$ objects from a set of $n$ objects, with repetition allowed, we need a box with $k$ places for the chosen object and $n-1$ places for the dividers dividing the box into $n$ compartments.

Given any random box: $\boxed{\ast \ast |\ast \ast \ast |\ast ||}$, we have $k+n-1$ places.

The number of ways we can choose our $k$ objects is the number of ways we can distribute the dividers in the box. Out of the $k+n-1$ places, we hace to choose $n-1$ for the dividers. The number of ways of doing this is:

$$\boxed{\left(\begin{array}{c}k+n-1\\ n-1\end{array}\right)}=\left(\begin{array}{c}k+n-1\\ k\end{array}\right)$$

This formula should be remembered!

Going back to the example, we find that:

$$\begin{array}{rl}\left(\begin{array}{c}4+3-1\\ 3-1\end{array}\right)& =\left(\begin{array}{c}6\\ 2\end{array}\right)\\ & =\frac{6!}{4!\cdot 2!}\\ & =\frac{6\times 5}{1\times 2}\\ & =15\text{ ways}\end{array}$$Link to original