Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.20143 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915384704106496 |
|---|---|
| author | Bui, Vuong |
| author_facet | Bui, Vuong |
| contents | Klarner and Rivest showed that the growth of the number of polyominoes, also known as Klarner's constant, is at most $2+2\sqrt{2}<4.83$ by viewing polyominoes as a sequence of twigs with appropriate weights given to each twig and studying the corresponding multivariate generating function. In this short note, we give a simpler proof by a recurrence on an upper bound. In particular, we show that the number of polyominoes with $n$ cells is at most $G(n)$ with $G(0)=G(1)=1$ and for $n\ge 2$, \[
G(n) = 2\sum_{m=1}^{n-1} G(m)G(n-1-m). \] It should be noted that $G(n)$ has multiple combinatorial interpretations in literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20143 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bounding Klarner's constant from above using a simple recurrence Bui, Vuong Combinatorics 05B50, 05A16 Klarner and Rivest showed that the growth of the number of polyominoes, also known as Klarner's constant, is at most $2+2\sqrt{2}<4.83$ by viewing polyominoes as a sequence of twigs with appropriate weights given to each twig and studying the corresponding multivariate generating function. In this short note, we give a simpler proof by a recurrence on an upper bound. In particular, we show that the number of polyominoes with $n$ cells is at most $G(n)$ with $G(0)=G(1)=1$ and for $n\ge 2$, \[ G(n) = 2\sum_{m=1}^{n-1} G(m)G(n-1-m). \] It should be noted that $G(n)$ has multiple combinatorial interpretations in literature. |
| title | Bounding Klarner's constant from above using a simple recurrence |
| topic | Combinatorics 05B50, 05A16 |
| url | https://arxiv.org/abs/2412.20143 |