-1
$\begingroup$

For $n \ge 0$, let $h_n$ be the number of ways of taking $n$ (distinguishable) rabbits, putting them into identical cages with one to three rabbits per cage and then ordering the cages in a row. Find an exponential generating function for $h_n$ (assuming $h_0 = 1$).

I know if the ordering of the cages does not matter, then generating function would be $h_n = h_{n-1}+(n-1)h_{n-2}+(n-2)(n-1)h_{n-3}$. How can I include the ordering of the cages in the function?

$\endgroup$
2
  • 1
    $\begingroup$ Why not calculate a few values of $h_n$ and look for a pattern? (or look them up in the OEIS?) $\endgroup$
    – Gerry Myerson
    Commented Nov 16, 2017 at 6:11
  • $\begingroup$ What you have written down as a generating function is no such thing. What you have written down is a recurrence relation. A generating function is something of the form $\sum h_nx^n/n!$. $\endgroup$
    – Gerry Myerson
    Commented Nov 16, 2017 at 12:07

1 Answer 1

Reset to default
2
$\begingroup$

I computed the first nine values of $h_n$ $(n\geq1)$ recursively and obtained the sequence $$ 1, 3, 13, 74, 530, 4550, 45570, 521640, 6717480\ .$$ This is sequence A189886 in OEIS. There is a reference to sequences of sets, no set containing more than three elements. But I didn't study the details.

$\endgroup$
4
  • $\begingroup$ You'll find both a linear recurrence relation and an exponential generating function at that page. But maybe oeis.org/A189886 is a better link for it. $\endgroup$
    – Gerry Myerson
    Commented Nov 16, 2017 at 12:44
  • $\begingroup$ Thanks a lot! Do you mind to explain why the generating function is $1/(1 - x - x^2/2! - x^3/3!) $? I get that the denominator is for a block with size 1-3, but why is it an inverse? $\endgroup$
    – wtnmath
    Commented Nov 16, 2017 at 18:25
  • $\begingroup$ There are links and references at that OEIS page. Have you followed them up, wtnmath, to see whether they derive the exponential generating function? $\endgroup$
    – Gerry Myerson
    Commented Nov 16, 2017 at 21:05
  • $\begingroup$ So, any follow-up, wtnmath? $\endgroup$
    – Gerry Myerson
    Commented Nov 18, 2017 at 2:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .