Proving optimized function is still correct

[Terry Reedy]

"Terry Reedy" <tjreedy at home.com> wrote in message
news:ct2I7.212078$5A3.78366686 at news1.rdc2.pa.home.com...
>
> <salvasan at yahoo.com> wrote in message
> news:9sq46c$o93$1 at news.carib-link.net...
> > I gave a colleague of mine a Python function to optimise:
...
> description of what your function computes:  the number of ways of
> distributing n indistinguishable items among m labelled bins, with
> bins possibly left empty, and where 'labelled' means that each
> permutation among bins is counted separately.
...
> The following is a more direct recursion:
...
> def d(m,n):
>   if m == 1 or n == 0: return 1
>   cnt = 0
>   for i in range(n+1): cnt = cnt + d(m-1,n-i) # put i items in 1 bin
and distribute rest
>   return cnt

After posting above, I realized that
d(m,n) == sum(i=0,n; d(m-1, n-i)) == sum(i=n,0; d(m-1,n-i)) ==
sum(i=0,n; d(m-1,i)) and
d(m,n-1) = = sum(i=0,n-1; d(m-1,i))  imply the simpler recursion
d(m,n) = d(m,n-1) + d(m-1,n), with easily proven solution
(n+m-1)!/n!(m-1)!.

A recursive implementation like

def d(m,n):   return (m == 1 or n == 0) and 1 or d(m,n-1) + d(m-1,n)

is inefficient in the same way as recursive fibonacci

def fib(n): return n <= 1 and 1 or fib(n-2) + fib(n-1)

in that both needlessly recompute the function for 'lower' values of
the parameter(s).  The following iterative solution computes each
function value only once.

def d2(m,n):
  if m == 1 or n == 0: return 1
  temp = (n+1) * [1] # change 1 to 1L to force long computation to
avoid overflow
  for i in range(2,m+1):
    for ni in range(1,n+1):
       temp[ni] = temp[ni-1] + temp[ni]
  return temp[n]

>>> d2(6,4)
126

Unlike the factorial formula, this does not overflow until the answer
does.  If one needed to call this function many times for small enough
values of m and n, one could modify d2 to save all computed values in
a table for later lookup.

Terry J. Reedy