Test of Mathematics Solution Subjective 55 - Partition of a set of functions

This is a Test of Mathematics Solution Subjective 55 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

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) $