Ordered choices

Idea: Count a decision step by step

Split the outcome into steps, count the options at each step, and multiply.

• The options may change by path; only their number must stay fixed
• Do the restricted step first

Example: 3 jobs, 9 analysts

$9$ analysts, $3$ different jobs, nobody takes more than one. How many rosters?

1. First job: $9$ options, then $8$, then $7$
2. Rosters: $9\times 8\times 7=504$

Idea: With repetition

Let one person hold several jobs, and every step has all the options again.

• $9\times 9\times 9=9^3=729$
• Without repetition: $504$

Formula: k of n in order

$P(n,k)=\frac{n!}{(n-k)!}$

Order k of n distinct people. All n of them give n! orders, and 0! = 1.

Example: A code with no leading zero

How many codes of $4$ different digits have a first digit that is not zero?

1. First digit first: $9$ options
2. Then $9$, $8$, $7$: zero is back, used digits are out
3. Total: $9\times 9\times 8\times 7=4536$

Formula: Glue a block

$(n-m+1)!\times m!$

A block of m who must sit together among n: order the units, then the inside of the block.

Common mistake: Forgetting the inside of the block

$3$ traders glued in a row of $7$: counting only $5!=120$ misses the order inside the block.

Instead Multiply by $3!=6$: $120\times 6=720$. A block of $3$ removes only $2$ units.

Quick check: A pair side by side

$5$ people sit in a row. In how many orders do $A$ and $B$ sit side by side?

Idea: Say it in the room

Name the steps before you multiply, and why each count does not depend on earlier choices.

• Say you handle the restriction first
• Finish with a tiny case you can list