Question 169
For two positive integers $n$ and $d$, let $S_n(d)$ be the set of all ordered $d$-tuples $(x_1, x_2, \dots, x_d)$ that satisfy all the following conditions:
i) $x_i \in \{1, 2, \dots, n\}$ for every $i \in \{1, 2, \dots, d\}$;
ii) $x_i \neq x_{i+1}$ for every $i \in \{1, 2, \dots, d-1\}$;
iii) There do not exist indices $1 \le i \lt j \lt k \lt l \le d$ such that $x_i = x_k$ and $x_j = x_l$.
a) Compute $|S_3(5)|$.
b) Prove that $|S_n(d)| \gt 0$ if and only if $d \le 2n-1$.
i) $x_i \in \{1, 2, \dots, n\}$ for every $i \in \{1, 2, \dots, d\}$;
ii) $x_i \neq x_{i+1}$ for every $i \in \{1, 2, \dots, d-1\}$;
iii) There do not exist indices $1 \le i \lt j \lt k \lt l \le d$ such that $x_i = x_k$ and $x_j = x_l$.
a) Compute $|S_3(5)|$.
b) Prove that $|S_n(d)| \gt 0$ if and only if $d \le 2n-1$.