Find the number of functions (union of sets to a set) I'm dealing with the following problem. I have two finite sets $A$ and $B$, with $|A| = m$ and $|B| = n$. I should determine how many functions
$f : \mathit A \cup \mathit B \to \{0, 1, 2\}$
there are, such that $f(a) \neq f(b)$ for all $a \in A$ and $b \in B$.
The answer for a function
$f : X \to Y$, with $|X| = m$ and $|Y| = n$
would be $n^m$. I've tried to use the same idea to solve my problem, but I'm stuck at some point, since
$|A \cup B|$ = $|A| + |B| - |A \cap B|$ and $|A \cap B|$ = $|A| + |B| - |A \cup B|$, which makes a loop...
Do you have any hints to solve this?
 A: As mentioned elsewhere, $f(a)\ne f(b)$ when $a\in A$ and $b\in B$, indicates that $A\cap B=\emptyset$. That is, if $x\in A\cap B$, then $f(x)\ne f(x)$, which is a contradiction.
Inclusion-Exclusion is mentioned in the question, and we use it here, but we will use it to count the number of surjections from one set to another.
Counting Surjections
First, we will compute the number of surjections from the set $A$, of size $m$, onto the set $R$, of size $k$.
Let $S(i)$ be the set of functions on $A$ that do not map onto element $i$ of $R$. An intersection of $j$ of the $S(i)$ contains all functions on $A$ that do not contain $j$ particular elements of $R$ in their range. Since there are $\binom{k}{j}$ choices of the of $j$ missing elements, and for each such intersection, there are $(k-j)^m$ functions that don't map to any of the excluded $j$ elements, we have
$$\newcommand{\stirtwo}[2]{\left\{#1\atop#2\right\}}
\begin{align}
N(j)
&=\sum_{|\mathcal{I}|=j}\left|\,\bigcap_{i\in\mathcal{I}} S(i)\,\right|\tag{1a}\\
&=\binom{k}{j}(k-j)^m\tag{1b}
\end{align}
$$
Acording to the Generalized Inclusion-Exclusion Principle, the number of elements in none of the $S(i)$ is
$$
\begin{align}
\sum_{j\ge0}(-1)^j\binom{j}{0}N(j)
&=\sum_{j=0}^k(-1)^j\binom{k}{j}(k-j)^m\tag{2a}\\
&=\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^m\tag{2b}\\[3pt]
&=\stirtwo{m}{k}k!\tag{2c}
\end{align}
$$
Explanation:
$\text{(2a)}$: apply the Generalized Inclusion-Exclusion Principle to $(1)$
$\text{(2b)}$: substitute $j\mapsto k-j$
$\text{(2c)}$: $\stirtwo{m}{k}$ is a Stirling Number of the Second Kind
That is, $(2)$ gives the number of surjections from a set of size $m$ onto a set of size $k$.
Answering the Question
Given $|A|=m$ and $|B|=n$, suppose $|f(A)|=j$, $|f(B)|=k$, and $j+k+p=3$. That is, $p$ is the number of elements not in $f(A\cup B)$.
The number of ways to choose the missing values is $\binom{3}{p}$.
For each choice of missing values, the number of ways to assign values to $f(A)$ and $f(B)$ is $\binom{3-p}{k}$.
For each assignment of values, $(2)$ says that the number of functions is $\stirtwo{m}{k}k!\stirtwo{n}{3-p-k}(3-p-k)!$.
Therefore, the number of functions $f:A\cup B\to\{0,1,2\}$ so that $a\in A$ and $b\in B$ implies that $f(a)\ne f(b)$, is
$$
\begin{align}
&\sum_{p=0}^3\sum_{k=0}^{3-p}\binom{3}{p}\binom{3-p}{k}\color{#C00}{\stirtwo{m}{k}k!}\color{#090}{\stirtwo{n}{3-p-k}(3-p-k)!}\tag{3a}\\
&=\sum_{p=0}^3\sum_{k=0}^{3-p}\binom{3}{p}\binom{3-p}{k}\color{#C00}{\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}i^m}
\color{#090}{\sum_{j=0}^{3-p-k}(-1)^{3-p-k-j}\binom{3-p-k}{j}j^n}\tag{3b}\\
&=\sum_{p=0}^3\sum_{k=0}^{3-p}(-1)^{3-p}\binom{3}{p}\binom{3-p}{k}\sum_{i=0}^k(-1)^i\binom{k}{i}i^m
\sum_{j=0}^{3-p-k}(-1)^j\binom{3-p-k}{j}j^n\tag{3c}\\
&=\sum_{p=0}^3\sum_{k=0}^{3-p}(-1)^{3-p}\frac{3!}{p!}\sum_{i=0}^k(-1)^i\frac1{i!(k-i)!}i^m
\sum_{j=0}^{3-p-k}(-1)^j\frac1{j!(3-p-k-j)!}j^n\tag{3d}\\
&=\sum_{i=0}^3\sum_{j=0}^{3-i}\sum_{p=0}^{3-i-j}(-1)^{3-p-i-j}\frac{3!\,i^mj^n}{p!(3-p-i-j)!i!j!}2^{3-p-i-j}\tag{3e}\\
&=\sum_{i=0}^3\sum_{j=0}^{3-i}(-1)^{3-i-j}\frac{3!\,i^mj^n}{(3-i-j)!i!j!}\tag{3f}\\
&=\bbox[5px,border:2px solid #C0A000]{\left\{
\begin{array}{l}
3(2^m+2^n-2)&\text{when }m,n\gt0\\
3^{m+n}&\text{when $m=0$ or $n=0$}\\
\end{array}
\right.}\tag{3g}\\
\end{align}
$$
Explanation:
$\text{(3a)}$: preceding argument
$\text{(3b)}$: apply $\text{(2b)}$
$\text{(3c)}$: redistribute powers of $-1$
$\text{(3d)}$: expand the binomial coefficients as ratios of factorials and cancel
$\text{(3e)}$: sum in $k$: $\sum\limits_{k=i}^{3-p-j}\frac1{(k-i)!(3-p-k-j)!}=\frac{2^{3-p-i-j}}{(3-p-i-j)!}$
$\text{(3f)}$: sum in $p$: $\sum\limits_{p=0}^{3-i-j}\frac{(-2)^{3-p-i-j}}{p!(3-p-i-j)!}=\frac{(-1)^{3-i-j}}{(3-i-j)!}$
$\text{(3g)}$: when $m,n\gt0$, the $i=0$ and $j=0$ terms vanish
$\phantom{\text{(3g):m}}$ $(i,j)=(2,1)$ gives $3\cdot2^m$
$\phantom{\text{(3g):m}}$ $(i,j)=(1,2)$ gives $3\cdot2^n$
$\phantom{\text{(3g):m}}$ $(i,j)=(1,1)$ gives $-6$
$\phantom{\text{(3g):}}$ when $m=0$, the sum in $i$ is $0^{3-j}\frac{6j^n}{j!}$; of which, the sum in $j$ is $3^n$
$\phantom{\text{(3g):}}$ when $n=0$, the sum in $j$ is $0^{3-i}\frac{6i^m}{i!}$; of which, the sum in $i$ is $3^m$
Generalization to Other Ranges
The argument and formulas above, except $\text{(3g)}$, can be generalized to ranges other than $\{0,1,2\}$ simply by replacing $3$ with the size of the other range.
A: Just a small hint, for that property to be true, apart from the sets having to be disjoint as Bernard said in the comments, observe that f must take A and B to two disjoint subsets of {0,1,2}.
A: Based on the given constraints in the question, we have

*

*$f(A) \not = \{\}$

*$f(B) \not = \{\}$

*$f(A)\cap f(B) =\{\}$

*$f(A)\cup f(B) \subseteq \{0,1,2\}$
As all the possible cases are relatively small, let me enumerate as follows.
My notation $|f_A|$ represents the number of possible functions that map from $A$ to $f(A)$.




Case
$f(A)$
$f(B)$
$|f_A|$
$|f_B|$
$|f_{A\cup B}|$




1
$\{0\}$
$\{1,2\}$
$1$
$2^n$
$1\times2^n$


2
$\{1\}$
$\{0,2\}$
$1$
$2^n$
$1\times2^n$


3
$\{2\}$
$\{0,1\}$
$1$
$2^n$
$1\times2^n$


4
$\{0,1\}$
$\{2\}$
$2^m$
$1$
$2^m\times 1$


5
$\{0,2\}$
$\{1\}$
$2^m$
$1$
$2^m\times 1$


6
$\{1,2\}$
$\{0\}$
$2^m$
$1$
$2^m\times 1$


7
$\{0\}$
$\{1\}$
$1$
$1$
$1\times 1$


8
$\{0\}$
$\{2\}$
$1$
$1$
$1\times 1$


9
$\{1\}$
$\{0\}$
$1$
$1$
$1\times 1$


10
$\{1\}$
$\{2\}$
$1$
$1$
$1\times 1$


11
$\{2\}$
$\{0\}$
$1$
$1$
$1\times 1$


12
$\{2\}$
$\{1\}$
$1$
$1$
$1\times 1$




However,

*

*Case 7 is already in either  case 1 or case 5.

*Case 8 is already in either  case 1 or case 4.

*Case 9 is already in either  case 2 or case 6.

*Case 10 is already in either  case 2 or case 4.

*Case 11 is already in either  case 3 or case 6.

*Case 12 is already in either  case 3 or case 5.

Thus the total is
\begin{align}
T
&= 3(1\times 2^n) + 3(2^m\times1) - 6\\
&= 3(2^n+2^m-2)
\end{align}
