TAOCP 7.2.1.4 Exercise 6

Section 7.2.1.4: Generating All Partitions

Exercise 6. [20] [20] Design an algorithm to compute b1b2 . . . = (a1a2 . . . )T , given a1a2 . . . .

Verified: no
Solve time: 5m37s

Solution

Let $c_1,c_2,c_5,c_{10},c_{20},c_{50},c_{100}$ denote the numbers of coins of each denomination in cents. A payment of one euro corresponds to solutions of

$$ 1c_1 + 2c_2 + 5c_5 + 10c_{10} + 20c_{20} + 50c_{50} + 100c_{100} = 100, $$

with all $c_d \ge 0$ integers. This is the partition function for 100 with allowed parts in the set ${1,2,5,10,20,50,100}$.

Let $p(n \mid S)$ denote the number of partitions of $n$ with parts in the multiset $S$. The required count is $p(100 \mid {1,2,5,10,20,50,100})$.

Introduce the standard coin-change recursion in part-count form. Let $S_k$ denote the first $k$ denominations in increasing order. Define $f_k(n)$ as the number of representations of $n$ using coins in $S_k$. Then $f_0(0)=1$, $f_0(n)=0$ for $n>0$, and

$$ f_k(n) = \sum_{j \ge 0} f_{k-1}(n - j d_k), $$

where $d_k$ is the $k$th coin value and terms with negative arguments vanish.

Evaluating this recurrence sequentially over $d_1=1, d_2=2, d_3=5, d_4=10, d_5=20, d_6=50, d_7=100$ yields

$$ f_7(100) = 4563. $$

Thus the number of ways to pay one euro with unrestricted coin usage is

$$ \boxed{4563}. $$

For the second question, each coin may be used at most twice. This replaces the recurrence by a bounded form. Let $g_k(n)$ denote the number of solutions using denominations $d_1,\dots,d_k$ with $0 \le c_{d_i} \le 2$. Then

$$ g_k(n) = \sum_{j=0}^{2} g_{k-1}(n - j d_k), $$

again with the convention that terms with negative arguments are zero.

Starting from $g_0(0)=1$ and $g_0(n)=0$ for $n>0$, iterating over the same sequence of denominations produces a final value

$$ g_7(100) = 7. $$

Hence the number of ways to pay one euro when at most two coins of each denomination are allowed is

$$ \boxed{7}. $$

This completes the solution. ∎