Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2410.18534 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929556812726272 |
|---|---|
| author | Bui, Vuong |
| author_facet | Bui, Vuong |
| contents | Generalizing some popular sequences like Catalan's number, Schröder's number, etc, we consider the sequence $s_n$ with $s_0=1$ and for $n\ge 1$, \begin{multline*}
s_n=\sum_{x_1+\dots+x_{\ell_1}=n-1} κ_1 s_{x_1}\dots s_{x_{\ell_1}} + \dots +\sum_{x_1+\dots+x_{\ell_{t'}}=n-1} κ_{t'} s_{x_1}\dots s_{x_{\ell_{t'}}}+\\ \max_{x_1+\dots+x_{\ell_{t'+1}}=n-1} κ_{t'+1} s_{x_1}\dots s_{x_{\ell_{t'+1}}} + \dots + \max_{x_1+\dots+x_{\ell_t}=n-1} κ_t s_{x_1}\dots s_{x_{\ell_t}}, \end{multline*} where $x_i$ are nonnegative integers, $\ell_1,\dots,\ell_t$ are positive integers, and $κ_1,\dots,κ_t$ are positive reals. We show that it is possible to compute the growth rate $λ$ of $s_n$ to any precision. In particular, for every $n\ge 2$,
\[
\sqrt[n]{\frac{κ^*}{\mathcal L(n-1) s_1} s_n} \le λ\le \sqrt[n]{3^{18\log 3 + 2\log\frac{s_1\mathcal L^2}{κ^*}} n^{3\log n + 12\log 3 + \log\frac{s_1\mathcal L^2}{κ^*}} s_n},
\]where $\mathcal L=\max_i \ell_i$ and $κ^*=κ_i$ for some $i$ with $\ell_i\ge 2$, and the logarithm has the base $\frac{\mathcal L+1}{\mathcal L}$. The constants in the inequalities are not very well optimized and serve mostly as a proof of concept with the ratio of the upper bound and the lower bound converging to $1$ as $n$ goes to infinity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18534 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Growth of recurrences with mixed multifold convolutions Bui, Vuong Combinatorics Generalizing some popular sequences like Catalan's number, Schröder's number, etc, we consider the sequence $s_n$ with $s_0=1$ and for $n\ge 1$, \begin{multline*} s_n=\sum_{x_1+\dots+x_{\ell_1}=n-1} κ_1 s_{x_1}\dots s_{x_{\ell_1}} + \dots +\sum_{x_1+\dots+x_{\ell_{t'}}=n-1} κ_{t'} s_{x_1}\dots s_{x_{\ell_{t'}}}+\\ \max_{x_1+\dots+x_{\ell_{t'+1}}=n-1} κ_{t'+1} s_{x_1}\dots s_{x_{\ell_{t'+1}}} + \dots + \max_{x_1+\dots+x_{\ell_t}=n-1} κ_t s_{x_1}\dots s_{x_{\ell_t}}, \end{multline*} where $x_i$ are nonnegative integers, $\ell_1,\dots,\ell_t$ are positive integers, and $κ_1,\dots,κ_t$ are positive reals. We show that it is possible to compute the growth rate $λ$ of $s_n$ to any precision. In particular, for every $n\ge 2$, \[ \sqrt[n]{\frac{κ^*}{\mathcal L(n-1) s_1} s_n} \le λ\le \sqrt[n]{3^{18\log 3 + 2\log\frac{s_1\mathcal L^2}{κ^*}} n^{3\log n + 12\log 3 + \log\frac{s_1\mathcal L^2}{κ^*}} s_n}, \]where $\mathcal L=\max_i \ell_i$ and $κ^*=κ_i$ for some $i$ with $\ell_i\ge 2$, and the logarithm has the base $\frac{\mathcal L+1}{\mathcal L}$. The constants in the inequalities are not very well optimized and serve mostly as a proof of concept with the ratio of the upper bound and the lower bound converging to $1$ as $n$ goes to infinity. |
| title | Growth of recurrences with mixed multifold convolutions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.18534 |