# a spider has 1 sock and 1 shoe for each leg. then find out the the total possibilities.

a spider has one sock and one shoe for each of its 8 legs.in how many different orders can the spider put on its shocks and shoes; assuming that on each leg ;the shock must be put on before the shoe? i have tried the problem in following processes-

• we consider in k th step it has completed covering exactly its k legs with socks.now we find the total possibilities in (k+1) th step.
• in (k+1) th step either one of the remaining (8-k) legs will be covered by shocks or one of the (k-r) legs will be covered by shoe. where r denote the number of legs among the k legs which were already covered by shoes. so 0$\leq$r$\leq$k and 1$\leq$k$\leq$8
• so in the 1st case there are (8-k) possibilities and in the 2nd case ..........if 1 leg is covered with shoe then (k-1) possibilities; if 2 legs are covered with shoes then (k-2) possibilities; if no leg then k possibilities. so total possibilities is k.(k-1).(k-2)(k-3).........1=k!
• in (k+1)th step the total possibilities is (8-k).k!.[in each step it puts on either a shock or a shoe]
• so the solution is $\Sigma$(8-k).k! ;k=1 to 16
• if i am wrong in any step then show me please. if i am not then give an alternate solution of this.

Let the act of putting on a sock be $1,2,3,4,5,6,7,8$, each corresponding to a leg. Let the act of putting on a shoe be $A,B,C,D,E,F,G,H$, each corresponding to a leg as well.

This problem is now bijective to counting the number of strings such that $A,B,C,D,E,F,G,H$ comes after $1,2,3,4,5,6,7, 8$ respectively.

We start with $1$ leg. Then there is only $1$ way: $1A$. Now we want to add the next leg. There are $3 \times 4$ ways to add $2$ and $B$ into the string, without any order. Why? Because there are $3$ ways to insert $2$ into $1A$, and $4$ ways to insert $B$ into each of the the resultant string.

But there are as many ways to insert $2$ and $B$ such that $2$ comes after $B$ as there are ways of insertion such that $B$ comes after $2$. So there are $\frac{1}{2} \times 3 \times 4$ ways such that $B$ comes after $2$, i.e. second shoe comes after second sock.

Generalize this to get a recursion: Let $a_n$ be the number of ways for $n$ legs. Then,

$$a_{n + 1} = \frac{1}{2}\times a_n \times (2n + 1)\times(2n + 2)$$

• nice Yiyuan. nice solution. but is my process right? – krishan acton Apr 5 '14 at 14:27
• @krishan I am unable to follow through your solution, it seems a bit too complicated to me... – Yiyuan Lee Apr 5 '14 at 14:42
• – gar Apr 6 '14 at 14:45
• am i right or not? answer me please.yes or no . – krishan acton Apr 9 '14 at 6:50