Forming Certain Functions

Relevant wiki: Principle of Inclusion and Exclusion Problem Solving

Each possible function may be viewed as a 10-tuple of values between 1 and 10. So we count all 10-tuples of this kind where the numbers are not all a multiple of a value greater than 1.

Start with all possible 10-tuples: $10^{10}$

Subtract the following :

• all multiples of two: $5^{10}$ (anything with 2, 4, 6, 8, 10)

• all multiples of three: $3^{10}$ (anything with 3, 6, 9)

• all multiples of five: $2^{10}$ (anything 5, 10)

• all multiples of seven: $1^{10}$ (anything 7)

Now we have subtracted out some tuples twice, so we add them back in once. Add the following :

• all multiples of six: $1^{10}$

• all multiples of ten: $1^{10}$

Thus the number of possibilities is $10^{10} - 5^{10} - 3^{10} - 2^{10} - 1^{10} + 1^{10} + 1^{10} = 9\:990\:174\:303$

Let $\mathcal{F}$ be the set of all functions $f: \{1, 2, 3, \cdots, 10\}\rightarrow \{1, 2, 3, \cdots, 10\}.$ The number of elements in $\mathcal{F},$ by the Rule of Product , is $10^{10}.$ Let us define $\mathcal{A}$ as the set of functions $f$ in $\mathcal{F}$ for which the greatest common factor of the numbers in $range(f)$ is 1. For any natural number $n,$ we can define $\mathcal{B}_n$ as the set of all functions $f$ in $\mathcal{F}$ such that all the numbers in $range(f)$ are divisible by $n.$ It is clear that if $n> 10,$ then $\mathcal{B}_n=\emptyset.$ In what follows, we are going to denote the cardinality of an arbitrary set $C$ by $|C|.$ Then using the Rule of Product, it is not difficult to get the following: $|\mathcal{B}_2|=5^{10}, |\mathcal{B}_3|=3^{10}, |\mathcal{B}_5|=2^{10}, |\mathcal{B}_6|=|\mathcal{B}_7|=|\mathcal{B}_{10}|=1\:\:\:\:\:\:(1)$ Additionally, it can be proved that if $m$ and $n$ are two prime numbers less than 10 then $\mathcal{B}_n\cap\mathcal{B}_m=\mathcal{B}_{m\times n}.\:\:\:\:\:\:\:(2)$ A similar property applies for more than two primes. For example, $\mathcal{B}_2\cap\mathcal{B}_3\cap\mathcal{B}_5=\mathcal{B}_{30}=\emptyset.$

It is easy to see that $\mathcal{A}=\mathcal{F}\setminus(\mathcal{B}_2\cup\mathcal{B}_3\cup\mathcal{B}_5\cup\mathcal{B}_7).$ Then we get the following:
$|\mathcal{A}|=|\mathcal{F}|-|\mathcal{B}_2\cup\mathcal{B}_3\cup\mathcal{B}_5\cup\mathcal{B}_7|=10^{10}-|\mathcal{B}_2\cup\mathcal{B}_3\cup\mathcal{B}_5\cup\mathcal{B}_7|.\:\:\:\:\: (3)$ Now using the Principle of Inclusion-Exclusion we obtain that $|\mathcal{B}_2\cup\mathcal{B}_3\cup\mathcal{B}_5\cup\mathcal{B}_7|=|\mathcal{B}_2|+|\mathcal{B}_3|+|\mathcal{B}_5|+|\mathcal{B}_7| - |\mathcal{B}_2\cap\mathcal{B}_3|- |\mathcal{B}_2\cap\mathcal{B}_5|- |\mathcal{B}_2\cap\mathcal{B}_7|-$ $- |\mathcal{B}_3\cap\mathcal{B}_5|- |\mathcal{B}_3\cap\mathcal{B}_7|- |\mathcal{B}_5\cap\mathcal{B}_7|+ |\mathcal{B}_2\cap\mathcal{B}_3\cap\mathcal{B}_5|+ |\mathcal{B}_2\cap\mathcal{B}_3\cap\mathcal{B}_7|+ |\mathcal{B}_2\cap\mathcal{B}_5\cap\mathcal{B}_7|+$ $|\mathcal{B}_3\cap\mathcal{B}_5\cap\mathcal{B}_7|-|\mathcal{B}_2\cap\mathcal{B}_3\cap\mathcal{B}_5\cap\mathcal{B}_7|$ Then using (1) and (2) and the fact that the last 9 terms in the right side of the previous equation are zero, we get that $|\mathcal{B}_2\cup\mathcal{B}_3\cup\mathcal{B}_5\cup\mathcal{B}_7|=5^{10}+3^{10}+2^{10}+1 - 1-1=9825697$ Using (3), $|\mathcal{A}|= 10^{10}-9825697=9990174303.$