Question

Let $A=\{1,2,3,4,5\}$ and $B=\{-2,-1,0,1,2,3,4,5\}$. Then which of the following statements is (are) true?

• A. The number of increasing functions from $A$ to $B$ is 56
• B. The number of non-decreasing function from $A$ to $B$ is 792
• C. The number of onto functions from $A$ to $A$ such that $f(i) \neq i$ is equal to 44
• D. The number of onto functions from $B$ to $A$ is 126000

Answer 1

Answer: (A), (B), (C), (D)

All options are true

Answer 2

1. Increasing functions from A to B:

A strictly increasing function $f: A \to B$ means $f(1) < f(2) < \cdots < f(5)$. Such a function is determined by choosing 5 elements in increasing order from the 8 element set $B$.

$$\text{No. of functions} = \binom{8}{5} = 56.$$

2. Non-decreasing functions from A to B:

A non-decreasing function satisfies $f(1) \le f(2) \le \cdots \le f(5)$. Using the stars and bars method, the number of ways to choose 5 values out of 8 (with repetition allowed) is given by:

$$\binom{8+5-1}{5} = \binom{12}{5} = 792.$$

3. Onto functions from A to A with $f(i) \neq i$:

Onto functions $f: A \to A$ are bijections (permutations) on a 5-element set. The condition $f(i) \neq i$ for all $i$ means we need the number of derangements of 5 elements. The number of derangements of $n$ objects is given by:

$$!n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n\frac{1}{n!}\right).$$

For $n=5$:

$$!5 = 120\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 44.$$

4. Onto functions from B to A:

To count onto functions $f: B \to A$ with $|B|=8$ and $|A|=5$ use the inclusion-exclusion principle:

$$\text{No. of onto functions} = \sum_{j=0}^{5} (-1)^j \binom{5}{j} (5-j)^8.$$

Calculating term by term:

$$\begin{array}{rcl} j=0: & & \binom{5}{0}5^8 = 1 \cdot 390625 = 390625,\\[1mm] j=1: & & -\binom{5}{1}4^8 = -5 \cdot 65536 = -327680,\\[1mm] j=2: & & \binom{5}{2}3^8 = 10 \cdot 6561 = 65610,\\[1mm] j=3: & & -\binom{5}{3}2^8 = -10 \cdot 256 = -2560,\\[1mm] j=4: & & \binom{5}{4}1^8 = 5 \cdot 1 = 5,\\[1mm] j=5: & & -\binom{5}{5}0^8 = 0. \end{array}$$

Now summing these:

$$390625 - 327680 + 65610 - 2560 + 5 = 126000.$$