How many functions are there from set $S$ to set $T$ such that subset of $T$ is in range?

140 Views Asked by At

Given a set $S$ of length $n$ and set $T=\{2,7,4,5\}$ how many functions $f:S\to T$ are there such that $\{7,4,5\}\subseteq \operatorname{Range}(f)$?

I thought inclusion/exclusion principle can be used here.

There're a total of $4^n$ functions from $S$ to $T$. There're $2^n$ functions such that one element from $\{7,4,5\}$ is not in $\operatorname{Range}(f)$. There're $1^n$ functions such that two elements are not in $\operatorname{Range}(f)$. Therefore the answer is: $$ 4^n-{3\choose 1}2^n+{3\choose 2}1^n $$

I'm not sure if I'm counting correctly, specifically whether is it should be $4^n$ in the beginning or $3^n$ because maybe we need to focus only on the $\{7,4,5\}$ subset.

2

There are 2 best solutions below

0
On BEST ANSWER

You are correct that there are $4^n$ functions $f: S \to T$ since there are four elements in the codomain to which each of the $n$ elements in the domain could be mapped.

From these, we wish to subtract those functions that do not include all the elements of the subset $U = \{4, 5, 7\}$ in the range.

There are $\binom{3}{1}$ ways to exclude one of the elements of set $U$ from the range. For each such choice, there are $3$ elements of set $T$ that could still be in the range. Since the $n$ elements in the domain could be mapped to one of these $3$ other elements in the codomain, there are $$\binom{3}{1}3^n$$ ways to exclude one of the elements in set $U$ from the range.

By similar reasoning, there are $$\binom{3}{2}2^n$$ ways to exclude two elements of $U$ from the range and $$\binom{3}{3}1^n$$ ways to exclude all three elements of $U$ from the range.

By the Inclusion-Exclusion Principle, the number of functions $f:S \to T$ that include all of set $U$ in the range is $$4^n - \binom{3}{1}3^n + \binom{3}{2}2^n - \binom{3}{3}1^n$$

0
On

Let $F_i$ stand for the set of functions $f:S\to N$ with $i\notin\mathsf{Range}(f)$

Then with inclusion/exclusion and symmetry we find: $$|F_7\cup F_4\cup F_5|=3|F_7|-3|F_7\cap F_4|+|F_7\cap F_4\cap F_5|=3\cdot3^n-3\cdot2^n+1$$so that $$|F_7^{\complement}\cap F_4^{\complement}\cap F_5^{\complement}|=4^n-[3\cdot3^n-3\cdot2^n+1]=4^n-3\cdot3^n+3\cdot2^n-1$$