How to put lions into n cages

Question

In how many ways can you put lions into n cages so that in each cage there's no more than 1 lion and every two adjacent cages are not occupied (lions cant be located next to each other). We have an unlimited number of lions and there's at least one lion (so at least one cage is occupied).

Thanks in advance for any help!

Edit: I think I could find the generating function if I had the reccurent sequence

Answer 1

Let $f(n)$ be the number of the ways you want.

Also, let $g(n)$ be the number of the ways with a lion in the $n$-th cage, and let $h(n)$ be the number of the ways without any lion in the $n$-th case.

So, we have $$f(n)=g(n)+h(n).$$

Now you'll easily get $$g(n+1)=h(n)$$ $$h(n+1)=g(n)+h(n).$$

Hence, you'll get $$h(n+1)=h(n)+h(n-1).$$

This is a well-known sequence...

Answer 2

If you remove condition that at least one cage is occupied, this is the same as asking

How many $n$-lengthed strings of $A$'s and $B$'s are there, in which there are no conscutive $A's$?

Recursion. Let be $T(n)$ number of strings. $T(1) = 2$, $T(2) = 3$ and

$$T(n) = T(n-1) + T(n-2)$$ for $n>2$. Try to prove upper relation. Hint: take a look at the last char of string.

Answer 3

If you write out the number of lions in each cage, the zeros and ones give you exactly the Zeckendorf representations of length at most $n$, so there are $F_{n+2}-1$ ways (minus one because you eliminated $0$). (With the usual Fibonacci numbers starting at $F_0=0$.)

See Zeckendorf on Wikipedia for details.

Answer 4

As this question is tagged generating-functions, here's a different approach (looks long but it gives the generating function directly), using the formalism from the wonderful book Analytic Combinatorics (available online!) by Flajolet and Sedgewick.

Let "L" denote a cage with a lion in it, and "E" denote an empty cage. Then, convince yourself that

• any configuration of cages can be denoted by a sequence of 'E's and 'L's such that no two 'L's are consecutive, and that

• this is the same as a sequence over the alphabet $\{\mathrm{E}, \mathrm{EL}\}$, except possibly with an $\mathrm{L}$ at the beginning.

For example, "EELEEELEEE" is one arrangement of $10$ cages, and it can be viewed as the sequence $(\mathrm{E}, \mathrm{EL}, \mathrm{E}, \mathrm{E}, \mathrm{EL}, \mathrm{E}, \mathrm{E}, \mathrm{E})$.

Let $\mathcal{C}$ denote the class of all cage configurations. Then, by the reasoning above, we have (where $\epsilon$ denotes the empty string)

$$\mathcal{C} = (\epsilon + \mathrm{L}) \operatorname{S\scriptsize EQ}(\{\mathrm{E}, \mathrm{EL}\})$$

which immediately translates (by the first theorem in the book) to the generating function

$$C(z) = (1 + z)\frac{1}{1-(z+z^2)}$$

which (note that $C(z) = 1 + 2z + 3z^2 + 5z^3 + 8z^4 + \dots$) is exactly what you would get from the recurrence relations.

Note that we didn't have to consider configurations of specifically $n$ cages explicitly and then sum over $n$ to get the generating function; we directly derived the generating function of the entire class of configurations.

---

[Notes: $\epsilon$ is of size $0$ and has generating function $z^0 = 1$, $\mathrm{L}$ is of size $1$ and has generating function $z^1 = z$, the set $\{\mathrm{E}, \mathrm{EL}\}$ has generating function $z^1 + z^2$, and a sequence over a class with generating function $B(z)$ has generating function $\dfrac{1}{1-B(z)}$.]

---

Oh also: I just noticed the "at least one lion" requirement. Well, in that case (dropping some braces in the notation for convenience): $$\mathcal{C} = \left((\epsilon + \mathrm{L}) \operatorname{S\scriptsize EQ}(\mathrm{E}, \mathrm{EL})\right) \setminus \operatorname{S\scriptsize EQ}(\mathrm{E})$$ so $$C(z) = (1 + z)\frac{1}{1-(z+z^2)} - \frac{1}{1-z}$$

Another way of deriving the same result is to say: we want a (possibly empty) sequence of 'E's, followed by an 'L' (the "at least one lion", namely the first), followed by a (possibly empty) sequence over $\{\mathrm{E}, \mathrm{EL}\}$. So $$\mathcal{C} = \operatorname{S\scriptsize EQ}(\mathrm{E}) \, \mathrm{L} \, \operatorname{S\scriptsize EQ}(\mathrm{E}, \mathrm{EL})$$ which translates to $$C(z) = \frac{1}{1-z} z \frac{1}{1-(z+z^2)}$$ which is the same.