2
$\begingroup$

If $P = \{1,2,3,4,5\}$ and $Q = \{0,1,2,3,4,5\}$. The number of one one function function from

$P$ to $Q$ such that $g(1)\neq 0$ and $g(i)\neq i$ for $i=1,2,3,4,5$ is?

My attempt: Since $g(1) \neq 0,1$, $g(1)$ can take any $4$ values as $2,3,4,5$, which can be done in $4$ ways. Now $g(2),g(3),g(4),g(5)$ can take the remaining $5$ values which can be done in $\displaystyle \binom{5}{4}\cdot 4!$ ways. As such, the number of one-one functions such that $g(1)\neq0,1$ equals:

$$\displaystyle 4\cdot \binom{5}{4}\cdot 4! = 480$$

How can I find the number of functions for which $g(i) \neq i$ for $i = 2, 3, 4, 5$?

$\endgroup$
1
  • $\begingroup$ Hint: use inclusion exclusion. $\endgroup$
    – Anurag A
    Jun 22, 2017 at 3:41

2 Answers 2

3
$\begingroup$

The so-called rencontres numbers $D_n$ count the number of fixed point free permutations (called derangements) of a set with $n$ elements. These numbers appear in the context of inclusion/exclusion, but it is easy to see that they verify the recursion $$D_1=0,\quad D_2=1,\qquad D_n=(n-1)(D_{n-1}+D_{n-2})\quad (n\geq3)\ .$$

I claim that the number $N$ of admissible $f:\>P\to Q$ is given by $$N=D_5+{4\over5}D_6=44+{4\over5}\cdot 265=256\ .$$ Proof. If $0\notin f(P)$ then $f$ is a derangement of $P$, hence is counted in $D_5$. If $0\in f(P)$ then extend $f$ to a map $\bar f:\>Q\to Q$ by letting $\bar f(0)$ be the value in $Q$ not taken by $f$. Then $\bar f$ is a derangement of $Q$, and is counted in $D_6$. But ${1\over5}$ of these derangements have $f(1)=0$, which is forbidden.$\qquad\square$

$\endgroup$
1
$\begingroup$

You can use the inclusion-exclusion principle to solve this question. First consider all $6! = 720$ permutations of $0, 1, 2, 3, 4, 5$, and discard the last digit. We then remove disallowed permutations step by step, considering the $i^{th}$ digit in the permutation. In the first step we remove all permutations containing a 0 or 1 in $1^{st}$ position. Then, in the second step, we subtract all possible permutations with a 2 in $2^{nd}$ position, and add again all permutations containing a 0 or a 1 in $1^{st}$ position and a 2 in $2^{nd}$ position, since these were already eliminated in the first step. Removing invalid permutations one by one, we get:

  1. Permutations containing a 0 or 1 in $1^{st}$ position: $$720 - 2 \cdot 5! = 480$$

  2. Permutations containing a 2 in $2^{nd}$ position: $$480 - 5! + 2 \cdot 4! = 408$$

  3. Permutations containing a 3 in $3^{rd}$ position: $$408 - 5! + 2 \cdot 4! + 4! - 2 \cdot 3! = 348$$

  4. Permutations containing a 4 in $4^{th}$ position: $$348 - 5! + 2 \cdot 4! + 4! + 4! - 2 \cdot 3! - 2 \cdot 3! - 3 \cdot 2 + 2 \cdot 2 = 298$$

  5. Permutations containing a 5 in $5^{th}$ position: $$348 - 5! + 2 \cdot 4! + 4! + 4! + 4! - 2 \cdot 3! - 2 \cdot 3! - 2 \cdot 3! - 3 \cdot 2 - 3 \cdot 2 - 3 \cdot 2 + 2 \cdot 2 + 2 \cdot 2 + 2 \cdot 2 + 2 - 2 = 256$$

If you would like to verify these results, you can use the following Python script:

from itertools import permutations

d = [0] * 5
for p in permutations(range(6)):
  for i in range(5):
    if p[0] != 0 and p[i] != i + 1:
      d[i] += 1
    else:
      break

for r in d:
  print(r)
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .