Introduction to Discrete Mathematics, Fall 2000
Problem Set 5, 24-26 October

1. Consider a system of $n$ non-parallel lines in the plane, no three of which intersect at the same point. (One can think of the lines having been drawn in sequence so that each ``new'' line intersects all the ``old'' lines, each at a different point.) Denote by $a_n$ the number of planar subdivisions thus formed, i.e. $a_0 = 1$, $a_1 = 2$, $a_2 = 4$, $a_3 = 7$ etc. Find a recurrence equation for the sequence $a_n$ and solve it.

2. Solve, using generating functions, the recurrence:
   
   $$\left\{\begin{array}{l} a_0 = 0, \quad a_1 = 1,\\ a_n = a_{n-1} + 6a_{n-2}+2^n, \quad n \geq 2. \end{array}\right.$$
   
   

3. Establish, using generating functions, the summation rule for binomial coefficients known as the Vandermonde convolution:
   
   $$\sum_{k=0}^n {{r}\choose{k}}{{s}\choose{n-k}} = {{r+s}\choose{n}}.$$
   
   
   (Hint: $(1+x)^r(1+x)^s = (1+x)^{r+s}$.) Can you come up with a purely combinatorial proof of the result?

4. How many integer solutions does the equation $a+b+c=10$ have, under the constraints that the value of each variable must be at least 2 and at most 5?

5. The Council of the Faculty of Combination Technology consists of 9 representatives from three groups: professors, other staff, and students. In how many ways can the Council be composed so that each group gets at least one representative, but no group has an absolute majority on its own? (Hint: Apply the summation formula $1+x+x^2+\cdots+x^n = \frac{1-x^{n+1}}{1-x}$, and the results of Problem 5 in the previous Problem Set.)

6. A box contains 30 blue, 40 red, and 50 green balls. How many different selections of 70 balls can be made from its contents? (Hint: As in the preceding Problem.)

7. The cash register line at the University cafeteria has $2n$ randomly ordered students waiting to pay for their food. A student lunch costs 10 FIM, and half of the students are in possession of a 10 FIM coin, while the other half only have 20 FIM bills. Initially, the cash register of the cafeteria is empty. What is the probability that the register can serve all the $2n$ students, without running out of change at any point? (Hint: Let $s_n$ denote the number of those favourable student lineups, where the cash register contains a nonnegative amount of money throughout the whole process. Clearly $s_1 = 1$. The value of $s_n$, for $n > 1$, can be deduced e.g. by considering after how many student pairs the amount of money in the register first returns to zero. If this happens only at the very end, then it must have been the case that the first student had a 10 FIM coin, the last student had a 20 FIM bill, and throughout the whole intermediate interval the register contained a positive amount of money: there are a total of $s_{n-1}$ such lineups. Otherwise there is some smallest number $k$ of student pairs, $1 \leq k \leq n-1$, after which the register returns to zero. In this case ... [Note: You need to know about Catalan numbers to solve this problem.])

The first Midterm Exam of the course takes place on Wed 25 October at 8-11 a.m. The exam covers the material discussed in Problem Sets 1 thru 5.