HHC 2016 RPN contest is now live

[Paul Dale]

Some explanation about my approach.

We're looking for \( \sum_{i=1}^{k}x_i = n \) where each \( x_i \) is a single digit. Without the single digit restriction, there are \( \binom{n+k-1}{k-1} \) possibilities (see e.g. here).

To enforce the must be a digit restriction use the inclusion-exclusion principle to remove the illegal cases with digits > 10 from the above result.

A bit of fiddling around gives: \( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} \)

However, this allows leading zeros, so we do the summation a second time for k-1 instead of k and subtract that from the first sum to get the result:

\( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} - \sum_{i=0}^{min(k-1, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k-1}{i} \binom{n+k-10i-2}{k-2} \)

I feel that there should be a more direct approach, but can't see it. My allergies have been dreadful for the last week and I'm not thinking even close to straight, so I could easily be completely wrong about all of this.


- Pauli