cmi-entrance 2019 QB1

cmi-entrance · India · ugmath 10 marks Permutations & Arrangements Counting Functions with Constraints

For a natural number $n$ denote by $\operatorname{Map}(n)$ the set of all functions $f : \{1,2,\ldots,n\} \rightarrow \{1,2,\ldots,n\}$. For $f, g \in \operatorname{Map}(n)$, $f \circ g$ denotes the function in $\operatorname{Map}(n)$ that sends $x$ to $f(g(x))$.
(a) Let $f \in \operatorname{Map}(n)$. If for all $x \in \{1,\ldots,n\}$ $f(x) \neq x$, show that $f \circ f \neq f$.
(b) Count the number of functions $f \in \operatorname{Map}(n)$ such that $f \circ f = f$.

For a natural number $n$ denote by $\operatorname{Map}(n)$ the set of all functions $f : \{1,2,\ldots,n\} \rightarrow \{1,2,\ldots,n\}$. For $f, g \in \operatorname{Map}(n)$, $f \circ g$ denotes the function in $\operatorname{Map}(n)$ that sends $x$ to $f(g(x))$.

(a) Let $f \in \operatorname{Map}(n)$. If for all $x \in \{1,\ldots,n\}$ $f(x) \neq x$, show that $f \circ f \neq f$.

(b) Count the number of functions $f \in \operatorname{Map}(n)$ such that $f \circ f = f$.

Paper Questions

QA1 QA10 QA2 QA3 QA4 QA5 QA6 QA7 QA8 QA9 QB1 QB2 QB3 QB4 QB5 QB6