Для каж­до­го k, обо­зна­чим через мно­же­ство марш­ру­тов шашки, ве­ду­щих из ле­во­го ниж­не­го в пра­вый верх­ний угол доски и де­ла­ю­щих ровно шагов ниже глав­ной диа­го­на­ли. Имеет место по­тря­са­ю­щий факт: при фик­си­ро­ван­ном n все мно­же­ства со­дер­жат по­ров­ну эле­мен­тов!

Это утвер­жде­ние на­зы­ва­ет­ся тео­ре­мой Чанга-Фел­ле­ра, оно впер­вые до­ка­за­но Мак­Ма­го­ном в 1909 г. При­во­ди­мое ниже ком­би­на­тор­ное до­ка­за­тель­ство по­яви­лось в 1955 г.

Предъ­явим вза­им­но од­но­знач­ное со­от­вет­ствие между мно­же­ства­ми и Марш­рут шашки можно ин­тер­пре­ти­ро­вать как по­сле­до­ва­тель­ность из букв «в» или «п», при­чем букв каж­до­го вида в ней по­ров­ну. Рас­смот­рим про­из­воль­ный марш­рут a из мно­же­ства За­пи­шем его в виде

где «в» обо­зна­ча­ет пер­вый ход, ко­то­рый шашка сде­ла­ла вверх, на­хо­дясь на диа­го­на­ли; «п»  — это ход, ко­то­рым она впер­вые после этого вер­ну­лась на диа­го­наль; то, воз­мож­но, пу­стая по­сле­до­ва­тель­ность ходов, ко­то­рые шашка со­вер­ши­ла до вы­пол­не­ния хода в (эти ходы были сде­ла­ны ниже диа­го­на­ли); это, воз­мож­но, пу­стая по­сле­до­ва­тель­ность ходов, ко­то­рые шашка со­вер­ши­ла после вы­пол­не­ния хода в, но до вы­пол­не­ния хода «п» (эти ходы были сде­ла­ны выше диа­го­на­ли); на­ко­нец, w  — это все осталь­ные ходы шашки. По­ста­вим в со­от­вет­ствие марш­ру­ту сле­ду­ю­щий марш­рут b из мно­же­ства :

Это со­от­вет­ствие би­ек­тив­но.

Ответ: