Combinatorics: 11 Fishermen problem

Question

$11$ fishermen go fishing together. There are $11$ chairs near the river in a row. The first fisherman can choose any chair to sit (on the edges, in center, etc). The second fisherman has to sit next to the first. The third one has to sit next to the previous men, without leaving empty chairs between them, and so forth: the $k$-th fisherman has to sit next to the group, without leaving empty gaps.

For example : $$4- 2-1 -3 -5- 6- 7- 8- 9- 10 -11$$ $$4 -3 -2- 1- 5- 6 -7- 8 -9 -10 -11$$ $$1- 2- 3- 4- 5- 6- 7 -8 -9 -10 -11$$ $$9 -8 -5 -4 -2 -1 -3 -6 -7 -10 -11$$

In how many combinations can they sit?

Answer 1

There is a very nice formula for this. Suppose there are $n$ chairs, and the first person sits at chair $k$. There are now $n-1$ chair left over, from which $k-1$ at the left side. The other fisherman can only choose whether they sit left or right. We have to choose $k-1$ from the $n-1$ fisherman to sit at the left. Therefor there are $\binom{n-1}{k-1}$ ways the other fisherman can sit.

Thus, the total amount of possibilities is $$\sum_{k=1}^{n}\binom{n-1}{k-1} = 2^{n-1}$$

Answer 2

It all depends where the first fisherman is sitting. I'll call the chairs $A,B,C,\dots,K$. Let $f:\mbox{chairs}\to \mathbb{N}$, and $f(x)$ be the amount of ways that the fishermen can sit if fisherman 1 sits in chair $x$.

If fisherman 1 sits in $A$, there is only one way in which the rest of them can sit, i.e. $f(A)=1$. If $1$ sits in $B$, then only one fisherman among the remaining 10 can sit in $A$, and the rest of them can sit in only one way. I.e. $f(B)=10$. Likewise, if fisherman 1 sits in $C$, two fishermen must sit at $A,B$: $$f(C)=\sum_{i=1}^{9}(10-i)$$ (the order in which the two left-seaters fishermen are chosen matters and we can't allow fisherman $i$ to sit before fisherman $j$ if $i>j$). I'll let you continue the argument to determine $f(A)+\dots+f(K)$, and come back at the comments if you have any questions, cheers.

Answer 3

As mentioned in my comment the problem is easily solved if you work backwards from the last person seated. Let's generalise for $n$ fishermen.

However the $n$ fishermen successively choose to seat themselves, the $n^\text{th}$ fisherman can only sit in seat $1$ or $n$, otherwise some previous fisherman must have seated himself apart from the others which violates the rule in the question.

So, fisherman $n$ either sits in seat $1$ or $n$: $2$ possibilities.

Now we use the same argument with the remaining $n-1$ fishermen in the remaining $n-1$ seats, i.e. for each seating of fisherman $n$, fisherman $n-1$ has $2$ seating possibilities: one at either end of the block of the $n-1$ remaining empty seats.

Continue this argument recursively ($2$ choices for each fisherman) until we get to fisherman $1$ who only has $1$ fixed choice since there is only $1$ empty seat remaining.

$$\text{seatings}=\underbrace{2\times 2\times\cdots\times 2}_{\text{$n-1$ times}}\times 1=2^{n-1}\, .\tag{Generalisation}$$

For this case $n=11$ and we have

$$2^{10}=1024\tag{Answer}$$

seatings.

---

An equivalent problem with slightly more obtuse wording is:

"How many permutations of $\{1,\ldots,n\}$ are there where every number except for the leftmost is different by $1$ from some number on it's left?"

The main difference being that the elements $1$ to $n$ take on the role of the seats and the left to right positions are the fishermen $1$ to $n$. The permutations of elements in left-to-right positions are then assignments of seats to fishermen.