### Project Euler #78

If you have a pile of

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;

**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 = …p n = …

**
**