How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

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

Test of Mathematics at the 10+2 Level

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


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


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

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.