Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 90
Текст из файла (страница 90)
Однако, проблемой остается их размещение. Оказывается, что лучше использовать левые (открывающие) скобки и первые 1О чисел, чем левые и правые скобки, поскольку чисел не может быть больше, чем левых скобок. Например, рассмотрим 3+4 †8х2 †:4 — 7+4х56 — 2х4. Согласно последовательности разместим левые скобки там, где имеется 1, а символ — там, где имеется — 1, после чего получим (3+ ((4 — ((8 х 2) кь 4)) — ((((7+ 4) х 5) "6) — (2 х 4)))).
Левые скобки размещены в паре с правыми скобками. Теперь рассмотрим что соответствует (3 + ((((4 — 8) х 2) кь 4) — ((7 + 4) х (5 (6 — (2 х 4)))))), и наконец что соответствует ((((3 + 4) — 8) х 2) †: ((((((4 — 7) + 4) х 5) 6) — 2) х 4)). РКЗДЕЛ 12.2.
Числа Каталана 497 Формулировке задач мы уделили достаточно много времени. Теперь приступим к их решению. Для начала найдем решение при и = 10, чтобы окончательно разобраться с нашим примером, а затем выведем формулу для произвольного и. Вернемся к человеку, идущему на работу. Для начала рассмотрим все пути, по которым он может добраться до работы мокрым или сухим, не возвращаясь. Ему следует в некотором порядке пройти 10 кварталов на север и 10 на восток. Поскольку рассматриваются все пути, включая те, которые пересекают реку, то десять Е и десять ЛГ могут быть в любом порядке. Если рассмотреть строку из десяти Е и десяти М как строку из 20 пробелов, то необходимо выбрать 10 из них, в которых разместить Е. Таким образом, общее количество путей к месту работы равно количеству способов выбрать 10 пробелов из 20, в которых будут размещены Е.
Это число равно Сзо, или (~~~) =,~~',. Теперь воспользуемся довольно распространенным в подсчетах приемом. Подсчитаем количество путей, при прохождении которых наш персонаж будет мокрым, и вычтем это число из общего количества путей. Иными словами, найдем количество путей, которые нам не подходят, и вычтем его из общего количества путей, чтобы получить количество путей, по которым наш персонаж может безопасно добраться до места работы. Наш герой оказывался в реке всякий раз, когда, достигнув какой-либо точки маршрута, он проходил на север больше кварталов, чем на восток.
Иными словами, если в некоторой точке продвижений )У у него на одно больше, чем продвижений Е, то он попадает в реку. Например, в строке ЕЕММЛ7ЕЕЛ(ЕЛ(ЕЛ(ЕЕЛ(Л(МЕЛ(Е знак М показывает точку, в которой человек попадает в реку. К моменту попадания в реку было сделано два продвижения Е и три продвижения Х, после чего осталось еще 8 Е и 7 Х. Заменим теперь все Е, расположенные в строке после ЛГ, на Х, а все Лг — на Е, после чего получаем строку (2) ЕЕЛ1НЛ(НЛ7ЕХЕИЕЛ(Л(ЕЕЕХЕИ.
На новом пути (который не приведет человека к месту работы) имеется 2 Е и 3 М, за которым следует 8 М и 7 Е, что в сумме даст 9 Е и 11 Л1. Это понятно, если учесть, что при попадании в реку в пройденном пути было на одно Л' больше, поэтому в оставшейся части пути на одно Е было больше. После изменения остатка пути в нем оказалось на одно Л' больше. Следовательно, во всем пути продвижений М стало на два больше, чем продвижений Е.
Попробуем еще раз. В строке (3) ЕЫЕЛ(ЕМЕЖЛ7ЕМЕЛ(ЕЕЛ(ЕМЧЕ человек попадает в реку после 5 продвижений Л1 и 4 продвижений Е. После Л( осталось 5 Лг и б Е продвижений. Опять заменяем каждое Е, стоящее в строке после ЛГ, на Л(, а каждое М вЂ” на Е, после чего получаем б Лг и 5 Е, стоящие в строке после ЛГ, ЕЛ(ЕХЕХЕЛ(Л7МЕЛ7ЕХЛ1 ЕЛ(ЕЕЖ. (4) Поэтому новая строка имеет в сумме 9 Е и 11 Л1 продвижений. Обратно, если имеется строка, в которой 9 Е и !1 Лг, то в некоторой точке строки продвижений Лг должно быть больше, чем продвижений Е. Выбираем 498 ГлдВА 12. снова о комбонаторных подсчетах первую такую точку и меняем первое такое М на М, Далее снова изменяем оставшуюся часть строки, меняя каждое Х на Е и каждое Š— на М.
Например, пусть дана строка ЕМЕХЕЕМЕХЕХММЕХЕХХХЕ, (5) которая содержит 9 Е и 11 М. Выберем первое место в последовательности, в котором количество продвижений Х больше, чем количество продвижений Е, и заменим М в этой точке на М. На данный момент в строке имеется б Е и 7 М, включая М. Остаток строки содержит 3 Е и 4 М. Меняем все М, стоящие после М, на Е, а все Е, стоящие после М, на М.
В результате получаем (6) ЕМЕМЕЕХЕХЕММММЕХЕЕММ, в которой после М стоит 4 Е и 3 М. В сумме получаем 10 Е и 10 Х. Опять получили путь, который приводит нашего героя в реку, и это произойдет в точке М. Это понятно, поскольку мы начали с момента 9 Е и 11 Х, и до момента М, и включая его, у нас продвижений Х было на одно больше, чем продвижений Е. Следовательно, оставшаяся часть строки, стоящая после М, также имеет на одно М больше, чем Е.
После изменения остатка строки в ней продвижений Е на одно больше, чем продвижений Х. Следовательно, во всей новой строке всегда будет равное количество Е и Х, а начальная часть строки, включая М, всегда будет содержать на одно М больше, чем Е. При этом М вЂ” то лишнее продвижение на север, которое и приводит нашего героя в реку. Легко заметить, что каждая строка, которая "окунает" наш персонаж в реку, может быть преобразована в строку с 9 Е и 11 Х, и обратно, каждая строка, содержащая 9 Е и 11 М, может быть преобразована в строку, которая приводит нашего героя в реку.
Отсюда количество строк, приводящих в реку, равно количеству способов сформировать строку, содержащую 9 Е и 11 Х. Таким обгоазом, 9 мест для Е выбираются из 20 мест, и для этого существуют С(20,9) = ( о) = го', способов. Поэтому количество способов добраться до места работы сухим равно числу, полученному при вычитании из общего числа способов количества путей, при кото~ых персонаж попадает в реку. Обозначим это число С1о, так что С1о =,о... — —,„,.
Это число можно быго~ о~ ло бы подсчитать, но настояшие математики никогда не используют числа, когда можно оперировать символами, чтобы избежать арифметических ошибок. Предположим, что имеется п кварталов на север и п на восток, т.е. в рассмотренном выше примере п = 10. Теперь используем строку длины 2п, половину которой составляют символы Е, а вторую половину — символы Х. Во избежание попадания человека в реку, нежелательно, чтобы число символов М превышало число символов Е. Как и ранее, рассмотрим все возможные пути попасть к месту работы сухим или мокрым без возвращений.
Выбираем из 2п возможных мест п мест для размешения Е. Как было показано, сушествуют С(2п, п) = (г„") = ~„,",,~, таких размешений. Далее опять находим пути, которые нам не подходят, поскольку приводят нашего героя в реку. Используя процедуру, описанную выше, находим, что количество таких путей равно количеству строк, в которых символ Е появляется и — 1 раз, символ Х появляется и+1 раз. Число таких строк равно количеству способов выбрать и — 1 место из 2п возможных для размешения сим° е, х. р.
а бу с(2, — 1) = („'"З = ~„-+~~„-';;;;„с.. РАЗДЕЛ т2.2. Числа Каталана 499 ~2пН дл ! количество безопасных путей добраться до места работы, равно „;„,' — „ Теперь можно осуществить подсчет. Итак, получаем (2п)! (2п)! (2п)! ( и ''1 ( (2п)! '~ и!и! (и — 1)!(и+1)! п)п) (,и+1/ (, и!и! / Прежде чем оставить это путешествие, снова вернемся к случаю и = 10. Рассмотрим иной способ подсчета подходящих путей, т.е.
С„, а также случай, когда наш герой достигает реки, пройдя один километр на восток и один на север. Считаем, что дом нашего героя находится в начале координат (0,0), так что он достигает точки (1,1) и продолжает путь к месту работы. Этот путь изображен на рис. )2.2. о,д> Рис. !2.3 Сколько существует таких путей? Очевидно, попасть в точку (1,1) по суше можно только одним способом. Легко видеть, что задача о том, как попасть из точки (1, 1) в точку (10, 10), т.е. к месту работы, ничем не отличается от исходной, за исключением того, что теперь нужно, не угодив в реку, пройти 9 кварталов на восток и 9 на север. Это можно сделать Сд способами. Поскольку Со = 1, мы говорим, что имеются Со Сд способов попасть к месту работы, проходя через точку (1,1). Это соответствует обозначениям, которые мы введем в дальнейшем.
Теперь предположим, что наш герой по пути на работу первый раз достигает берега реки в точке (я,й), где 1 < и < 10. Для начала подсчитаем, сколько путей, не достигающих берега реки, вплоть до точки (й, й), ведут из точки (0,0) в точку (й, й).
Любой из путей должен начинаться с движения на 2 квартала на восток, иначе персонаж достигнет реки в точке (1,1). Закончить путь персонаж должен движением на 2 квартала на север, иначе ему следовало бы достигнуть реки в точке (к — 1,н — 1). Как видно из рис. 12.3, если провести линию, параллельную реке и проходящую на один километр южнее между точками (1,0) и (й, й — 1), то путь не пересечет эту линию. Следовательно, можно использовать любой путь, который начинается в точке (1, 0), проходит 9 — 1 блоков на север и й — 1 блоков на восток и достигает точки (ь.,й — 1), не пересекая новую диагональ. Существуют Сь 1 способов провести такой путь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
