General form for this problem

Question

I encountered this problem by Polya about counting the number of ways that a dollar can be changed. Suppose that there are pennies (worth 1), nickels (worth 5), dimes (worth 10), quarters (worth 25) and fiftycent coins (worth 50). The number of ways to change a dollar (worth 100) can be written as the following generating function:

$$
D(z) = \sum_p z^p \sum_n z^{5n} \sum_d z^{10d} \sum_q z^{25q} \sum_f z^{50f}
$$

where $D(z)$ is:

$$
\frac{1}{(1-z)(1-z^5)(1-z^{10})(1-z^{25})(1-z^{50})}
$$

I understand the generating function, but is there a general form to express its coefficients given any set of denominations ? i.e. How to dervive $[z^n]D(z)$, where:

$$
D(z) = a_0z^0 + a_1z^1 + a_2z^2 + …
$$

and the coefficient $a_k$ of $z^k$ express the number of ways that an amount worth $k$ can be arrived at given denominations $\{d_1,d_2,d_3,…,d_n\}$, i.e. in the example above, we have $n=5$ and $d_1=1,d_2=5,d_3=10,d_4=25,d_5=50$.

EDIT:

It looks like that a general form for this problem is hard to compute … (the problem hints that a computer simulation may be needed) … However, it looks like that $D(z)$ is asymptotic to the following formula, where $N$ represents the denomination of the bill, i.e. if it is a dollar, we have $N=100$

$$
\frac{N^{t-1}}{d_1d_2,…,d_t(t-1)!}
$$

Is there an explanation why $D(z)$ has this asymptotic form ?

Answer 1

Coefficient extraction:

We have \begin{align*} D(z)&=\frac{1}{\left(1-z\right)\left(1-z^5\right)\left(1-z^{10}\right)\left(1-z^{25}\right)\left(1-z^{50}\right)} \end{align*}

We know from this answer \begin{align*} A(z)&=\frac{1}{\left(1-z\right)\left(1-z^5\right)\left(1-z^{10}\right)}\\ &=\sum_{m=0}^\infty\left(\frac{1}{4}\left\lfloor\frac{m}{5}\right\rfloor^2+\frac{5}{4}\left\lfloor\frac{m}{5}\right\rfloor -\frac{1}{2}\left\lfloor\frac{m}{10}+\frac{1}{2}\right\rfloor+1\right)z^m\tag{1} \end{align*}

We calculate analogously \begin{align*} \color{blue}{B(z)}&=\frac{1}{\left(1-z^{25}\right)\left(1-z^{50}\right)}\\ &=\sum_{q=0}^\infty z^{25q}\sum_{f=0}^\infty z^{50f}\\ &=\sum_{n=0}^\infty\left(\sum_{{25q+50f=n}\atop{q,f\geq 0}}\right)z^n\\ &=\sum_{n=0}^\infty\left(\sum_{{2q+f=n}\atop{q,f\geq 0}}\right)z^{25n}\\ &=\sum_{n=0}^\infty\left(\sum_{q=0}^{\lfloor n/2\rfloor}1\right)z^{25n}\\ &\,\,\color{blue}{=\sum_{n=0}^\infty\left(\left\lfloor \frac{n}{2}\right\rfloor+1\right)z^{25n}}\tag{2} \end{align*}

Using the coefficient of operator $[z^t]$ to denote the coefficient of $z^t$ of a series we obtain from (1) and (2) \begin{align*} \color{blue}{[z^t]}&\color{blue}{D(z)}=[z^t]A(z)B(z)=[z^t]\sum_{m=0}^\infty a_mz^m\sum_{n=0}^\infty b_nz^{25n}\\ &=[z^t]\sum_{q=0}^\infty\left(\sum_{{m+25n=q}\atop{m,n\geq 0}}a_mb_n\right)z^q\\ &=[z^t]\sum_{q=0}^\infty\left(\sum_{n=0}^{\lfloor q/25\rfloor}a_{q-25n}b_n\right)z^q\\ &=\sum_{n=0}^{\lfloor t/25\rfloor}a_{t-25n}b_n\\ &=\sum_{n=0}^{\lfloor t/25\rfloor} \left(\frac{1}{4}\left\lfloor\frac{t-25n}{5}\right\rfloor^2+\frac{5}{4}\left\lfloor\frac{t-25n}{5}\right\rfloor -\frac{1}{2}\left\lfloor\frac{t-25n}{10}+\frac{1}{2}\right\rfloor+1\right)\\ &\qquad\qquad\quad\cdot \left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)\\ &\,\,\color{blue}{=\sum_{n=0}^{\lfloor t/25\rfloor} \left(\frac{1}{4}\left(\left\lfloor\frac{t}{5}\right\rfloor-5n\right)^2+\frac{5}{4}\left(\left\lfloor\frac{t}{5}\right\rfloor-5n\right) -\frac{1}{2}\left\lfloor\frac{t}{10}-\frac{5n}{2}+\frac{1}{2}\right\rfloor+1\right)}\\ &\qquad\qquad\quad\color{blue}{\cdot \left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)}\tag{3} \end{align*}

It seems, the result (3) can be considerably simplified, since we obtain with the help of Wolfram alpha the nice representation

\begin{align*} D(z)&=\color{blue}{1} + z + z^2 + z^3 + z^4\\ &\qquad + \color{blue}{2} z^5 + 2 z^6 + 2 z^7 + 2 z^8 + 2 z^9 \\ &\qquad+ \color{blue}{4} z^{10} + 4 z^{11} + 4 z^{12} + 4 z^{13} + 4 z^{14}\\ &\qquad+ \color{blue}{6 }z^{15} + 6 z^{16} + 6 z^{17} + 6 z^{18} + 6 z^{19}\\ &\qquad + \color{blue}{9} z^{20} + 9 z^{21} + 9 z^{22}+ 9 z^{23} + 9 z^{24}\\ &\qquad + \color{blue}{13}z^{25} + 13 z^{26} + 13 z^{27} + 13 z^{28} + 13 z^{29}\\ &\qquad + \color{blue}{18} z^{30} + 18 z^{31} + 18 z^{32} + 18 z^{33} + 18 z^{34}\\ &\qquad+ \color{blue}{24} z^{35} + 24 z^{36}+ 24 z^{37} + 24 z^{38} + 24 z^{39}\\ &\qquad + \color{blue}{31} z^{40} + 31 z^{41} + 31 z^{42} + 31 z^{43} + 31 z^{44}\\ &\qquad+ \color{blue}{39} z^{45} + 39 z^{46 }+ 39 z^{47} + 39 z^{48} + 39 z^{49}\\ &\qquad + O(z^{50}) \end{align*} with equal coefficients in groups of five.

First-order Asymptotics:

The asymptotic estimation of OP is correct. We find in chapter IV: Complex Analysis, Rational and Meromorphic Asymptotics of Analytic Combinatorics by P. Flajolet and R. Sedgewick the

Proposition IV.2: Let $T$ be a finite set of integers without a common divisor ($\gcd(T) = 1$). The number of partitions with summands restricted to $T$ satisfies \begin{align*} P_t^{T}\sim\frac{1}{\tau}\,\frac{t^{r-1}}{(r-1)!},\qquad \text{ with }\tau:=\prod_{\omega\in T}\omega,\qquad r:= \mathrm{card}(T) \end{align*}

Here we consider \begin{align*} [z^t]D(z)=[z^t]\frac{1}{\left(1-z\right)\left(1-z^5\right)\left(1-z^{10}\right)\left(1-z^{25}\right)\left(1-z^{50}\right)}\tag{4} \end{align*} For first-order asymptotic of coefficients in (4) only the pole at $z=1$, which is the nearest pole to $0$ with highest order $5$ needs to be considered.

We have according to (4) $T=\{1,5,10,25,50\},\tau=1\cdot5\cdot10\cdot25\cdot50,r=4$ from which \begin{align*} \color{blue}{[z^t]D(z)\sim} \frac{1}{1\cdot5\cdot10\cdot25\cdot50}\,\frac{t^4}{4!}=\color{blue}{\frac{2}{3}10^{-6}t^4} \end{align*} follows.

Chapter 4 of the book provides all the necessary information to derive this asymptotic estimation.