Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
14.28. Ответ. Пусть множители имеют вид 2 a 1 5 b 1 , 2 a 2 и 2 a 3 5 b 3 . Тогда a 1 + a 2 + a 3 = 6 и b 1 + b 2 + b 3 = 6. При этом числа a i и могут быть равны нулю. Если a 1 = k, то для разложения+ a 3 = 6 − k получаем 7 − k вариантов. Поэтому для разложения+ a 2 + a 3 = 6 получаем 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 вариантов. Всего получаем 28 2 = 784 способа. Но мы пока не учли тождественность разложений, отличающихся лишь порядком множителей. Есть ровно одно разложение, не зависящее от порядка множителей, в котором все множители равны 100. Те разложения, в которых есть два равных множителя, мы посчитали трижды. В каждый из равных множителей 2 может входить в степени 0, 1, 2 или 3, те. всего четырьмя различными способами столькими же способами может входить 5. Всего получаем разложений такого видано одно из них — рассмотренное выше разложение стремя равными множителями. Остаётся 15 разложений, каждое из которых мы посчитали трижды. Количество разложений с попарно различными множителями равно. Каждое из них мы посчитали 6 раз, поэтому среди них будет 738/6 = 123 различных разложения. Всего получаем + 15 + 123 = 139 разложений. 14.29. С одной стороны, 2 2n = (1 + 1) 2n = C 0 2n + C 1 2n + . . . + С другой стороны n! = 2n n · 2n − 1 n − 1 · . . . · n + 1 поскольку − k n − k > 2 для k = 0, 1, . . . , n − 1. Глава 14. Комбинаторика. По определению C k p = p(p − 1) . . . (p − k + 1) 1 · 2 · . . . · k . Числитель делится на p, а знаменатель не делится на p. Поэтому целое число, которое получается в результате деления числителя на знаменатель, делится на p. 14.31. Тождество C k p = C k −1 p −1 + показывает, что те. Если 1 6 m 6 p − 1, то согласно задаче 14.30 каждое слагаемое делится на p. 14.32. Тождество (1 + x) np = ((1 + показывает, что. . . Согласно задаче 14.30 число делится на p, если 0 < k < Поэтому в указанной сумме на делятся все слагаемые, за исключением тех, для которых k i = p для некоторого i. Каждое из таких слагаемых равно 1, а их количество равно n. 14.33. При m=2 нужно доказать, что C m n = n(n − делится на это очевидно. Пусть m > 3. В выражении C m n = n(n − 1) . . . (n − m + 1) 1 · 2 · . . . · числитель делится на n = p a −2 , а наивысшая степень p, на которую делится знаменатель, равна h m p i + h m p 2 i + . . . 6 m p + m p 2 + . . . = m p − Если m = 3, то делится на p в степени a − 2 − h 3 p i + h 3 p 2 i + . . . = a − 2 − h 3 p i > a − 3 = a − Если m > 4, то делится на p в степени a − 2 − h m p i + h m p 2 i + . . . > a − 2 − m p − 1 > a − 2 − m 2 > a − m. 14.34. Ясно, что C k n = n(n − 1) . . . (n − k + 1) k! . Рассматриваемое простое число p делит числитель этой дроби. Пусть p r — наибольшая степень p, которая делит хотя бы одно из чисел от n − k + 1 до включительно пусть это будет число m если таких чисел несколь- Решения задач 193 ко, то мы выбираем любое из них. Сосредоточим внимание на числе m ив соответствии с этим запишем числитель рассматриваемой дроби в виде+ a)(m + a − 1) . . . (m + 1)m(m − 1) . . . (m − здесь m + a = n и m − b = n − k + 1, поэтому k = a + b + 1. Множители знаменателя переставим в соответствии с записью числителя a(a − 1) · . . . · 1 · (a + 1)(a + 2) . . . (a + b + Число + 1)(a + 2) . . . (a + b + 1) b! = целое обозначим его Итак + a a · m + a − 1 a − 1 · . . . · m + 1 1 · m − 1 1 · m − 2 2 · . . . · m − b b · m l ; множитель m l мы переставили в конец. Пусть x — некоторое целое число, причём −b6x6a, а p r 1 — наибольшая степень p, делящая x. Если r 1 < r, то наибольшая степень, которая делит числитель дроби + x x , равна p r 1 . Степени в числителе ив знаменателе сокращаются. Предположим теперь, что r 1 > r. Из неравенств для x следует, что n − k + 1 6 m + x 6 Поэтому согласно выбору числа m наибольшая степень p, которая делит числитель дробине превосходит p r . В этом случае после сокращения степень p может остаться только в знаменателе. Таким образом, наибольшая степень p, делящая C k n , не превосходит наибольшей степени p, делящей m. Значит, p a 6 p r 6 m 6 n. 14.35. Первое решение. Элемент, не обладающий ни одним изданных свойств, даёт вклад только в первый член Элемент, обладающий ровно одним свойством, даёт вклад впервые два члена его общий вклад равен 1 − 1 = 0. Элемент, обладающий ровно k > 2 свойствами, даёт вклад впервые членов. В член P i 1 < ...<i l N i 1 ...i l он даёт вклад C l k , поэтому его общий вклад равен − C 1 k + C 2 k + . . . + (−1) l C l k + . . . + (−1) k C k k = (1 − 1) k = Второе решение. Положим, если й предмет обладает свойством если не обладает Глава 14. Комбинаторика Тогда искомое число равно C(K, 1))(1 − C(K, 2)) . . . (1 − C(K, n)) = = N − n X i =1 N X K =1 C(K, i) + X i 1 < i 2 N X K =1 C(K, i 1 )C(K, i 2 ) − . . . Остаётся заметить, что, i) =N i , P i 1 < i 2 N P K =1 C(K, i 1 )C(K, i 2 ) = = и т. д. Пусть данные предметы — числа от 1 до n, а свойство заключается в том, что данное число не делится на p i . Количество чисел от 1 до n, делящихся на p i , равно n/p i , делящихся на и на p j , равно n p i p j и т. д. Поэтому по формуле включений и исключений − 1 p 1 ” . . . “ 1 − 1 p k ” 14.37. а) Воспользуемся формулой включений и исключений. А именно, пусть предметы — это перестановки чисел 1, . . . , n; их количество равно n!. Свойство заключается в том, что a i = Тогда N i 1 ...i k = (n − k)! — количество перестановок, оставляющих на месте k чисел i 1 , . . . , i k . Количество слагаемых в сумме P i 1 < ...<i k N i 1 ...i k равно C k n — это количество способов выбрать k элементов i 1 , . . . , среди n элементов. Остаётся заметить, чтоб) Доля таких перестановок равна − 1 + 1 2! − 1 3! + . . . + ( −1) k k! + . . . При n → ∞ это число стремится к задача 29.47). 14.38. Положим A(m, n) = m! (2n + 2m)! (2m)! n! (n + m)! . Тогда A(m, 0) = и A(0, n) = C n 2n . Кроме того, n−1)+A(m−1, n)= (m −1)! (2n+2m−2)! (2m −2)! (n−1)! (n+m−1)! “ 4m 2m(2m−1) + 1 n ” Решения задач 195 Заметив, что + 2m − 1 n(2m − 1) = (2n + 2m − 1)(2n + 2m)m n(2m − 1)2m(n + m) , получим, n − 1) + A(m − 1, n) = A(m, n). 14.39. Пусть искомое число равно d n . Ясно, что d 3 = 1 и d 4 = Для удобства положим d 2 = 1. Проверим, что d 5 = d 2 d 4 + d 3 d 3 + Фиксируем одну из сторон пятиугольника. Пусть этот пятиугольник разрезан непересекающимися диагоналями на треугольники. К фиксированной стороне прилегает ровно один из этих треугольников. Возможны три варианта слева от этого треугольника расположен четырёхугольник, по обе стороны расположены треугольники, справа расположен четырёхугольник. Каждый из этих многоугольников нужно разрезать диагоналями на треугольники, а затем подсчитать общее число вариантов. В результате получим+ d 3 d 3 + d 4 = d 2 d 4 + d 3 d 3 + Аналогично для любого n получаем d n = d 2 d n −1 + d 3 d n −2 + . . . . . . + d n −1 d 2 . Значит, d n = c n −2 14.40. Между расстановками скобок для n + 1 букв и разрезани- ями (n + угольника на треугольники непересекающимися диагоналями можно установить взаимно однозначное соответствие. На рис. 14.2 показано, как это делается в конкретном случае. b a ( ab) c d e (( ab)c) ( de) ((( ab)c)(de)) Рис. В общем случае буквы последовательно записываются на сторонах+ угольника почасовой стрелке. Одна фиксированная сторона остаётся свободной. Если заданы диагонали (n + угольника Глава 14. Комбинаторика то каждой диагонали сопоставляем пару скобок, заключающих выражения на сторонах прилегающего к ней треугольника. Так последовательно будут записаны выражения в скобках на каждой диагонали, ив конце на свободной стороне будет записана требуемая расстановка скобок. Наоборот, если задана расстановка пар скобок, то ей можно сопоставить набор диагоналей, сопоставляя каждой паре скобок диагональ, начиная со скобок, заключающих пару соседних букв. Правильная скобочная структура из n скобок характеризуется тем, что в ней n левых скобок, n правых скобок, ив любом её начальном участке количество правых скобок не превосходит количества левых скобок. Ясно, что при n = 1 и 2 количество правильных скобочных структур равно 1 и 2 соответственно. Требуемое рекуррентное соотношение доказывается следующим образом. Сопоставим крайней левой скобке первую правую скобку, для которой количество левых скобок и количество правых скобок, заключённых между этими скобками, равны. Тогда между указанными скобками заключена правильная скобочная структура из k пар скобок для некоторого k возможно, k = 0). Действительно, иначе выбранная правая скобка не была бы первой. Вне выбранных скобок расположена правильная скобочная структура из n − k − 1 пар скобок. Ясно также, что обе эти правильные скобочные структуры могут быть произвольными. а) Взаимно однозначное соответствие между путями Дика и правильными скобочными структурами из задачи можно установить, сопоставив звену (1, 1) левую скобку, а звену) — правую скобку. б) Дополним путь Дика (в конце) одним звеном (1, −1). Фиксируем в полученном пути одно из n+1 звеньев (1, −1) и сопоставим ему путь из точки (1, −1) в точку (2n + 1, −1) следующим образом. Перенесём параллельно в начало координат путь, который состоит из фиксированного звена и следующего за ним участка пути Дика, включая добавленное звено. Вконец полученного пути перенесём начальный участок пути Дика от начала координат до фиксированного звена. Теперь фиксированное звено всегда ведёт в точку (1, −1), поэтому мы получаем путь из точки (1, −1) в точку. Поэтому пути мы можем восстановить исходный путь Дика. А именно, рассмотрим все нижние точки пути и выберем среди них крайнюю справа. Эта точка разбивает путь на два участка. Перенесём первый участок так, чтобы он заканчивался в точке (2n + 1, −1), а второй участок — так, чтобы он начинался в точке (0, 0). В результате после отбрасывания последнего звена Решения задач 197 получим путь Дика это очевидно для первого участка полученного пути и легко проверяется для второго. Если мы возьмём ка- кую-нибудь другую нижнюю точку пути и попробуем применить туже самую конструкцию, то для первого участка полученного пути требуемое свойство будет выполняться, а для второго — нет. Количество всех путей из точки (−1, 1) в точку (2n + 1, равно C n 2n . Действительно, из 2n звеньев мы должны выбрать n звеньев. Каждому пути Дика соответствует ровно n + 1 таких путей, поэтому количество путей Дика равно + 1 C n 2n 14.43. а) Между такими последовательностями и путями Дика можно установить взаимно однозначное соответствие, сопоставив числу звено (1, б) Положим a i = 1, если у го человека в очереди 50 рублей, и a i = −1, если 100. Кассир сможет всем дать сдачу тогда и только тогда, когда на каждом шаге количество полученных им 50-рублёвых купюр не меньше количества 100-рублёвых, т. е. a 1 > 0, a 1 + a 2 > 0, . . . , a 1 + a 2 + . . . + a 2n−1 > 0 (по условию+ a 2 + . . . + a 2n = 0). Таким образом, мы приходим к задаче а. Первый и последний ходы ладьи определены однозначно. Поэтому можно рассматривать пути ладьи без первого и последнего хода. Взаимно однозначное соответствие между такими путями и путями Дика из 2(n − 2) звеньев устанавливается очевидным образом. На рис. 14.3 показано, как плоскому бинарному дереву с одним корнем и n листьями можно сопоставить разбиение+ угольника на треугольники и расстановку скобок для e d c b a a b c d e ( ab) (( ab)c) ( de) ((( ab)c)(de)) Рис. 14.3 Глава 14. Комбинаторика букв. В многоугольнике выделяется одна сторона, которая соответствует корню. Остальные стороны соответствуют листьям. а) Количество способов пометить n вершин (2n + угольника единицами (а на остальные места поставить нули) равно. Число 2n + 1 не делится на n, поэтому никакой набор пометок не может перейти сам в себя при повороте (2n + 1)-угольника. Количество поворотов (2n + угольника, переводящих его все- бя, равно 2n + 1. Поэтому количество различных наборов пометок равно 2n + б) Покажем, что существует взаимно однозначное соответствие между наборами пометок и расстановками n пар скобок для n + букв. Сопоставим расстановке скобок последовательность из нулей и единиц, заменив каждую левую скобку единицей, а каждую букву нулём; правые скобки при этом игнорируются. Обратная операция для последовательностей определена не всегда, потому что расстановке скобок не может соответствовать последовательность, начинающаяся с нуля. Поэтому запишем полученную последовательность в вершинах правильного (2n + угольника почасовой стрелке. Для такого набора пометок обратная операция определена однозначно. Действительно, нулей больше, чем единиц, поэтому обязательно найдётся тройка последовательных чисел 100. Для такой тройки расстановка скобок определена однозначно правая скобка стоит сразу же за соответствующими двумя буквами. Выражение в скобках играет такую же роль, как буква. Поэтому последовательность 100 можно заменить на 0, перейдя к (2n − угольнику, и т. д. Воспользовавшись формулой из задачи 14.18, получим 1 − x − y + 2xy = 1 (1 − x)(1 − y) · 1 1 + xy (1 − x)(1 − y) = = ∞ X k =0 ( −1) k x k y k (1 − x) k +1 (1 − Значит, a p,q = P k>0 ( −1) k C k p C k q — коэффициент при в выражении+ x) p (1 − x) q . Нас интересует случай, когда p = 2n и q = 2n + В этом случае (1 + x) p (1 − x) q = (1 − x 2 ) 2n (1 − x) 2 ; коэффициент Решения задач 199 при равен (−1) n C n 2n + (−1) n −1 C n −1 2n = (−1) n (2n)! n! n! “ 1 − n n + 1 ” = = (−1) n 1 n + 1 C n 2n |