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.

Answer 2

If you have a closed formula for your generating function $D(z)$, all you have to do to obtained its coefficients differentiate several times and evaluate at zero.

This works since if $$ D(z) = a_0 + a_1 z + a_2 z^2 + ...$$ then we have that $$a_k = \frac{D^{(k)}(0)}{k!},$$ and this is easy enough to compute for finite $k$ with a bit of Maple/Mathematica/Sympy.

If this is not the kind of closed formula you're after, you will have to look at the comment of Matti P and Somos to find a different closed expresion in terms of finite sums.