• LOGIN
  • No products in the cart.

Profile Photo

Partition of a set of functions

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

August 25, 2013

No comments, be the first one to comment !

Leave a Reply

Your email address will not be published. Required fields are marked *

© Cheenta 2017

Login

Register

FACEBOOKGOOGLE Create an Account
Create an Account Back to login/register
X