Putting socks and shoes on a spider

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

What does it mean?

It means first put sock on leg $\color{red}{3}$ and on 4-th move put shoe on leg $\color{red}{3}$

then put sock on leg $\color{blue}{4}$ and on 11-th move put shoe on leg $\color{blue}{4}$ 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 $${16\choose 2}{14\choose 2}....{4\choose 2}{2\choose 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.