# Combinatorics of functions

I tried to solve some truth/false questions i found in old books regarding combinatorics of functions, but i'm not fully grasping this concept. can you please check and correct me if i did a mistake to help me understand better?

1)a={1,2,3,4,5,6}. the number of injective functions from a->a that are copying even numbers(not odd) to even numbers is equal to the number of functions from {1,2} -> a ({1,2} to a).

2)the number of injective functions from a={1,2,3,4,5} to itself that are copying 1 to a different number than 1 is $5!-4!$

3)the number of injective functions from a={1,2,3,4,5} to itself that copy 1 to a different number than 1 and 2 to a different number than 2 is $5!-2*4!$

4)the number of functions from A={1,2,3,4} on b={1,2,3} is $3^4-3*2^4$

5)the number of subsets of a={1,2,3,4,5,6} that consist of at least 3 elements is equal to the number of the subsets of at most 3 variables.

what i did:

1)false. since an injective function is such that for every element of the function's codomain is the image of at most one element of its domain, and since the only even elements of a is the subset {2,4,6}, then it consist of more possiblities than the number of functions from {1,2} to a ({1,2}->a). so it's false.

2)correct. by the above given definition of injectivity, it seems to be correct that in order to arrange the given function in the given conditions, one should substract the non-needed combinations, i.e: $5!-4!$

3)false. the mathmatical expression doesn't seem to make sense.

4)correct. if i understand it correctly, in order for a to be over b, we must make sure that b is fully covered. so the number of functions should consist only of options that fully cover b (excluding uneeded combinations of 4). so $3^4-3*2^4$ seems to be the correct number.

5)false. since if we divide a={1,2,3,4,5,6} to 2 different sets, under the given conditions, we get that for a to consist of at least 3 elements, these are the given subsets: {1,2,3,4,5,6},{1,2,3,4,5}, {1,2,3,4}, {1,2,3}. and if we divide a so that the number of elements is at most 3, we get the following subsets={1},{1,2},{1,2,3}. and it seems to be obvious that the first condition(at least 3 elements) has more possible combinations than the second(at most 3 elements).

please correct me and explain if i did mistakes so i can learn from my mistakes.

thank you very much!

• For $1)$, Can you explain how you count each class of functions? What two numbers do you get? – lulu Sep 2 '17 at 17:40
• For 3) although it is false, the expression does make sense where it came from. The correct amount being $5!-2\cdot 4!+3!$. In any case, this is a rather lengthy question. A great deal of it comes down to understanding of multiplication principle and inclusion-exclusion. The short answers are F (should be $3!\cdot 3!$), T, F (should be $5!-2\cdot 4!+3!$), F (should be $3^4-3\cdot 2^4+3\cdot 1^4-1\cdot 0^4$), T. – JMoravitz Sep 2 '17 at 18:08
• For 5) you seem to be forgetting about the existence of the empty-set. Indeed $\binom{6}{3}+\binom{6}{4}+\binom{6}{5}+\binom{6}{6}=\binom{6}{3}+\binom{6}{2}+\binom{6}{1}+\binom{6}{0}$ remembering that $\binom{n}{r}=\binom{n}{n-r}$ and that $\binom{n}{r}$ is the number of $r$-element subsets of an $n$ element set. – JMoravitz Sep 2 '17 at 18:09
• In the first three questions, the word copying should be replaced by the word mapping. – N. F. Taussig Sep 2 '17 at 21:45
• @N.F.Taussig f maps even numbers to even numbers. JMoravitz thank you very much, i forgot about the existenc of the empty set. so they're equal. i didn't think of it at all. for 3-4: it means that 3 is false, and from above 2 is incorrect as well? lulu: the number of the injective functions from a to a that copy even numbers to even numbers should eventually include the subset {2,4,6}, and it is not equal to the number of functions from {1,2}->a(there are more options here). if you seem to see something else that i'm missing, please tell me how you count so i'll be able to learn. – BeginningMath Sep 2 '17 at 21:55

The number of injective functions $f: \{1, 2, 3, 4, 5, 6\} \to \{1, 2, 3, 4, 5, 6\}$ that map even numbers to even numbers is equal to the number of functions $g:\{1, 2\} \to \{1, 2, 3, 4, 5, 6\}$.

Let $A = \{1, 2, 3, 4, 5, 6\}$; let $B = \{1, 2\}$.

If $f: A \to A$ is an injective function that maps even numbers to even numbers, it must also map odd numbers to odd numbers. Such a function permutes the even numbers and permutes the odd numbers. Since there are $3!$ ways to permute the even numbers and $3!$ ways to permute the odd numbers, there are $3!^2 = 36$ such functions.

A function $g:B \to A$ is defined by how $g(1)$ and $g(2)$ are assigned. Since there are six ways to assign $g(1)$ and six ways to assign $g(2)$, there are $6 \cdot 6 = 36$ such functions.

Hence, the number of injective functions $f: A \to A$ that map even numbers to even numbers is equal to the number of functions $g: B \to A$.

The number of injective functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5\}$ that map $1$ to a number different from itself is $5! - 4!$.

This statement is true, and your reasoning is correct.

The number of injective functions $f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5\}$ that map $1$ to a number different from itself and that map $2$ to a number different from itself is $5! - 2 \cdot 4!$.

Let $A = \{1, 2, 3, 4, 5\}$.

This statement is false.

There are $4!$ injective functions $f: A \to A$ that map $1$ to itself and $4!$ injective functions $f: A \to A$ that map $2$ to itself. However, we have counted injective functions that map $1$ to itself and $2$ to itself twice. There are $3!$ such functions. Hence, the number of injective functions $f: A \to A$ that map $1$ to itself or $2$ to itself is $$2 \cdot 4! - 3!$$ Hence, the number of injective functions $f: A \to A$ that map $1$ to a number different from itself and $2$ to a number different from itself is $$5! - 2 \cdot 4! + 3!$$ as @JMoravitz indicated in the comments.

The number of surjective (onto) functions $f:\{1, 2, 3, 4\} \to \{1, 2, 3\}$ is $3^4 - 3 \cdot 2^4$.

Let $A = \{1, 2, 3, 4\}$; let $B = \{1, 2, 3\}$

The statement is false.

Method 1: If the function is surjective, then exactly one element of $B$ is the image of two elements of $A$, while the other elements of $B$ are each the image of exactly one element of $A$. There are $\binom{3}{1}$ ways to choose which element of $B$ is the image of two elements of $A$, $\binom{4}{2}$ ways to choose which two elements of $A$ map to that element of $B$, two ways of assigning the smaller of the remaining elements of $A$ to one of the two remaining elements in $B$, and one way to assign the remaining element of $A$ to the remaining element of $B$. Hence, there are $$\binom{3}{1}\binom{4}{2}2!$$ surjective functions.

Method 2: We use the Inclusion-Exclusion Principle.

There are three possible images for each of the four elements in $A$, so there are $3^4$ functions $f: A \to B$. From these, we must exclude those functions that map to fewer than three elements in the codomain.

There are $\binom{3}{1}$ ways to exclude one of the elements in the codomain from the range and $2^4$ ways to assign the four elements in the domain to one of the other two elements in the codomain.

However, if we subtract $\binom{3}{1}2^4$ from the total, we will have subtracted the three constant functions twice, once for each of the ways we could have designated one of the other elements as the excluded element.

There are $\binom{3}{2}$ ways to exclude two of the elements in the codomain from the range and one way to assign each of the four elements in the domain to the remaining element in the codomain.

Hence, the number of surjective functions $f: A \to B$ is $$3^4 - \binom{3}{1}2^4 + \binom{3}{2}1^4$$ as @JMoravitz indicated in the comments.

The number of subsets of $A = \{1, 2, 3, 4, 5, 6\}$ that contain at least three elements is equal to the number of subsets of $A$ that contain at most three elements.

This is true.

Method 1: Since $A$ has six elements, we can construct a bijection from the set of subsets of $A$ with at least three elements to the set of subsets of $A$ with at most three elements by mapping each subset of $A$ with at least three elements to its complement.

Method 2: Since $|A| = 6$, there are $\binom{6}{k}$ subsets of $A$ with exactly $k$ elements. Since $\binom{6}{k} = \binom{6}{6 - k}$, $$\binom{6}{3} + \binom{6}{4} + \binom{6}{5} + \binom{6}{6} = \binom{6}{3} + \binom{6}{2} + \binom{6}{1} + \binom{6}{0}$$ where the left-hand side counts subsets with at least three elements and the right-hand side counts subsets with at most three elements. Once again, @JMoravitz stated this in the comments.

• thank you so much. it's almost 3 am now, i'll study your reply very well to learn from it. thank you wholeheartedly for being so elaborative! – BeginningMath Sep 2 '17 at 23:52
• Please get some sleep. – N. F. Taussig Sep 2 '17 at 23:53