Question 5
Let $n,d$ be positive integers. Let $S_n(d)$ be the set of all ordered tuples $(x_1,\ldots,x_d)$ satisfying:
(i) $x_i\in\{1,2,\ldots,n\}$ for $1\le i\le d$;
(ii) $x_i\ne x_{i+1}$ for $1\le i\le d-1$;
(iii) there are no indices $1\le i\lt j\lt k\lt l\le d$ such that $x_i=x_k$ and $x_j=x_l$.
(a) Find $|S_3(5)|$.
(b) Prove that $S_n(d)$ is nonempty if and only if $d\le2n-1$.
(i) $x_i\in\{1,2,\ldots,n\}$ for $1\le i\le d$;
(ii) $x_i\ne x_{i+1}$ for $1\le i\le d-1$;
(iii) there are no indices $1\le i\lt j\lt k\lt l\le d$ such that $x_i=x_k$ and $x_j=x_l$.
(a) Find $|S_3(5)|$.
(b) Prove that $S_n(d)$ is nonempty if and only if $d\le2n-1$.