WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 19 | 20 || 22 | 23 |   ...   | 65 |

Тогда искомое число равно N 1 - C(K, 1) 1 - C(K, 2)... 1 - C(K, n) = K=n N N = N - C(K, i) + C(K, i1)C(K, i2) -...

i=1 K=1 i1

i1

pipj Поэтому по формуле включений и исключений 1 1 1 n (n) = n - n +... + + n +... + -... + (-1)k = p1 pk p1p2 p1... pk 1 = n 1 -... 1 -.

p1 pk Глава 14. Комбинаторика 14.37. а) Воспользуемся формулой включений и исключений. А именно, пусть предметы это перестановки чисел 1,..., n; их количество равно n!.

Свойство Pi заключается в том, что ai = i. Тогда Ni1...ik = (n - k)! количество перестановок, оставляющих на месте k чисел i1,..., ik. Количество n слагаемых в сумме Ni1...ik равно это количество способов i1<...

k k! б) Доля таких перестановок равна 1 1 (-1)k (-1)n 1 - 1 + - +... + +... +.

2! 3! k! n! При n это число стремится к e-1 (задача 29.47).

m!(2n + 2m)! 14.38. Положим A(m, n) =. Тогда A(m, 0) = 1 и A(0, n) = (2m)!n!(n + m)! 2n =. Кроме того, n (m - 1)!(2n + 2m - 2)! 4m 4A(m, n - 1) + A(m - 1, n) = +.

(2m - 2)!(n - 1)!(n + m - 1)! 2m(2m - 1) n 2n + 2m - 1 (2n + 2m - 1)(2n + 2m)m Заметив, что =, получим 4A(m, n - 1) + n(2m - 1) n(2m - 1)2m(n + m) + A(m - 1, n) = A(m, n).

14.39. Пусть искомое число равно dn. Ясно, что d3 = 1 и d4 = 2. Для удобства положим d2 = 1. Проверим, что d5 = d2d4 + d3d3 + d4d2. Фиксируем одну из сторон пятиугольника. Пусть этот пятиугольник разрезан непересекающимися диагоналями на треугольники. К фиксированной стороне прилегает ровно один из этих треугольников. Возможны три варианта: слева от этого треугольника расположен четырёхугольник, по обе стороны расположены треугольники, справа расположен четырёхугольник. Каждый из этих многоугольников нужно разрезать диагоналями на треугольники, а затем подсчитать общее число вариантов. В результате получим d4 + d3d3 + d4 = d2d4 + + d3d3 + d4d2.

Аналогично для любого n получаем dn = d2dn-1 + d3dn-2 +... + dn-1d2.

Значит, dn = cn-2.

14.40. Между расстановками скобок для n+1 букв и разрезаниями (n+2)угольника на треугольник непересекающимися диагоналями можно установить взаимно однозначное соответствие. На рис. 14.2 показано, как это делается в конкретном случае. В общем случае буквы последовательно записываются на сторонах (n + 2)-угольник по часовой стрелке. Одна фиксированная сторона остаётся свободной. Если заданы диагонали (n + 2)-угольника, то каждой диагонали сопоставляем пару скобок, заключающих выражения на сторонах прилегающего к ней треугольника. Так последовательно будут записаны выражения в скобках на каждой диагонали, и в конце на свободной стороне будет записана требуемая расстановка скобок. Наоборот, если задана 176 Глава 14. Комбинаторика Рис. 14.2.

расстановка пар скобок, то ей можно сопоставить набор диагоналей, сопоставляя каждой паре скобок диагональ, начиная со скобок, заключающих пару соседних букв.

14.41. Правильная скобочная структура из n скобок характеризуется тем, что в ней n левых скобок, n правых скобок, и в любом её начальном участке количество правых скобок не превосходит количества левых скобок. Ясно, что при n = 1 и 2 количество правильных скобочных структур равно 1 и соответственно. Требуемое рекуррентное соотношение доказывается следующим образом. Сопоставим крайней левой скобке первую правую скобку, для которой количество левых скобок и количество правых скобок, заключённых между этими скобками, равны. Тогда между указанными скобками заключена правильная скобочная структура из k пар скобок для некоторого k (возможно, k = 0). Действительно, иначе выбранная правая скобка не была бы первой. Вне выбранных скобок расположена правильная скобочная структура из n - k - 1 пар скобок. Ясно также, что обе эти правильные скобочные структуры могут быть произвольными.

14.42. а) Взаимно однозначное соответствие между путями Дика и правильными скобочными структурами из задачи 14.41 можно установить, сопоставив звену (1, 1) левую скобку, а звену (1, -1) правую скобку.

б) Дополним путь Дика (в конце) одним звеном (1, -1). Фиксируем в полученном пути одно из n + 1 звеньев (1, -1) и сопоставим ему путь из точки (1, -1) в точку (2n + 1, -1) следующим образом. Перенесём параллельно в начало координат путь, который состоит из фиксированного звена и следующего за ним участка пути Дика, включая добавленное звено. В конец полуГлава 14. Комбинаторика ченного пути перенесём начальный участок пути Дика от начала координат до фиксированного звена. Теперь фиксированное звено всегда ведёт в точку (1, -1), поэтому мы получаем путь из точки (1, -1) в точку (2n + 1, -1).

По этому пути мы можем восстановить исходный путь Дика. А именно, рассмотрим все нижние точки пути и выберем среди них крайнюю справа. Эта точка разбивает путь на два участка. Перенесём первый участок так, чтобы он заканчивался в точке (2n + 1, -1), а второй участок так, чтобы он начинался в точке (0, 0). В результате после отбрасывания последнего звена получим путь Дика: это очевидно для первого участка полученного пути и легко проверяется для второго. Если мы возьмём какую-нибудь другую нижнюю точку пути и попробуем применить ту же самую конструкцию, то для первого участка полученного пути требуемое свойство будет выполняться, а для второго нет.

2n Количество всех путей из точки (-1, 1) в точку (2n + 1, -1) равно.

n Действительно, из 2n звеньев мы должны выбрать n звеньев (1, 1). Каждому пути Дика соответствует ровно n + 1 таких путей, поэтому количество путей 1 2n Дика равно.

n + 1 n 14.43. а) Между такими последовательностями и путями Дика можно установить взаимно однозначное соответствие, сопоставив числу ai звено (1, ai).

б) Положим ai = 1, если у i-го человека в очереди 50 рублей, и ai = = -1, если 100. Кассир сможет всем дать сдачу тогда и только тогда, когда на каждом шаге количество полученных им 50-рублёвых купюр не меньше количества 100-рублёвых, т.е. a1 0, a1 + a2 0,..., a1 + a2 +... + a2n-1 (по условию a1 + a2 +... + a2n = 0). Таким образом, мы приходим к задаче а).

14.44. Первый и последний ходы ладьи определены однозначно. Поэтому можно рассматривать пути ладьи без первого и последнего хода. Взаимно однозначное соответствие между такими путями и путями Дика из 2(n - 2) звеньев устанавливается очевидным образом.

14.45. На рис. 14.3 показано, как плоскому бинарному дереву с одним корнем и n листьями можно сопоставить разбиение (n + 1)-угольника на треугольники и расстановку скобок для n букв. В многоугольнике выделяется одна сторона, которая соответствует корню. Остальные стороны соответствуют листьям.

14.46. а) Количество всех способов пометить n вершин (2n+1)-угольника 2n + единицами (а на остальные места поставить нули) равно. Число n 2n + 1 не делится на n, поэтому никакой набор пометок не может перейти сам в себя при повороте (2n + 1)-угольника. Количество поворотов (2n + + 1)-угольника, переводящих его в себя, равно 2n + 1. Поэтому количество 1 2n + различных наборов пометок равно.

2n + 1 n 178 Глава 14. Комбинаторика c b d a e Рис. 14.3.

б) Покажем, что существует взаимно однозначное соответствие между наборами пометок и расстановками n пар скобок для n + 1 букв. Сопоставим расстановке скобок последовательность из нулей и единиц, заменив каждую левую скобку единицей, а каждую букву нулём; правые скобки при этом игнорируются. Обратная операция для последовательностей определена не всегда, потому что расстановке скобок не может соответствовать последовательность, начинающаяся с нуля. Поэтому запишем полученную последовательность в вершинах правильного (2n + 1)-угольника по часовой стрелке.

Для такого набора пометок обратная операция определена однозначно. Действительно, нулей больше, чем единиц, поэтому обязательно найдётся тройка последовательных чисел 100. Для такой тройки расстановка скобок определена однозначно: правая скобка стоит сразу же за соответствующими двумя буквами. Выражение в скобках играет такую же роль, как буква. Поэтому последовательность 100 можно заменить на 0, перейдя к (2n - 1)-угольнику, и т.д.

14.47. Воспользовавшись формулой из задачи 14.18, получим 1 1 = · = xy 1 - x - y + 2xy (1 - x)(1 - y) 1 + (1 - x)(1 - y) (-1)kxkyk = = (1 - x)k+1(1 - y)k+k=Глава 14. Комбинаторика k + i k + j = (-1)k xk+iyk+j = k k i,j,k= p q = xpyq (-1)k.

k k p,q=0 k p q Значит, ap,q = (-1)k коэффициент при xp в выражении (1 + k k k + x)p(1- x)q. Нас интересует случай, когда p = 2n и q = 2n+ 2. В этом случае 2n (1 + x)p(1 - x)q = (1 - x2)2n(1 - x)2; коэффициент при x2n равен (-1)n + n 2n (2n)! n 1 2n + (-1)n-1 = (-1)n 1 - = (-1)n.

n - 1 n!n! n + 1 n + 1 n 14.48. О т в е т: 9. Числа 9 и 10 можно получить двумя разными способами:

9 = 3 + 6 = 4 + 5 и 10 = 4 + 6 = 5 + 5. Но нам необходимо учитывать порядок, в котором выпадают числа на костях. Поэтому число 9 получается четырьмя разными способами, а число 10 лишь тремя: 9 = 3 + 6 = 6 + 3 = 4 + 5 = 5 + 4, 10 = 4 + 6 = 6 + 4 = 5 + 5.

14.49. О т в е т: отец–мать–отец. (Такой ответ представляется на первый взгляд странным, потому что приходится дважды играть с сильным игроком.

Но при другом порядке матчей нужно обязательно выиграть единственный матч с сильным игроком, а не один из двух матчей.) Пусть вероятность выиграть матч у отца равна p, а у матери q. По условию p < q. Победу мальчику приносят следующие исходы турнира: ВВП, ВВВ, ПВВ (здесь В означает выигрыш, а П проигрыш). Для турнира отец– мать–отец вероятности таких исходов равны pq(1-p), pqp, (1-p)qp. Поэтому вероятность выигрыша в таком турнире равна 2pq - pqp. Аналогично вероятность выигрыша в турнире мать–отец–мать равна 2pq - qpq. Ясно, что pqp < qpq, поэтому 2pq - pqp > 2pq - qpq.

14.50. О т в е т: 7: 1. Пусть игроки сыграют ещё три партии, т.е. игра фиктивно продолжается даже после того, как первый игрок получил приз. Второй игрок получит приз тогда и только тогда, когда он выиграет все три партии.

Поскольку все 23 = 8 исходов этих трёх партий равновероятны, второй игрок получит приз с вероятностью 1/8. Соответственно, первый игрок получит приз с вероятностью 7/8.

14.51. а) О т в е т: 4. Пусть в ящике лежит m красных носков и n чёрных.

m Вероятность того, что первый выбранный носок красный, равна. При n + m условии, что первый выбранный носок красный, вероятность того, что второй m - выбранный носок тоже красный, равна. Поэтому вероятность того, n + m - m m - что оба носка красные, равна ·. Таким образом, требуется, n + m n + m - чтобы выполнялось равенство m m - 1 · =. (1) n + m n + m - 1 180 Глава 14. Комбинаторика При n = 1 получаем m = 3. Такой набор носков нам подходит.

б) О т в е т: 21. Ясно, что n > 0. Тогда, как легко проверить, m m - >. Поэтому должны выполняться неравенства n + m n + m - 2 1 m m - > >, n + m 2 n + m - т.е. ( 2 + 1)n < m < ( 2 + 1)n + 1. По условию число n чётно. Для n = 2, 4, получаем m = 5, 10, 15. В первых двух случаях равенство (1) не выполняется, а в третьем выполняется. При этом n + m = 6 + 15 = 21.

Замечание. Равенство (1) можно переписать в виде (2x - 1)2 - 2(2y)2 = 1, где x = m - n и y = n. Поэтому в общем случае мы имеем дело с уравнением Пелля.

14.52. О т в е т: да, могут. Пусть, например, на гранях костей написаны следующие числа:

на кости A 1,4,4,4,4,4;

на кости B 2,2,2,5,5,5;

на кости C 3,3,3,3,3,6.

B выигрывает у A, если на B выпадает 5 или на B выпадает 2, а на A 1 1 1 7 выпадает 1. Вероятность этого равна + · = >.

2 2 6 12 C выигрывает у B, если на C выпадает 6 или на C выпадает 3, а на B 1 5 1 7 выпадает 2. Вероятность этого равна + · = >.

6 6 2 12 A выигрывает у C, если на A выпадает 4, а на C выпадает 3. Вероятность 5 5 25 этого равна · = >.

6 6 36 Глава 15.

Рекуррентные последовательности Рекуррентной последовательностью порядка k называют последовательность чисел u1, u2,..., где числа u1, u2,..., uk произвольные, а при всех n 1 выполняется соотношение un+k = a1un+k-1 +... + akun, где a1, a2,..., ak некоторые фиксированные числа.

15.1. Общие свойства 15.1. Пусть a1, a2,..., ak фиксированные числа и un+k = = a1un+k-1 +... + akun. Докажите, что Pk-1(x) u1 + u2x + u3x2 + u4x3 +... =, 1 - a1x - a2x2 -... - akxk где Pk-1(x) многочлен степени не выше k - 1.

15.2. Пусть a1, a2,..., ak фиксированные числа и un+k = = a1un+k-1 +... + akun. Предположим, что x1,..., xk попарно различные корни уравнения xk = a1xk-1 + a2xk-2 +...+ ak. Докажите, что тогда un = c1xn-1 +... + ckxn-1 для некоторых фиксированных чисел 1 k c1,..., ck.

15.2. Числа Фибоначчи Числами Фибоначчи называют последовательность чисел F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2 при n 3. Начало этой последовательности 182 Глава 15. Рекуррентные последовательности имеет вид 1, 1, 2, 3, 5, 8, 13, 21,...

15.3. Докажите, что Fn+k = Fn-1Fk + FnFk+1.

15.4. а) Докажите, что числа Fn и Fn+1 взаимно просты.

б) Докажите, что НОД(Fm, Fn) = Fd, где d = НОД(m, n).

15.5. Докажите, что если m > 2, то Fn делится на Fm тогда и только тогда, когда n делится на m.

15.6. Докажите, что n n 1 1 + 5 1 - Fn = 2 (Бине).

15.7. Докажите, что для любого натурального n число n n n n + 5 + 25 + 125 +...

1 3 5 делится на 2n-1.

15.8. а) Рассмотрим последовательность многочленов f1(x) = 1, f2(x) = x, fn(x) = xfn-1(x) + fn-2(x) при n 3. Докажите, что n - 1 n - 2 n - fn+1(x) = xn + xn-2 + xn-4 + xn-6 +...

1 2 б) Докажите, что n - 1 n - 2 n - Fn+1 = 1 + + + +...

1 2 15.9. Докажите, что = F1 + F2x + F3x2 + F4x3 +...

1 - x - x15.10. Докажите, что для любого натурального числа n найдётся число Фибоначчи, делящееся на n.

15.11. Докажите, что сумма восьми последовательных чисел Фибоначчи не может быть равна числу Фибоначчи.

15.12. Докажите, что если a2 -ab-b2 = ±1, где a и b натуральные числа, то a = Fn+1 и b = Fn для некоторого n.

15.13. Найдите все решения в натуральных числах уравнения n n - 1 n n! =, где = биномиальный коэфm - 1 m m m!(n - m)! фициент.

Глава 15. Рекуррентные последовательности 15.14. а) Докажите, что F2n+1F2n-1 = F2n + 1.

2 б) Докажите, что F2n+1 + F2n-1 + 1 = 3F2n+1F2n-1.

15.15. При каких натуральных a и b число a2 + b2 + 1 делится на ab 15.16. Найдите все пары натуральных чисел a и b, для которых a2 + 1 делится на b, а b2 + 1 делится на a.

Pages:     | 1 |   ...   | 19 | 20 || 22 | 23 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.