Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following question:

I got two groups $X=\{1,2,3,4\}$ , $Y=\{1,2,3,4,5,6\}$

How many injective functions $f: X → Y$ consider next terms: for each $i \in X$ , $f(i) ≠ i$ . The solution has to be via inclusion - exclusion principle.

Can anyone suggest an approach or an answer?

Thanks!

share|improve this question
    
It isn't that simple, @tetori. Note the requirement that $f(i)\neq i$ for all $i\in X$. –  Cameron Buie Feb 3 '13 at 16:00

2 Answers 2

up vote 0 down vote accepted

You can use this approach. At first you count the total no. of injective functions. This according to me is $$6C4*4!$$ Then you can count the no. of ways in which 1 of the $F(i)=i$ this equals $$4C1\times5C3\times3!$$Then you can count the no. of ways in which 2 of the $F(i)=i$ this equals $$4C2\times4C2\times2!$$Then for 3 i such that $F(i)=i$ this equals $$4C3\times3C1\times1!$$And lastly the case when all $F(i)=i$ this equals $$1$$.So the no. of fns. are $$6C4*4!-4C1\times5C3\times3!+4C2\times4C2\times2!-4C3\times3C1\times1!+1$$ Using inclusion exclusion principle.

share|improve this answer

Hint: Lets enumerate the numbers. If $f$ is such that injection, then in how many ways we can define $f(1)\in Y$? It is $5$, cause we exclude $f(1)=1$. Do the same way for another number $2\in X$, so we have $4$ and s... so there are $5!$ injective functions with that property.

share|improve this answer
    
If $f(1)=2$, then 2 has 5 possibilities! –  Stefan Feb 3 '13 at 16:13
    
@Stefan: But we assume that $f$ is an injectice, so we should care about $x=2$, so it takes 4 positions. –  Babak S. Feb 3 '13 at 16:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.