Introduction to Discrete Mathematics, Fall 2000
Problem Set 3, 10-12 October

1. In how many ways can 6 identical balls be coloured using three colours? What if the balls are distinguishable (e.g. of different sizes)? How many of the colourings contain balls of all three colours, when the balls are (a) identical, (b) distinguishable?

2. How many nonnegative integer triples $(k,l,m) \in {\mathbf N}^3$ are contained in the plane $\{(x,y,z) \in {\mathbf R}^3 \;\vert\; x + y + z = 10\}$?

3. How many different game situations (configurations) are possible after two plys (move pairs) in a game of tic-tac-toe on a 3-by-3 board? The board is thought to have a fixed orientation, so that the ``equivalence'' of situations under reflections or rotations of the board need not be considered.

4. How many partitions (equivalence relations) are possible on the set $A = \{a,b,c,d\}$? Enumerate them.

5. [Finnish content.]
   1. How many anagrams can one obtain from the word TIIVITAAVI? (Two words are anagrams, if they contain the same letters in a different order. In the present problem the anagrams do not need to conform to any phonetic rules.)
   2. In how many ways can the lecturer (PO) and the four Teletubbies (Finnish names: Tiivi-Taavi, Hipsu, Laa-Laa, Pai) be grouped into four nonempty groups.

6. The DNA nucleotide sequences that act as the carrier of biological hereditary information can be viewed as words over the four-letter alphabet $\{A, T, G, C\}$, where the letters correspond to the nucleotide bases adenine, thymine, guamine, and cytosine. How many different nucleotide sequences of length 6 are possible? How many of these contain at least one instance of each base? How many are such that no base occurs in two adjacent positions?

7. Establish the correctness of the following formula for representing the integral powers of a number $n$ in terms of binomial coefficients:
   
   $$n^p = \sum_{r=1}^p S(p,r)r!{{n}\choose{r}}.$$
   
   
   (Hint: Consider different ways of selecting a sequence of length $p$ from a basis set of $n$ elements.) Represent the cube $k^3$ as a sum of the binomial coefficients ${{k}\choose{i}}$, $1 \leq i \leq 3$. Prove, using this representation and the summation formula from problem 4(c) in the previous problem set, the summation formula for integral cubes:
   
   $$1^3 + 2^3 + \cdots n^3 = \frac{1}{4}n^2(n+1)^2.$$