2
$\begingroup$

I'm searching for a formula to create http://oeis.org/A057537.

  • 0
    See http://math.stackexchange.com/questions/15521/making-change-for-a-dollar-and-other-number-partitioning-problems2011-02-17
  • 1
    It's on OEIS, in the Maple section.2011-02-17

1 Answers 1

1

I would use a recursion. With [the coins and notes] $c(1)$, $c(2)$, $c(3)$,... $c(m)$ in order, smallest first, I would start with $$b(i,j) = 0 \textrm{ for } j<0 \textrm{ or } i<0$$ $$b(i,0) = 1 $$ $$b(0,j) = 0 \textrm{ for } j>0$$ $$b(i,j) = b(i-1,j)+b(i,j-c(j)) \textrm{ for } i,j>0$$ then $b(i,j)$ is the number of ways of making $i$ where the largest part is no bigger than $c(j)$.

So A057537($n$) and similar sequences are simply $b(n,m)$. If the $c(j)$ represent a very large or infinite collection, then you only need to take $m$ large enough, i.e. so $c(m+1)$ is greater than $n$.