Y by
For a finite set
, let
denote the number of elements in the set
.
(a) Let
be the set of all functions
satisfying the condition:
Show that
![\[ |F| = k(k-1)^{n-1}. \]](//latex.artofproblemsolving.com/a/8/8/a88a07984bad88a854de4dad8c24424aaad38365.png)
(b) Let
denote the number of functions in
satisfying
.
For
, show that
![\[ c(n, k) = k(k-1)^{n-1} - c(n-1, k). \]](//latex.artofproblemsolving.com/8/7/2/87285a27401b9853e72b45249196954082d9ec30.png)
(c) Using part (b), prove that for
,
![\[ c(n, k) = (k-1)^n - (-1)^n(k-1). \]](//latex.artofproblemsolving.com/2/f/c/2fcbcb385fcc1b3956232dadfd7ec4a31f4d71d6.png)



(a) Let

![\[ f : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, k\} \quad \text{with } n \geq 3,\; k \geq 2 \]](http://latex.artofproblemsolving.com/b/1/b/b1bf08934378882b9cd0b7d983f83b15453acca9.png)
![\[ f(i) \ne f(i+1) \quad \text{for every } i,\; 1 \leq i \leq n-1. \]](http://latex.artofproblemsolving.com/f/d/1/fd11b44d7fc482b5c6018e19161f6e30b7835c2d.png)
![\[ |F| = k(k-1)^{n-1}. \]](http://latex.artofproblemsolving.com/a/8/8/a88a07984bad88a854de4dad8c24424aaad38365.png)
(b) Let



For

![\[ c(n, k) = k(k-1)^{n-1} - c(n-1, k). \]](http://latex.artofproblemsolving.com/8/7/2/87285a27401b9853e72b45249196954082d9ec30.png)
(c) Using part (b), prove that for

![\[ c(n, k) = (k-1)^n - (-1)^n(k-1). \]](http://latex.artofproblemsolving.com/2/f/c/2fcbcb385fcc1b3956232dadfd7ec4a31f4d71d6.png)