5
$\begingroup$

The number of directed animals (aka polyominoes) of size $n$ (A005773) is enumerated by the generating function $$\frac{1}{2} \left(1+\sqrt\frac{{1+z}}{{1-3 z}}\right).$$ This generating function also enumerates the number of $n$-element multisets of $\{1,\ldots,n\}$ containing no pair of consecutive integers (e.g. $111, 113, 133, 222, 333$ for $n=3$).

The first few numbers in the sequence are $$1, 1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721.$$ Is there a good bijection between the two combinatorial classes?

$\endgroup$
1
$\begingroup$

I haven't seen the second interepretation, but it seems natural enough. I recall this paper by Gouyou-Beauchamps and Viennot, which gives a bijection between directed animals and certain lattice paths. The latter tend to be much easier to work with, so if you really need the bijection try to related these paths with the multisets. Good luck!

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