Ukrainian Mathematical Olympiad

Через $m$, $0\le m\le n$, позначимо кількість чисел множини $\{1,2,\dots ,n\}$, які знаходяться серед індексів $i_1<i_2<\cdots <i_n$. Неважко довести, що такими $m$ індексами визначаються $n-m$ чисел із множини $\{n+1,n+2,\dots ,2n\}$, які увійдуть до даного набору індексів $i_1<i_2<\cdots <i_n$. Цим повністю описуються всілякі вдалі послідовності $a_1,a_2,\dots ,a_{2n}$. Для $m=0$ маємо вдалу послідовність $1,2,\dots ,n$, $1,2,\dots ,n$. Але ж ця сама вдала послідовність утворюється ще в $n$ випадках, коли для набору індексів $i_1<i_2<\cdots <i_n$ маємо, що $$\{i_1,i_2,\dots ,i_n\}\cap \{1,2,\dots ,n\}=\{1,2,\dots ,m\},1\le m\le n.$$ Усіляких підмножин $n$-елементної множини $\{1,2,\dots ,n\}$, відмінних від підмножин $\{1,2,...,m\}$, $1\le m\le n$, існує $2^n-n$. Усім таким підмножинам відповідають різні вдалі послідовності (порожня підмножина відповідає випадку $m=0$ і також враховується серед $2^n-n$ підмножин). Відповідь: $2^n-n$.