Timeline for Bounds on the number of integer compositions with parts bounded from above and below
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17, 2022 at 13:17 | comment | added | blizzard | I mean "same/different" only in the narrow sense of different problems (various combinations of $a$ and $b$) yielding exponential (or not) growth rates of the number of compositions. | |
| Feb 17, 2022 at 13:03 | comment | added | Brendan McKay | @blizzard Why would you expect different problems to have the same asymptotics? But the nature of the asymptotics is the same: $\sim C \alpha^{-n}$ where $C$ and $\alpha$ are constants depending on $a$ and $b$. | |
| Feb 17, 2022 at 12:44 | comment | added | blizzard | Digesting then, different $a, b$ will yield different asymptotics then, correct? Because they determine different roots of the denominator of the generating function. Perhaps this is what @BrendanMcKay meant above? Hence there's no general asymptotic for arbitrary $a$ and $b$ in the range indicated above. | |
| Feb 15, 2022 at 14:39 | comment | added | Max Alekseyev | @blizzard: If the book reference is not enough for you, you'd better seek help at math.stackexchange.com Please notice that MathOverflow is for professional mathematicians (who typically can digest references by themselves). | |
| Feb 15, 2022 at 12:51 | comment | added | blizzard | Thanks but I've (obviously) already read the above and references. My comment can be read as "more explicit high-level description" and "nice[r] and gentle[r] explanation". | |
| Feb 15, 2022 at 11:27 | comment | added | Peter Taylor | @blizzard, the second comment on this answer gives the high-level description and the third comment gives a reference to a book for the nice, gentle explanation. | |
| Feb 15, 2022 at 9:58 | comment | added | blizzard | It would be nice to have the steps that take you from the generating function to the result more explicit. A high-level description of the steps can also help. Otherwise, where can we find a nice, gentle explanation of these steps? | |
| Feb 14, 2022 at 22:16 | comment | added | Max Alekseyev | @blizzard: I'm not sure what mean under "unpacking". Its interpretation is that the coefficient of $x^n$ is big-Theta of $|\alpha|^{-n}$. | |
| Feb 14, 2022 at 18:21 | comment | added | blizzard | Anybody mind unpacking $|\alpha|^{-n}$ and its interpretation in terms of growth of the sequence of coefficients? | |
| Feb 14, 2022 at 15:49 | comment | added | Max Alekseyev | @blizzard: Both Peter and I sum over $k\geq0$, while you sum over $k\geq1$. The extra factor you get does not affect the asymptotic though. | |
| Feb 14, 2022 at 15:05 | comment | added | blizzard | The g.f. I arrive to (take the $[a, n]$ case as example) is different from the above by a factor of $\frac{x^a}{1-x}$. This is because $x^a + x^{a+1} + ... = x^a(1 + x^1 + x^2 + ...) = x^a \frac{1}{1-x}$ and this to the $k$-th power is for compositions of $k$ parts. Therefore we need to sum over $k$, and this gives $$\sum_k (\frac{x^a}{1-x})^k = \frac{x^a}{1-x} \frac{1}{1 - \frac{x^a}{(1-x)}} = \frac{x^a}{1-x-x^a}$$. Is there a mistake in the answer above or in the steps here? | |
| Feb 11, 2022 at 2:51 | comment | added | Brendan McKay | Using the original gf it is easy to see that the complex zero with the smallest absolute value is the smallest positive real zero. | |
| Feb 10, 2022 at 17:26 | comment | added | Max Alekseyev | It's pretty standard argument - e.g. see Chapter 5 in the generatingfunctionology book. | |
| Feb 10, 2022 at 17:24 | comment | added | Peter Taylor | @blizzard, the $[a, n]$ case corresponds to g.f. $\frac{1}{1 - (x^a + x^{a+1} + \cdots)} = \frac{1-x}{1-x - x^a}$. Partial fraction decomposition turns a rational function $\frac{P(x)}{Q(x)}$ into a sum of fractions $\frac{P_\alpha(x)}{x - \alpha} = \frac{-\alpha^{-1} P_\alpha(x)}{1 - \alpha^{-1}x} = -\alpha^{-1}P_{\alpha}(x)(1 + \alpha^{-1}x + \alpha^{-2}x^2 + \cdots)$ where the $\alpha$ are the roots of $Q$. | |
| Feb 10, 2022 at 16:43 | comment | added | blizzard | Would you care to elaborate, step by step with rationale, and perhaps relate the $[a,b]$ case to the $[a,n]$ case? | |
| Feb 10, 2022 at 13:46 | history | undeleted | Max Alekseyev | ||
| Feb 10, 2022 at 13:46 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Feb 10, 2022 at 13:44 | history | deleted | Max Alekseyev | via Vote | |
| Feb 10, 2022 at 13:35 | history | answered | Max Alekseyev | CC BY-SA 4.0 |