# Putting socks and shoes on a spider

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.

• I think your factor of $(8!)^2$ is overcounting because it doesn't account for the constratint that the sock on leg $n$ has to go on before the shoe on leg $n$. Your count would allow sequences starting sock on leg $1$, shoe on leg $2$, ... for example. But I can't see a simple expression for the distinguishable legs case. Jan 29, 2019 at 9:48
• Are those 4 left shoes and 4 right shoes and 8 symmetrical socks? Jan 30, 2019 at 12:47
• Wow! Ambiguous questions are to be expected in beginning combinatorics questions but this one takes it to a whole new level! What is a "way of putting on shoes". Is it about which shoe and sock goes on which foot? Is it about what order you put things on on which foot? Are shoes and sock distinguishable. Are legs? Feb 7, 2019 at 17:02
• @fleablood i want to ask something , if All socks and shoes are distinguishable , after we found wearing order , why did we not multiply by $(8!)^2$ ? For example , for $345322815....$ , i think that we should have determined which socks is for the first $3$ , and which shoe is for the second $3$ ? am i wrong? Sep 25, 2021 at 11:14
• @Bulbasaur I have no idea what you are asking. I don't know what "wearing order" means, I have no idea what you are proposing multiply by $(8!)^2$, I don't know what the numbers $345322815....$ means. And I have no idea why you are asking me this of all people..... This question is still ambiguous but if we assume that it means the spider has 8 distinct shoes and 8 distinct socks how many outcomes can it have if it has a shoe under a sock for each leg.... The the answer to that is $(8!)^2$. $8!$ positions for 8 socks on 8 legs and $8!$ positions for 8 shoes on 8 legs. Sep 25, 2021 at 17:01

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}$$

• I gave the tick to this answer because it's the easiest to understand. Jan 29, 2019 at 20:55
• Am I the only one amazed by the fact that there are over 81 billion possibilities? Jan 30, 2019 at 12:03
• You gave $34;53;22;81;56;46;77;81$. Why does $81$ appear twice, at positions 4 and 8, or have I misunderstood the way the sequence is written? Feb 4, 2019 at 23:12
• Oh, I figured it out: you have $1,1,2,2, ..., 8,8$ and you just permute them to form that sequence above. Feb 4, 2019 at 23:14
• i see that you deleted my comment , it is unrespectful behavior , you chould have added an explanation .Was my comment wrong? if not why did you delete Sep 25, 2021 at 10:58

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}$$.

• I wrote an comment in @aqua's answer , can you look at it ? i think that there is something deficit in your answers , it is said that socks and shoes are distinguishable , so $(8!)^2$ must be added to your answers Sep 23, 2021 at 15:36

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 $$\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.