3
$\begingroup$

Let $A$ be a set with six elements and $f$ be a function from $A$ to $A$. Then how to find number of functions $f$ such that $f$ contains exactly three elements in its image.

My idea is to use multiplication principle. Let $$ A = \{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\}, $$ then the total number of functions will be $\binom{6}{3} \cdot 6 \cdot 5 \cdot 4$, because first first elements can have six choices and second can have five and third can have four, and number of sets with three elements in $A$ are $\binom{6}{3}$. Is it correct?

$\endgroup$

1 Answer 1

2
$\begingroup$

Your answer is incorrect. Two functions are distinguished by which element is mapped to which element.

There are $\binom{6}{3}$ ways to exclude three of the six elements in set $A$ from the image.

That leaves three possible images for each of the six elements in the domain. Hence, there are $3^6$ functions from set $A$ to the three elements in set $A$ we have not excluded. However, some of these functions do not have three elements in their image. We must subtract those functions which miss one or more of the three elements we have not excluded from the image.

There are $\binom{3}{k}$ ways to exclude $k$ of the three remaining elements and $(3 - k)^6$ functions from set $A$ to the remaining elements. Hence, by the Inclusion-Exclusion Principle, the number of functions $f: A \to A$ such that $f$ contains exactly three elements in its image is $$\binom{6}{3}\left[3^6 - \binom{3}{1}2^6 + \binom{3}{2}1^6\right]$$

Notice that if you want to count directly, you have to choose an image for each of the six elements in such a way that exactly three elements are in the range. You would have to choose which three elements were in the range and then consider three cases:

  • Four elements are mapped to the same element of set $A$, with two other elements each being the image of one of the other two elements in set $A$
  • Three elements are mapped to one element of set $A$, two elements are mapped to another element, and one element is mapped to a third element of set $A$
  • Three elements of set $A$ are each the images of two elements of set $A$

That gives a count of $$\binom{6}{3}\left[\binom{3}{1}\binom{6}{4}2! + \binom{3}{1}\binom{6}{3}\binom{2}{1}\binom{3}{2} + \binom{6}{2}\binom{4}{2}\binom{2}{2}\right]$$

$\endgroup$
2
  • $\begingroup$ Shouldn't it be $-\binom{3}{2}1^6$ in first answer? $\endgroup$ Nov 11, 2022 at 13:27
  • 1
    $\begingroup$ Somehow you convinced me that I had made a mistake when I had not. The original version was correct, as you can see by comparing the values of the two answers. When we subtract cases in which one of the elements is excluded, we subtract each case in which two of the elements are missing twice, once for each way we could have designated one of the missing elements as the missing element. We only want to subtract such cases once, which is why we need to add the cases in which only one element is in the image to the total. $\endgroup$ Nov 11, 2022 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .