### Project Euler #78

If you have a pile of n coins, there's some number of distinct ways to divide them up into piles; let's refer to the function that maps a number of coins to the number of ways to divide them up into piles as p. The example they give is for five coins; as you can see, p 5 == 7.

OOOOO

OOOO O

OOO OO

OOO O O

OO OO O

OO O O O

O O O O O

Things to note:

the coins are all alike; it's not like you have different denominations that could distinguish one pile from another with the same number of coins. order doesn't matter; OOO OO and OO OOO don't count as different. One's first inclination is to say "If you create a pile of m coins, that leaves n - m, and there are p (n - m) ways to divide them up, right?" Not exactly; if you don't confine yourself to piles of m or fewer coins, you'll violate (2). So we need what we'll call p', where p' n m is the number of ways to divide up n coins into piles of size m or less. Then you have

p :: Int -> Int

p n = …

OOOOO

OOOO O

OOO OO

OOO O O

OO OO O

OO O O O

O O O O O

Things to note:

the coins are all alike; it's not like you have different denominations that could distinguish one pile from another with the same number of coins. order doesn't matter; OOO OO and OO OOO don't count as different. One's first inclination is to say "If you create a pile of m coins, that leaves n - m, and there are p (n - m) ways to divide them up, right?" Not exactly; if you don't confine yourself to piles of m or fewer coins, you'll violate (2). So we need what we'll call p', where p' n m is the number of ways to divide up n coins into piles of size m or less. Then you have

p :: Int -> Int

p n = …