3a)
There is no restriction on the number of each kind of coin.
Suppose you have a word of 8+5-1 = 12 letters 'O' :
OOOOOOOOOOOO
Now decide where you place 5-1 = 4 letters 'X' :
OXOXOOOXOXOO
Letters 'X' are separators between all different kind of coins.
The above word means :
1 penny - 1 nickel - 3 dimes - 1 quarter - 2 half-dollars
Each one of those words corresponds to a distribution of coins, and each distribution of coins corresponds to one of those words.
The number of all different such words is the number of choices of 4 places among 12 : this is a binomial coefficient, equals to 12 x 11 x 10 x 9 / ( 4 x 3 x 2 x 1) = 495
3bcde)
I don't know how to solve that kind of problem in a general way. Let me know if this something of interest for you, I could try to find something.
Given your values, I would simply proceed by subtracting impossible distributions :
b ) 9 coins :
subtract 1 impossible distribution (9 half-dollars)
answer = binom(13,4) - 1
c) 10 coins :
subtract 6 impossible distributions ( 10 half-dollars, or 9 half-dollars and 1 random coin, or 10 quarters)
answer = binom(14,4) - 6
d) 11 coins :
subtract 23 impossible distributions (I let you do the list)
answer = binom(15,4) - 23
e) 11 coins with at least 1 of each.
This is the same problem as picking 6 coins from piles consisting in 9 pennies, 9 nickels, 9 dimes, 8 quarters, 7 half-dollars (hence, no restriction)
answer = binom(10,4)
4) Another very interesting problem.
Let n an integer, and Un the number of n-digits strings without 3 '0' in a row.
U0 = 1 (empty string) = 2^0
U1 = 2 = 2^1
U2 = 4 = 2^2
U3 = 8 - 1 = 7, because obviously, all the 2^3 = 8 strings of length 3 are good, except '000'.
Now, proceed by induction :
Consider a string of length n+3 with no '000' :
the finishing part can be :
100
X10
XX1
where X denotes, indifferently, 0 or 1.
if the finishing part is 100, then all the n first digits must form a random working string : there are U_n of such strings.
if the finishing part is X10, then all the (n+1) first digits must form a random working string : there are U_(n+1) of such strings.
if the finishing part is XX1, then all the (n+2) first digits must form a random working string : there are U_(n+2) of such strings.
Hence : U_(n+3) = U_(n+2) + U_(n+1) + U_n
It's enough to compute the answer : U_13 = 3136
If you want a formula with variable 'n', then you must first solve : X^3 - X^2 - X - 1 = 0
Let me know, in this case, I'll go deeper into it.
5)
a) This is the same problem as 3)
Each child is a different kind of coin :
child #1 is a penny
child #2 is a nickel
...
child #6 is $1 banknote
Would you decide to give 2 candies to child1, and 18 candies to child2 (and no candy to other children), then that's a pile of 2 pennies and 18 nickels.
Answer = binom(25,5) = 25 x 24 x 23 x 22 x 21 / ( 5 x 4 x 3 x 2 x 1 )
b ) Give them 1 candy, and now, make a distribution of 15 candies to 6 children.
Answer = binom(20,5)
c) The problem seems to me very different now.
You must find the number of partitions of 20 into a sum of ordered and different non negative integers.
Notice that 1 children must recieve no candy (because 1+2+3+4+5+6 > 20).
ie :
20 = 0 + 1 + 2 + 3 + 4 + 10
20 = 0 + 1 + 2 + 3 + 5 + 9
20 = 0 + 1 + 2 + 3 + 6 + 8
20 = 0 + 1 + 2 + 4 + 5 + 8
20 = 0 + 1 + 2 + 4 + 6 + 7
20 = 0 + 1 + 3 + 4 + 5 + 7
there are only 6 different possibilities to form 6 piles of candies without the same number of candies.
Now it's time to give 1 pile to each child : this is a permutation of a set of 6 items : 6 ! = 6 x 5 x 4 x 3 x 2 x 1 possibilities.
Answer = 6 x 6 !
This post was edited by feanur on Nov 11 2018 02:06pm