A372123 Number of multisets of free polyominoes that can be constructed from n squares.

1, 2, 4, 10, 24, 68, 200, 652, 2203, 7794, 28182, 103979, 387931, 1461376, 5541033, 21126533, 80897892, 310938666, 1198917744, 4635816939, 17969766349, 69812201957, 271768139230, 1059903743280, 4140631641752, 16200937633453, 63479707135804, 249060516700509

Offset

1,2

Comments

This is the Euler transform of A000105, almost by definition. - Andrey Zabolotskiy , Jul 12 2024

Assuming A000105(n) ~ mu^n asymptotically for some constant mu, an asymptotic upper bound a(n) <= mu^n*A000040(n) can be established.

Links

Table of n, a(n) for n=1..28.

Formula

Let b(n) = A000105(n). Let P(n) be the set of partitions (A000040) of n. For a partition p in P(n), let p' be the set of unique elements of p. For an integer k in p, let m_p(k) be the multiplicity of k in p.

a(n) = Sum_{p in P} Product_{k in p'} (b(n) + m_p(k) - 1)!/((b(n) - 1)!m_p(k)!)

Example

For n = 4, partitions are [4],[3,1],[2,2],[2,1,1],[1,1,1,1].
There are 1,1,2,5 polyominoes for sizes 1,2,3,4.
So a(4) = 5 + 2 + 1 + 1 + 1 = 10.

Crossrefs

Cf. A000105, A000040.

Sequence in context: A148088 A028506 A029893 * A148089 A363065 A200743

Adjacent sequences: A372120 A372121 A372122 * A372124 A372125 A372126

Keyword

nonn

Author

Harold Mikula Quilty, Jul 06 2024

Extensions

a(13)-a(14) from Harold Mikula Quilty, Jul 11 2024

Status

approved