Counting surjective functions

We are interested in permutations (a surjective function from the finite set $I_7$ to itself must be bijective, so a permutation) in $S_7$ whose squares fix no points. This only happens for permutations which (a) fix no points themselves, (b) contain no $2$ -cycles in their cycle decomposition. Considering the possible cycle decompositions of elements of $S_7$ , there are only two possibilities:

• $7$ -cycles, of which there are $6! = 720$ ,

• $(3\times4)$ -cycles, of which there are ${}^7C_4 \times 3! \times 2 = 420$ .

Thus $N=1140$ .

Since there are $7$ elements in $I_7$ which make up both the given domain and range of the function, then each value $f(1)$ through $f(7)$ must correspond to a unique value $1$ through $7$ . That is, the function is $1$ to $1$ . In addition, since $f(f(a)) \neq a$ , then necessarily $f(a) \neq a$ . And, $f(a) \neq b$ if $f(b) = a$ .

We now look for the number of functions that satisfy these conditions. We can't have $f(a) = a$ nor $f(a) = b$ AND $f(b) = a$ , thus the equivalences must be made in a group of $3$ and $4$ or in a group of $7$ as groups of $(5, 2)$ or $(1, 6)$ would respectively result in $f(a) = b, f(b) = a$ or $f(a) = a$ .

There are ${7 \choose 3}$ ways to choose the way the integers are grouped together in the first case. For the group of $3$ we can have 2 distinct configurations, namely $f(a) = b, f(b) = c, f(c) = a$ or $f(a) = c, f(c) = b, f(b) = a$ . For the group of $4$ we have $3! = 6$ different configurations and, more generally, for a group of $n$ there are $(n - 1)!$ configurations*. Thus, there are $(35)(2)(6)$ functions in this case.

*If you were to place a point on a plane for every element of the set, then we want to find the number of ways to create a path that visits each point and then returns to the original point. Since the path is cyclic we can start with any vertex we choose. Then there are $n - 1$ vertices we could go to next, then $n - 2$ vertices and so on, resulting in $(n - 1)!$ paths.

Using this information, for the second case there must then be $6! = 720$ distinct functions. Thus, the total number of functions is $1140 \equiv 140 \pmod{1000}$ .

Obviously, $f$ has to be a permutation on $I_7$ .

Each permutation can be uniquely decomposed into disjoint cycles. The condition $\forall a: f(f(a))\not=a$ tells us that $f$ has no fixed points (i.e., cycles of length 1) and no cycles of length 2. Thus there are only two possible cases how the decomposition looks like: a) a single cycle of length 7, b) two cycles of lengths 3+4.

There are $(n-1)!$ different cyclic permutations of $n$ elements. Why? Imagine walking along the cycle, starting at the smallest element. Each of the $(n-1)!$ different orders in which we encounter the remaining $n-1$ elements defines a different cyclic permutation.

Thus, there are $6!=720$ different permutations of 7 elements that consist of a single cycle.

For the second case, we have ${7\choose 3}=35$ ways how to choose the 3 elements that form the shorter cycle, $2!=2$ ways how to form the shorter cycle using those elements, and $3!=6$ ways how to form the longer cycle using the remaining 4 elements. This gives us a total of $35\cdot 2\cdot 6 = 420$ such permutations.

Hence, $N = 720 + 420 = 1140$ , and the answer is $\fbox{140}$ .

We can think of such a surjective function in the following way. Draw $7$ points labeled $1,2,...,7$ and connect the points using arrows such that a point is directed to its image in $f$ .

A diagram like this can have cycles, for example when $1 \rightarrow 2 \rightarrow 4 \rightarrow 1$ we have a cycle of length 3. A function satisfies the condition of the question if and only if there is no cycle of length 2, and no point is directed towards itself.

As an important lemma, we claim that the number of directed cycles of length $n$ through $n$ given points is $(n-1)!$ . Indeed, for the first point, we can direct it to $n-1$ points. After we choose a destination for the first arrow, this point can be directed to $n-2$ other points (it cannot be directed to itself or the first point). We continuing in this manner until we reach the second last point, which only has one choice, and the last point will be directed back to the first point. Therefore the total number of such cycles is $(n-1)(n-2)...2.1.1=(n-1)!$

With $7$ points, we have two cases. In the first case, there is one cycle of length 7 through all the points and in the second case, there are 2 cycles of lengths 3 and 4.

The number of possible diagrams for the first case is $6!=720$ . To count the number of diagrams for the second case, we use the multiplication principle. First, we choose 4 points to go in the cycle of length 4, and there are $\binom{7}{4}$ ways. Given a group of 4 points and a group of 3 points, there are $3!$ cycles through all the 4 points and $2!$ cycles through all the 3 points. Thus the total number of diagrams for the second case is $\binom{7}{4} (3!)(2!) = 420$

Hence $N=720+420=1140$ . The last three digits of $N$ are $\fbox{140}$

First we note that every surjective function between two sets with the same number of elements is a bijection. Therefore we can see the function $f$ as a permutation of $7$ elements.

We know that every permutation can be written as product of disjoint cycles. Now in order to have that $f(f(a))\neq a$ we must have that none of the cycles in the permutation are $1$ -cycles or $2$ -cycles.

We have two possible configurations:

• One $7$ -cycle, and the number of cases is: $\frac{7!}{7}=6!$
• One $3$ -cycle and one $4$ -cycle, and the number of cases is: $\frac{7!}{3 \cdot 4}$

Adding these up we get a total of $1140$ . So the answer is $\fbox{140}$

As $f$ is surjective, $I_7 \subseteq \{f(1),f(2)...,f(7)\}$ but since both sets have the same number of elements, they must have exactly the same elements. Hence, $f$ is bijective.

Consider a graph with $7$ vertices labelled $1,2,...7$ and we draw an arrow from $a$ to $b$ if $f(a)=b$ . Since $f$ is bijective, every vertex has exactly one arrow pointing to and one pointing away from the vertex. If we start from any vertex and traverse the path by following the arrows, we cannot visit any other vertex twice since each vertex only has one arrow pointing into the vertex. However, every vertex has an arrow pointing out so the path cannot end so it must be the case that the path forms a cycle. Since every vertex has exactly one arrow in and one arrow out, all the vertices must form disjoint cycles.

The condition given tells us that there cannot be any cycles of length $1$ or $2$ so the only $2$ possible cases are that there are $2$ cycles of length $3$ and $4$ respectively or one cycle of length $7$ .

For the first case, we need to choose which numbers to be in which cycle and given $n$ vertices there are $(n-1)!$ ways to form one cycle using every vertex once since we can choose any vertex first and permute the other $n-1$ vertices to form a cycle in that order.

Using the above, the number of functions $f$ is $\binom{7}{3}(4-1)!(3-1)!+(7-1)! = \boxed{1140}$

Use cycle-notation for the functions $f$ , for example $(123)(4)(567)$ means that $f(1)=2$ , $f(2)=3$ , $f(3)=1$ , $f(4)=4$ , $f(5)=6$ , $f(6)=7$ and $f(7)=5$ .

$f(f(a)) ≠ a$ implies there can be no cycles of length 1 or 2 in $f$ .

That leaves us with 2 possibilities:

1) $f$ consists of a cycle of length 3 and a cycle of length 4.

There are 35 ways to choose 3 numbers from a set of 7. There are 2 possible cycles of three given numbers. There are 6 possible cycles of 4 given numbers. This means there are $35 \times 2 \times 6 = 420$ functions $f$ consisting of a cycle of length 3 and a cycle of length 4.

2) $f$ consists of a single cycle of length 7.

There are $6! = 720$ possible cycles of length 7.

That leaves us with $420 + 720 = 1140$ surjections.

We define a "contained subset" to be a subset of $I_7$ such that it satisfies the following conditions: 1. If we let the elements be $a_1, a_2, ..., a_n$ , and $f(a_1)=b_1, f(a_2)=b_2, ..., f(a_n)=b_n$ , ${b_1, b_2, ..., b_n}$ is a permutation of ${a_1, a_2, ..., a_n}$ . 2. There is no proper subset of $I_7$ that satisfies condition 1. 3. There are at least $3$ elements in that subset.

It is clear that all contained subsets are disjoint.

We call a function that satisfies the condition of the problem a valid function.

For each function we partition the elements into contained subsets. It is clear that there is only 1 such partition for each function. It is also clear that each valid function is partitioned into at most 2 contained subsets.

Suppose that the function is partitioned into 2 contained subsets. It is forced that the cardinality of the contained subsets are 3 and 4.

On the other hand, if the function is partitioned into 1 contained subset, then that contained subset has cardinality of 7.

Lemma: There are $(n-1)!$ surjective functions from the set of the subset's elements to itself for each contained subset with $n$ elements.

We fist select one of the elements of the subset. There are $n-1$ ways to choose the output of the function for that element, call it $a_1$ . Now we consider the output of that element, $a_2$ . There are $n-2$ ways to choose the output of that $a_2$ , $a_3$ , because we cannot choose itself or $a_1$ . There are $n-3$ ways to choose the output of $a_3$ , because we cannot choose itself, $a_1$ , or $a_2$ . We could continue this reasoning to conclude that there are $2$ ways to choose for the $n-2$ element and $1$ way to choose for the $n-1$ th element. Since we multiply the number of possibilities, there are $(n-1)!$ functions.

Case 1: The function is partitoned into 2 contained subsets of cardinality 3 and 4.

There are $7C_3=35$ ways to choose which 3 elements would go to the subset of cardinality 3. Likewise, there are $(3-1)!=2$ ways to choose the functions for the cardinality 3 subset and $(4-1)!=6$ ways to choose the functions for the cardinality 4 subset. Hence there are $(2)(6)(35)=420$ functions for this case.

Case 2: The function is partitioned into 1 contained subset of cardinality 7.

There are $(7-1)!=720$ functions for this case.

Hence there are $720+420=1140$ functions in all. The last 3 digits are $\boxed{140}$

A way of describing such functions is using cycles. For example the function (1 2 3 4 5 6 7) means that f(1) = 2, f(2) = 3, ... , f(7) = 1, or function (1 2 3 4) (5 6 7) means that f(1) = 2, ..., f(4) = 1, f(5) = 6, f(6) = 7, f(7) = 5. It is clear that the functions we search must not contain cycles of length 1 or 2 because in cycles (a) and (a b) it occurs that f(f(a)) = a. Therefore, we are left with functions made of just one cycle of length 7 or two cycles of lengths 3 and 4. There are 6! = 720 different cycles of length 7 (we choose the first element and permutate the rest, because cycles (1 2 3 4 5 6 7) and (2 3 4 5 6 7 1) are equivalent). There are 35 * 3! * 2! = 420 different functions made of two cycles of lengths 3 and 4 (35 are the ways of choosing 3 numbers out of the 7 which will compose the cycle of length 3). So there are 1140 functions satisfying the conditions.

We see that $f(f(a))$ not equal to $a$ also implies $f(a)$ does not equal $a$ . Thus this is equivalent to counting the number of permutations that contain no 2 or 1 cycles. Thus our cycles look like (a b c)(d e f g) or (a b c d e f g). The former we we have (7 choose 3)(3 - 1)!(4-1)! = 420 different permutations. The later we have (7-1)! = 720 different permutations. For a total of 1160.