What is the generating function for the number of ways to pass out \(k\) pieces of candy from an unlimited supply of identical candy to \(n\) children (where \(n\) is fixed) so that each child gets between three and six pieces of candy (inclusive)? Use the fact that
to find a formula for the number of ways to pass out the candy.
In paying off a mortgage loan with initial amount \(A\text{,}\) annual interest rate \(p\)% on a monthly basis with a monthly payment of \(m\text{,}\) what recurrence describes the amount owed after \(n\) months of payments in terms of the amount owed after \(n-1\) months? Some technical details: You make the first payment after one month. The amount of interest included in your monthly payment is \(.01p/12\text{.}\) This interest rate is applied to the amount you owed immediately after making your last monthly payment.
Find a formula for the amount owed after \(n\) months.
Find a formula for the number of months needed to bring the amount owed to zero. Another technical point: If you were to make the standard monthly payment \(m\) in the last month, you might actually end up owing a negative amount of money. Therefore it is ok if the result of your formula for the number of months needed gives a non-integer number of months. The bank would just round up to the next integer and adjust your payment so your balance comes out to zero.
What should the monthly payment be to pay off the loan over a period of 30 years?
We have said that for nonnegative \(i\) and positive \(n\) we want to define \(\binom{-n}{i}\) to be \(\binom{n+i-1}{i}\text{.}\) If we want the Pascal recurrence to be valid, how should we define \(\binom{-n}{-i}\) when \(n\) and \(i\) are both positive?
Find a recurrence relation for the number of ways to divide a convex \(n\)-gon into triangles by means of non-intersecting diagonals. How do these numbers relate to the Catalan numbers?
How does \(\sum_{k=0}^n\binom{n-k}{k}\) relate to the Fibonacci Numbers?
Let \(m\) and \(n\) be fixed. Express the generating function for the number of \(k\)-element multisets of an \(n\)-element set such that no element appears more than \(m\) times as a quotient of two polynomials. Use this expression to get a formula for the number of \(k\)-element multisets of an \(n\)-element set such that no element appears more than \(m\) times.
One natural but oversimplified model for the growth of a tree is that all new wood grows from the previous year's growth and is proportional to it in amount. To be more precise, assume that the (total) length of the new growth in a given year is the constant \(c\) times the (total) length of new growth in the previous year. Write down a recurrence for the total length \(a_n\) of all the branches of the tree at the end of growing season \(n\text{.}\) Find the general solution to your recurrence relation. Assume that we begin with a one meter cutting of new wood (from the previous year) which branches out and grows a total of two meters of new wood in the first year. What will the total length of all the branches of the tree be at the end of \(n\) years?
(Relevant to Appendix C) We have some chairs which we are going to paint with red, white, blue, green, yellow and purple paint. Suppose that we may paint any number of chairs red or white, that we may paint at most one chair blue, at most three chairs green, only an even number of chairs yellow, and only a multiple of four chairs purple. In how many ways may we paint \(n\) chairs?
What is the generating function for the number of partitions of an integer in which each part is used at most \(m\) times? Why is this also the generating function for partitions in which consecutive parts (in a decreasing list representation) differ by at most \(m\) and the smallest part is also at most \(m\text{?}\)
