TITLE: Teaching permutations, How to?
QUESTION [6 upvotes]: I posed this question to my niece while teaching her permutations:

Given four balls of different colours, and four place holders to put those balls, in how many ways can you arrange these four balls in the four place holders?

She reverted with $(4!)^2$ while I was expecting to hear $4!$.  Her reasoning was so:

I can select the first of any of the four balls in four ways.  Having picked one, I put this in any of the four place holders in four ways.  Now, I select the second ball from the three remaining ones in 3 ways.  I can place it in any of the remaining three place holders in 3 ways.

... and so on to produce $4^2 * 3^2 * 2^2 * 1^2$
How do I explain to her that only $4!$ arrangements are possible and this is regardless of which order she picks the balls?

REPLY [7 votes]: Demonstrate it inductively. Clearly there’s only one possible ordering of one object, $A$; that’s $1$. Add a second; it can go before ($BA$) or behind ($AB$), doubling the number of possiblities to $2\cdot1$. Add a third: it can go into any of three slots, tripling the number of possibilities: $3\cdot2\cdot1$. At this stage it’s a good idea still to illustrate everything:
$$\begin{array}{c}
&&&\square&B&\square&A&\square\\
&&&\color{blue}{C}&&\color{red}{C}&&\color{green}{C}\\
&&\swarrow&&&\downarrow&&&\searrow\\
\color{blue}{C}&\color{blue}{B}&\color{blue}{A}&&\color{red}{B}&\color{red}{C}&\color{red}{A}&&\color{green}{B}&\color{green}{A}&\color{green}{C}\\ \hline
\\
&&&\square&A&\square&B&\square\\
&&&\color{blue}{C}&&\color{red}{C}&&\color{green}{C}\\
&&\swarrow&&&\downarrow&&&\searrow\\
\color{blue}{C}&\color{blue}{A}&\color{blue}{B}&&\color{red}{A}&\color{red}{C}&\color{red}{B}&&\color{green}{A}&\color{green}{B}&\color{green}{C}
\end{array}$$
Then each of the $3\cdot2\cdot1$ strings of $3$ objects has $4$ slots in which to insert a new one, for a total of $4\cdot3\cdot2\cdot1$ strings, and so on:
$$\square\quad X\quad\square\quad Y\quad\square\quad Z\quad\square$$
{"set_name": "stack_exchange", "score": 6, "question_id": 154316}