21
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gandalf61 Jan 29 at 9:48
  • $\begingroup$ Are those 4 left shoes and 4 right shoes and 8 symmetrical socks? $\endgroup$ – Stian Yttervik Jan 30 at 12:47
  • 1
    $\begingroup$ 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? $\endgroup$ – fleablood Feb 7 at 17:02
35
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I gave the tick to this answer because it's the easiest to understand. $\endgroup$ – abc... Jan 29 at 20:55
  • $\begingroup$ Am I the only one amazed by the fact that there are over 81 billion possibilities? $\endgroup$ – CTodea Jan 30 at 12:03
  • $\begingroup$ 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? $\endgroup$ – jamesh625 Feb 4 at 23:12
  • 2
    $\begingroup$ Oh, I figured it out: you have $1,1,2,2, ..., 8,8$ and you just permute them to form that sequence above. $\endgroup$ – jamesh625 Feb 4 at 23:14
15
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.