6
$\begingroup$

Suppose $2$ sets with cardinality $X=5$ and $Y=7$.

How many one to one function from $X$ to $Y$ such that $k$th element of $X$ should not align with the $k$ th element of $Y$ ?


I think one to one possible are $6\times 5\times 4\times 3\times 2$, but not sure though.

$\endgroup$
  • 1
    $\begingroup$ I doubt your answer. The first element maps to one of six for sure, But the second element can also map to one of six when the first maps to the second. $\endgroup$ – Tom Collinge Jan 15 '17 at 11:13
  • $\begingroup$ How about inclusion-exclusion principle? $\endgroup$ – Amir Naseri Jan 15 '17 at 11:14
  • $\begingroup$ @TomCollinge You are right. I missed some possibilities . $\endgroup$ – Jon Garrick Jan 15 '17 at 11:14
  • 1
    $\begingroup$ Reminds me of the hat-check problem. $\endgroup$ – Jeppe Stig Nielsen Jan 15 '17 at 11:41
  • $\begingroup$ @JeppeStigNielsen Yes, indeed it's a derangement . $\endgroup$ – Jon Garrick Jan 15 '17 at 11:43
1
$\begingroup$

Total no. of one-to-one functions from $X$ to $Y$ = $^7P_5=2520$.

Now if any of the $k$th elements of $X$ and $Y$ align (call this property $A$) , we have the following cases:

  1. $X_1 \to Y_1$ and the rest unrestricted
  2. $X_2 \to Y_2$ and the rest unrestricted
  3. $X_3 \to Y_3$ and the rest unrestricted
  4. $X_4 \to Y_4$ and the rest unrestricted
  5. $X_5 \to Y_5$ and the rest unrestricted

Each of them create $^6P_4=360$ functions implying $1800$ functions in total.

But then there are repetitions as $(1)$ and $(2)$ contain parts of each other and so on for the others as well. Hence there are overcalculations.

So we deduct $\binom{5}{2}\times \,^5P_3= ?_1 $ functions.

But again we have overdeducted those where $3$ cases have their intersection.

So we add $\binom{5}{3}\times \,^4P_2= ?_2 $ functions.

Again, there is a overcalculation of those functions where $4$ cases have their intersection.

So we deduct $\binom{5}{4}\times \,^3P_1= ?_3 $ functions.

But again we have overdeducted those where $5$ cases have their intersection. And that is why we add $1$ function.

So the total no.of functions that satisfy the property $A$
= $1800-\binom{5}{2}\times \,^5P_3+\binom{5}{3}\times \,^4P_2-\binom{5}{4}\times \,^3P_1+1=?_4$

Hence your answer is $2520-?_5$.

Hope this helps.

$\endgroup$
  • $\begingroup$ Thankyou very much ! I got my error !! $\endgroup$ – Jon Garrick Jan 15 '17 at 11:24
  • 1
    $\begingroup$ You're welcome :) $\endgroup$ – SchrodingersCat Jan 15 '17 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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