Number of functions such that f(i) not equal to i

Tags:
1. Feb 22, 2016

Titan97

1. The problem statement, all variables and given/known data

$A=\{1,2,3,4,5\}$, $B=\{0,1,2,3,4,5\}$. Find the number of one-one functions $f:A\rightarrow B$ such that $f(i)\neq i$ and $f(1)\neq 0\text{ or } 1$.

2. Relevant equations
Number of derangements of n things = $$n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}\right)$$

3. The attempt at a solution

If either of $0$ and $1$ are not included in the range of $f$, then total possibilities = $2\times 44=88$

If both $0,1$ are included in the range of $f$, then one number from $\{2,3,4,5\}$ has to be mapped to $1$. Number of possibilities is $\binom{4}{1}$. Let me map $1$ to $5$.
For the remaining $5$ numbers, one number other than $0,1$ has to be excluded (since $0,1$ are in the range of $f$) Number of such possibilities is $\binom{3}{1}$. Let the number removed be $4$.

The remaining numbers $\{0,1,2,3\}$ has to be mapped to $\{2,3,4,5\}$. How can I use principle of inclusion and exclusion here?

2. Feb 22, 2016

Staff: Mentor

You can consider "mappings where both 2 and 3 are mapped to 2 and 3" and "mappings where either 2->2 or 3->3 but not both", and "all mappings". Not sure if that is faster than the approach "2 can be mapped to 3, or to 0 or 1, then ...".

3. Feb 22, 2016

geoffrey159

Use contraposition : Let $f: A\to B$

Not$( \forall i=1...5,\ f(i) \neq i \text{ and } f(1) \notin \{0,1\} ) \iff (\exists i = 1...5, f(i) = i \text{ or } f(1)\in \{0,1\} )$

With that kind of reasoning, if $N$ is the total number of function from A to B, and $M$ the number you are are looking for, you should get a formula that looks like

$M = N - \# ((\cup_{i=1}^n A_i) \cup A)$

Hopefully the principle of inclusion exclusion will give you something interesting

4. Feb 22, 2016

geoffrey159

At second thought I think my previous post was unclear.
What I meant is that if $S$ is the set of one to one maps from $A$ to $B$,
$U$ the subset of $S$ verifying your constraint, then $S$ is the disjoint union of $U$ and of its complement in $S$ (say $V$). Then you know that $|S| = |U| + |V|$.
Translate what it means for an element of $S$ to be in $V$.
Reduce into smaller unions, and apply the principle of inclusion exclusion.

5. Feb 24, 2016

haruspex

The formula you quote for derangements is a direct result of applying the principle of inclusion and exclusion, so try to use that rather than reinventing the wheel.
If a mapping does not use 0 in B, it is a derangement of 5 objects, so the formula counts those.
If a mapping does use the 0, you can extend the domain of the mapping in a unique way to make a derangement on B. Do you see how? That counts all those mappings, except that you have to discard some because 1 must not map to 0.

6. Feb 24, 2016

Titan97

I thought I could not use that formula if both 0,1 belong to the range of f because f(1) cannot take two values. (It works if either of 0,1 is excluded)

7. Feb 24, 2016

haruspex

As I posted, you just have to subtract out the derangements (of B) which mapped 1 to 0. How many things can 1 map to in a derangement of B? What fraction map it to 0?

8. Feb 24, 2016

haruspex

By the way, the really useful thing about the derangement formula is that you can pretend it is an infinite series and just round the result to the nearest integer. The error is less than 1/n.