Bijection between multisets and directed animals?

257 Views Asked by At

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?


This question is now resolved in this paper.

2

There are 2 best solutions below

0
On BEST ANSWER

This question is now resolved in this paper.

0
On

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!