Problem

Source: 2014 Thailand October Camp Combinatorics Exam p2

Tags: combinatorics



Determine the number of sequences of points $(x_1, y_1),(x_2, y_2), \dots ,(x_{4570}, y_{4570})$ on the plane satisfying the following two properties: $\text{(i)}$ $\{x_1,x_2,\dots,x_{4570}\}=\{1,2,\dots,2014\}$ and $\{y_1,y_2,\dots,y_{4570}\}=\{1,2,\dots,2557\}$ $\text{(ii)} $ For each $i = 1, 2,\dots , 4569$, exactly one of $x_i = x_{i+1}$ and $y_i = y_{i+1}$ holds.