MathDB

Let

n

be a positive integer, X \equal{} \{1, 2, \ldots , n\}, and

k

a positive integer such that

\frac{n}{2} \leq k \leq n.

Determine, with proof, the number of all functions

f : X \mapsto X

that satisfy the following conditions: (i) f^2 \equal{} f; (ii) the number of elements in the image of

f

k;

(iii) for each

y

in the image of

f,

the number of all points

x \in X

such that f(x)\equal{}y is at most

2.

Problem Statement