Teaching permutations, How to? 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?
 A: 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$$
A: Point out that, by this reasoning, there are $4$ ways to arrange two objects in order.
As for explaining, approach it this way. Rather than having holders specified for the balls (the main source of confusion, here) just think of it as drawing balls at random out of a hat, say. In how many distinct orders can the balls can be drawn, assuming one is drawn at a time? Alternately, if you want to keep the previous approach, point out that under her method, there are in fact $4!$ ways (chronological orders of placement) to obtain any given physical arrangement of the balls! Thus, to enumerate the distinguishable physical arrangements of the balls, we find $$\frac{(4!)^2}{4!}=4!,$$ as desired.
