Another approach:
Let $f(n)$ denote the number of ways for an $n$-legged animal to put socks and shoes on all of their legs.
With one leg, there's only one way: Put the sock on, then the shoe.
With two legs (like the vast majority of humans), there are 6 possibilities. In greedoid's notation, these are:
- 1122 = Sock on leg #1, shoe on leg #1, sock on leg #2, shoe on leg #2
- 1212 = Sock on leg #1, sock on leg #2, shoe on leg #1, shoe on leg #2
- 1221 = Sock on leg #1, sock on leg #2, shoe on leg #2, shoe on leg #1
- 2112 = Sock on leg #2, sock on leg #1, shoe on leg #1, shoe on leg #2
- 2121 = Sock on leg #2, sock on leg #1, shoe on leg #2, shoe on leg #1
- 2211 = Sock on leg #2, shoe on leg #2, sock on leg #1, shoe on leg #1
Now, suppose that we've calculated $f(k)$ for some $k$. How does introducing a $(k + 1)$th leg affect the problem?
If you take any possible sequence of the $2k$ sock+shoe events for $k$ legs, then there are $2k + 1$ possible positions in the sequence to put the sock for the new leg (the $2k - 1$ positions between existing events, at the beginning, or at the end). Assume that we decide to put this new event after $j$ of the original events.
Now, let's decide when to put on the shoe for the new leg. This is trickier, because it depends on when we put on the sock. This new event can be inserted at index $j + 1$, $j + 2$, $j + 3$, ..., up to $2k + 1$, for $2k + 1 - j$ possibilies.
So, that gives us $\sum\limits_{j=0}^{2k+1} (2k + 1 - j)$ possibilities for when to add the sock and shoe for the new leg, which works out to the $(2k + 1)$th triangular number = $\frac{(2k + 1)(2k + 2)}{2}$. With $k + 1 = n$, this can be rewritten as $\frac{(2n - 1)(2n)}{2} = n(2n - 1)$.
We now have the recurrence relation $f(n) = n(2n - 1)f(n-1)$ with base case $f(n) = 1$. Or, in Python syntax.
>>> def f(n):
... if n == 1:
... return 1
... else:
... return n * (2 * n - 1) * f(n - 1)
...
>>> f(8)
81729648000
Proof that this is equivalent to the non-recursive formulation $f(n) = \frac{(2n)!}{2^n}$ is left as an exercise for the reader.