# Why do we divide by $2^8$ when finding the number of combinations a spider puts on socks and shoes

In the question in which we find the number of ways that a spider can put on shoes and socks, it is obvious that it cannot put on shoes before it puts on socks.

In the answer in the below link in which someone has already showed how to do it, the answer process consisted of doing $\frac{16!}{2^8}$. While i do understand the 16! part and the concept behind dividing by $2^8$, the confusion that I am having is why is it $2^8$ in particular?

I thought it would just be the subtraction of cases in which the spider messes up by putting on shoes before socks?

• A spider has $8$ legs… – Bernard May 23 '17 at 16:13
• I don't think there is any reason why you couldn't solve it by subtracting cases where it put on shoes before socks. However, it should be a lot easier to divide by $2^8$, which would be the number of alterations you could make to a correct configuration. That is for any configuration where that works, there are $2^8$ alterations of it where at least one leg has a shoe on before a sock. – Tyberius May 23 '17 at 16:14

By considering each leg, the $16!$ part counts both the cases where the spider puts shoes on first and socks first.

However, only 'socks-first's should be counted.

So for each legs you divide the number of ways by $2$.

In total, $2^8$.

Observe that you don't get the number of allowed combinations just by subtracting the absurd ones ("sock over shoe") because every absurd combinations has "multiplicity".

Suppose that we have the absurd combination "sock over shoe on third leg", what happens to the rest of the legs under that constraint? They can exhibit other combinations too. There are quite a lot of combinations on the other legs that lead to the absurd case. That's why you divide and not subtract.

After considering $16!$ possible combinations of $8$ socks and $8$ shoes, only half are correct in the first leg, that is, shoe over sock. So divide by $2$ to discard the other half. Then divide the remaining again to leave only the half that that are correct in the second leg. Repeat eight times to get $\frac {16!}{2^8}$ combinations that are right on every leg.

let the number of ways for $n$ legs be $W_n$, the $n+1^{\text{st}}$ sock can be put in $2n+1$ positions, and for each choice $k \in [1,2n+1]$ there are $k$ choices for the position of the corresponding shoe, since it is barred from preceding the sock. thus the total number of choices for the $n+1^{\text{st}}$ pair is: $$\sum_{k=1}^{2n+1} k = \frac12(2n+1)(2n+2) = \frac12 \frac{(2(n+1))!}{(2n+1)!}$$ since $W_0=1$ $$W_n = \prod_{k=0}^{n-1}\frac{W_{n+1}}{W_n}= W_n = \prod_{k=0}^{n-1} \frac12 \frac{(2(n+1))!}{(2n+1)!} = \frac{(2n)!}{2^n}$$