Argthtjtr

A spider needs a sock and a shoe for each of its eight legs. In how many ways can it put on the shoes and socks, if socks must be put on before the shoe?

My attempt:

If I consider its legs to be indistinguishable, then it's exactly the $8^{text{th}}$ term of the Catalan sequence. However the legs are distinguishable. So the total number of ways equals $frac1{8+1} binom{16}{8} (8!)^2$.

Is this correct? Is there another way of doing it?

Edit:

All socks and shoes are distinguishable.

You can imagine doing this as writing a sequence, say $$3453228156467781$$

What does it mean? It means first put sock on leg $3$ and and on 4-th move put shoe on leg $3$ and so on. So for each leg you must choose a pair in this sequence. On smaller number in this pair put a sock and the other shoe.

So we have $${16choose 2}{14choose 2}....{4choose 2}{2choose 2} = {16!over 2!^8}$$

No, it's not correct. Multiplying the Catalan number by $8!$ twice means we're choosing legs arbitrarily for each instance of a socking or a shoeing - with no regard to whether that leg has a sock on it, in the latter case. It's a substantial overcount.

Multiplying by $8!$ once would correspond to a "last in, first out" restriction; each time we put a shoe on, it's the most recently socked leg. That's an undercount, of course.

There are two actions per leg - the sock and then the shoe. All we need to know to determine a sequence is when each leg was worked on. That's $binom{16}{2}$ for the first leg, $binom{14}{2}$ for the second, and so on - or, equivalently, the multinomial coefficient $binom{16}{2,2,dots,2} = frac{16!}{(2!)^8}$.

The answers given are correct, but I have a different (and possibly easier) way to think of it:

If you relax the condition for the sock/shoe event to be in order then there are $2n$ ($=16$) events hence $16!$ orderings.
This is of course an over-count: many (most) of these are of an invalid ordering, with at least one sock over the top of a shoe.
The question is by how many?

To answer this, suppose we divide them into groups. Specifically one group for each of the orderings of shoe/sock on each foot.
For example:

• a group where: the sock on leg 1 is before on leg 1, the sock on leg 2 is before the shoe on leg 2 ..., the sock on leg 8 is before the shoe on leg 8 (the one we want)


• a group where: the sock on leg 1 is after on leg 1, the sock on leg 2 is before the shoe on leg 2 etc (not valid for us)

These groups are of the same size (none of them are special).

There are $2^n$ ($2^8$) of these groups so each of them, including the one we want, is of size: $frac{16!}{2^8}$ or $81,729,648,000$.

Notes on generalisation:

Suppose $n$ legs and $k$ objects to put on in a given order.
There are $(k n)!$ events, $k!$ orderings of any one of the leg's objects. Hence $(k!)^n$ orderings of the objects on each leg, only one of which is desired and so:
$frac{(k n)!}{(k!)^n}$ possible valid orderings of placing an object on a leg.

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 $sumlimits_{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.