For a finite set A, let |A| denote the number of elements in set A.

(a) Let F be the set of all functions f:{1, 2, … , n} –> {1, 2, … , k}  (n \ge 3, k \ge 2 ) satisfying f(i) \ne f(i+1) for every i, 1\le i \le n-1 . Show that |F| = k(k-1)^{(n-1)}.

Solution: The function f may take the element 1 in domain to one of the k numbers in codomain (k choices for 1). Since f(2) cannot equal f(1), we have (k-1) choices for 2 to go. Similarly f(3) cannot equal f(2) (but it can equal f(1)) so there are k-1 choices for 3 and so on. In total the number of functions possible equals k \times (k-1) \times (k-1) ... (n-1) \times = k (k-1)^{(n-1)} .

(b) Let c(n,k) denote the number of functions in F such that f(n) \ne f(1) , n \ge 4. Then show that c(n,k) = k(k-1)^{(n-1)} - c(n-1, k)

Solution: We consider the following partition of the set of functions F:
(1) functions in which f(n) \ne f(1)
(2) functions in which f(n) = f(1)
Note the above partition is well defined as they are mutually exclusive and exhaustive. Functions of type (1) are given by c(n, k) and functions of type two is given by c(n-1, k) because if f(n) = f(1), f(n-1) cannot equal f(1) as F contains functions for which f(i) \ne f(i+1)
As functions of type 1 and type 2
makes up all the functions in F we have c(n,k) + c(n-1, k) = k(k-1)^{(n-1)} .

(c) Using part (b) or otherwise prove c(n, k) = (k-1)^{(n-1)} + (-1)^n (k-1)

Solution: We use induction on part (b). Suppose c(n, k) = (k-1)^{(n-1)} + (-1)^n (k-1) . Then c(n+1, k) = k (k-1)^{(n)} - c(n, k) = k (k-1)^{(n)} - (k-1)^{(n-1)} + (-1)^n (k-1)