1, 2 ..... n. Для кожного з цих ланок треба знати, в якому напрямку він йде. Наприклад, зображений на рис. 4 шлях приводить в точку
А (1, 2) і задається послідовністю букв (л, н, н, п, п, в, в, в. п, в, п, н, л, л, в), де буква В«пВ» означає рух вправо, В«лВ» - вліво, В«вВ» - вгору і В«нВ» - вниз. Тут п = 15, р = 1, q = 2. Позначимо через X безліч всіх номерів ланок, які йдуть вліво або вниз, а через Y безліч всіх номерів ланок, які йдуть вправо або вниз. Наприклад, для колії на рис. 4 ці множини такі:
X = {1, 2, 3, 12, 13, 14}, Y = {2, 3 , 4, 5, 9, 11, 12}.
В
Рис. 4
Виявляється, ці два набори повністю визначають шлях. Зовсім легко знайти ті номери ланок, які йдуть вниз - вони входять і в X, і в Y (на прикладі палити 2, 3 та 12). Рухам вліво відповідають числа з X, що не входять в Y (на прикладі - число 1, 13, 14); вправо - числа з Y, що не входять в X (у прикладі - числа 4, 5, 9, 11); вгору - числа, що не входять ні в X, ні і Y (і прикладі числа 6, 7, 8, 10, 15). Таким чином, задавши множини X в Y, ми для кожного моменту часу задаємо напрям руху, а тим самим і весь шлях з точки Про в деяку точку А. Множини X і У можна задавати довільно при одному лише обмежувальні умови - після n кроків нам треба опинитися в точці А (р; q ). Ця умова дозволяє знайти число елементів у X і в Y. Справді, позначимо через х п , х л , х в , х н кількість
ланок, що йдуть відповідно вправо, вліво, вгору і вниз. Тоді х п - х л = р , х в - х н = q, х п + х л + х в + х н = п. Безліч X складається з до номерів, яким відповідають рухи вліво або вниз. Легко знаходимо . Це зрозуміло - якщо з усіх п рухів прибрати р рухів вправо і q рухів вгору, то ми як би прийдемо назад в точку О. т. е. рухів вниз і вліво буде стільки ж. скільки залишилися вгору і вправо - вони погашають один одного. У нашому прикладі X складається з 6 елементів. p> У безлічі Y беруться ходи вправо, а не ходи вліво, їх на р більше, ніж ходів вліво (за рахунок цього ми і потрапляємо в точку з абсцисою р). Ходи ж униз в обох множин...
