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

[Titan97]

Homework Statement

$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$.

Homework Equations

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

The Attempt at a Solution

[/B]
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?

 

[mfb]

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 ...".

 

[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

 

[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.

 

[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.

 

[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)

 

[haruspex]

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 rather than just one value.

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?

 

[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.