function that counts...

[Bryan]

Lie Ryan wrote:
> I went through the mathematical foundation of using
> partition/distribution and inclusion-exclusion, and have written some
> code that solves a subset of the problem, feel free if you or superpollo
> are interested in continuing my answer (I won't be able to continue it
> until next week, have been a little bit busy here)
>
> copying the code here for convenience:
>
> # memoization would be very useful here
> def fact(n):
>     """ factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
>     return n * fact(n - 1) if n != 0 else 1
>
> def C(n, r):
>     """ regular Combination (nCr) """
>     return fact(n) / (fact(n - r) * fact(r))
>
> def D(M, N):
>     """ Distribution aka Partitioning """
>     return C(M + N - 1, M)
>
> def partition10(M, i):
>     """ Count how many integer < N sums to M where N = 10**int(i) """
>     s = 0
>     sign = 1
>     for j in range(i + 1):
>         s += sign * D(M, i) * C(i, j)
>
>         # flip the sign for inclusion-exclusion
>         sign *= -1
>
>         # if M = 32, then 32, 22, 12, 2, -8
>         M -= 10
>     return s

It doesn't seem to work. I get no answer at all, because it recursion-
loops out when it calls fact() with a negative integer.

--
--Bryan