9 coin sum problem

In the 4-coin case, each selection has a different value. Proof: the values of the four types coins are 1 + 0, 1 + 4, 1 + 9, and 1 + 24, so the sum of four coins = 4 + 4N + 9D + 24Q, where N, D, and Q are the numbers of nickels, dimes, and quarters, respectively. Given that N and D are each 0, 1, or 2, no combination of N and D matches any other combination.
That being said, the most popular combination is one of each coin - there are 2 x 2 x 2 x 3 = 24 ways to do this - so the most common sum is 1 + 5 + 10 + 25 = 41.

Actually, I can't think of a better way of doing this than counting each possible combination, determining its value and how many ways there are to do it, then summing the number of ways for each distinct value.

Easy, once you know the solution to 4 coins; the sum of 5 coins = the sum of all 9 coins - the sum of the other 4 coins, so the most common sum of 5 coins taken out of your purse = the sum of all nine coins - the most common sum of 4 coins left in your purse, or 107 - 41 = 66

Select 2, Sum 30
Select 3, Sum 40
Select 4, Sum 41
Select 5, Sum 66
Select 6, Sum 76
Select 7, Sum 77
Select 8, Sum 82
Select 9, Sum 107

Code: https://pastebin.com/ExeNXKC3

The easiest way is to consider all outcomes of how many coins of each rank there are.
This means (1c, 5c, 10c, 25c):(2,2,0,0), (2,1,1,0) etc. A little thought shows all combinations have unique monetary values (consider 5N+2, 5N+1, 5N+0).
The number of combinations of each is (if #1c coins = 1, then 2, else 1)*(if #5c coins = 1, then 2, else 1)*(if #10c coins = 1, then 2, else 1)*(if #25c coins = 1or2, then 3, else 1). Thus (1,1,1,1) is the most common as this uses all the "then" rather than "else 1".
Using a list of all the possible combinations gives the average is 47 5/9.

Five coins is exactly the same logic. Take all 9 coins and put four back, this leaves you five. The most common "left behind" is (1,1,1,1) so the ost common you have is (1,1,1,2). Similarly the average would be 1+1+5+5+10+10+25+25+25-47 5/9.