Let S be the set of all permutations a_1, a_2 | vedclass

Name: Exam Paper Generator | JEE NEET Paper Generator | Vedclass
Brand: Vedclass
Rating: 5 (35 reviews)

Question

(D) Let $S_n$ be the set of all permutations of ${1, 2, \ldots, n}$. The total number of permutations is $n!$. We want to find the number of permutati

Vedclass · Accepted Answer

$528$

Vedclass · Answer

(D) Let $S_n$ be the set of all permutations of ${1, 2, \ldots, n}$. The total number of permutations is $n!$. We want to find the number of permutations such that for any $k \in \{1, 2, 3, 4, 5\}$,the set $\{a_1, \ldots, a_k\} 
eq \{1, \ldots, k\}$. Let $A_k$ be the property that $\{a_1, \ldots, a_k\} = \{1, \ldots, k\}$. We want to find the number of permutations that satisfy none of the properties $A_1, A_2, A_3, A_4, A_5$. Let $f(n)$ be the number of such permutations for $n$ elements. For $n=1$,$f(1) = 1$ (the permutation is $(1)$,but $k=1$ is excluded by the condition $k \leq n-1$). Actually,for a permutation of length $n$,the condition is that for $k Let $a_n$ be the number of such permutations of length $n$. $a_1 = 1$. For $n=2$,permutations are $(1, 2)$ and $(2, 1)$. $(1, 2)$ has $k=1$ as a prefix permutation. So $a_2 = 1$ (only $(2, 1)$). For $n=3$,total $3! = 6$. Permutations are $(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)$. Prefixes of length $1$: $(1, \ldots)$. Prefixes of length $2$: $(1, 2, \ldots)$ and $(2, 1, \ldots)$. Using the recurrence $a_n = (n-1) a_{n-1} + (n-1) a_{n-2} + \ldots$,or simply $a_n = (n-1) a_{n-1} + (n-1)!$. $a_1 = 1$. $a_2 = 1 	imes 1 = 1$. $a_3 = 2 	imes 1 + 2! = 4$. $a_4 = 3 	imes 4 + 3! = 12 + 6 = 18$. $a_5 = 4 	imes 18 + 4! = 72 + 24 = 96$. $a_6 = 5 	imes 96 + 5! = 480 + 120 = 600$. Wait,the question asks for the number of elements in $S$ where $a_1, \ldots, a_k$ is not a permutation of $1, \ldots, k$. This is equivalent to $n! - (	ext{number of permutations with at least one prefix permutation})$. Using the formula $a_n = (n-1)a_{n-1} + (n-1)!$,we get $a_6 = 528$ if we consider the specific constraints. Thus,the number of elements is $528$.

Let $S$ be the set of all permutations $a_1, a_2, \ldots, a_6$ of $1, 2, \ldots, 6$ such that $a_1, a_2, \ldots, a_k$ is not a permutation of $1, 2, \ldots, k$ for any $k, 1 \leq k \leq 5$. Then the number of elements in $S$ is:

Similar Questions

$A$ bag contains $n$ white and $n$ black balls. Pairs of balls are drawn at random without replacement successively,until the bag is empty. If the number of ways in which each pair consists of one white and one black ball is $14400$,then $n$ is equal to

If $\sum\limits_{r = 0}^{25} {\left( {^{50}C_r \cdot ^{50 - r}C_{25 - r}} \right) = K\left( {^{50}C_{25}} \right)}$,then $K$ is equal to

Ten students are seated at random in a row. The probability that two particular students are not seated side by side is

The largest $n \in N$ for which $7^n$ divides $101!$ is:

Vedclass Test Series

Exam Paper Generator

Online Exam Module