1. Комбинаторика. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел (Слайды к лекциям), страница 3

билеты равноценны, то порядок в выборке не важен.Значит, число возможных способов распределений билетовравно числу сочетаний с повторениями из 20 по 3, т.е.33 = (22)3 = 22·21·20 = 22 · 7 · 10 = 1540.C20+3−1= C223!6Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадБиномиальные коэффициентыНапомним, что биномиальный коэффициент Cnk равен числусочетаний из n по k.Мы знаем, что Cnk =Отсюда получаем(n)kk! .(n)k(n)k · (n − k)!n!==.k!k! · (n − k)!k!(n − k)!Следовательно,Свойство. Для всех 0 ≤ k ≤ n верно Cnk = Cnn−k .Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадПоследовательности биномиальных коэффициентовТеорема 8. При каждом n ≥ 1 (конечная) последовательностьбиномиальных коэффициентов Cnr , где r = 0, 1, .

. . , n,n−1возрастает, если r < n−12 , и убывает, если r > 2 .Доказательство. Рассмотрим отношениеCnr +1Cnr ,0 ≤ r ≤ n − 1:Cnr +1n!n!n−r=:=.Cnr(r + 1)!(n − r − 1)! r !(n − r )!r +1Определим, когда это отношение больше единицы:n−rn−1> 1, если r <.r +12Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадПоследовательности биномиальных коэффициентовДоказательство (продолжение). Получаем, чтопри r < n−12 последовательность возрастает,n−1при r > 2 последовательность убывает.Пример.Пусть n = 3. Тогда последовательность такова: 1, 3, 3, 1.Пусть n = 4.

Тогда последовательность такова: 1, 4, 6, 4, 1.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадМаксимальные значенияСледствие 8.1. При четных значениях n максимальноезначение среди биномиальных коэффициентов Cnr ,r = 0, 1, . . . , n, достигается только при r = n2 ;при нечетных значениях n максимальное значение средибиномиальных коэффициентов Cnr , r = 0, 1, .

. . , n, достигаетсяn+1при r = n−12 и при r = 2 .Доказательство. По теореме если n ≥ 1, тоrпри r < n−12 последовательность Cn , r = 0, 1, . . . , n, возрастаетn−1и при r > 2 последовательность Cnr , r = 0, 1, . . . , n, убывает.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадМаксимальные значенияДоказательство.

Если значение n четно, то число n−12нецелое; поэтому максимальное значение достигается приnr = b n−12 c + 1 = 2;если значение n нечетно, то числоn−12n+12n−12целое; следовательно,Cn = Cn , и максимальное значение достигается приn+1r = n−12 и при r = 2 .bncСледствие 8.2.

Для всех n ≥ 1 и 0 ≤ r ≤ n верно Cnr ≤ Cn 2 .Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадСуммы биномиальных коэффициентовНапомним формулу бинома Ньютона:nPCnk x k y n−k .При n ≥ 1 верно (x + y )n =k=0Из нее следуют два свойства сумм биномиальныхкоэффициентов:Теорема 9. Для всех n ≥ 1 верноnP1.Cnk = 2n .2.k=0nP(−1)k Cnk = 0.k=0Доказательство.nP1. (1 + 1)n =Cnk = 2n .k=02. ((−1) + 1)n =nPk=0Cnk (−1)k = 0.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадОценки биномиальных коэффициентовИногда нужно знать оценки биномиальных коэффициентов илиих сумм.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадОценка биномиального коэффициентаТеорема 10.

Для всех n ≥ 1, 0 ≤ k ≤ n, верно Cnk ≤nnk k (n−k)n−k(по определению полагаем, что 00 = 1).Доказательство. Сначала заметим, что для всех n ≥ 1 верноnCn0 = 1 ≤ nnn·00 = 1, т.е. при k = 0 утверждение теоремы верно.Доказательство для n ≥ 1 при всех k, 1 ≤ k ≤ n проведеминдукцией по значению n.Базис индукции. Если n = 1, то Cn1 = 1 ≤1100 ·11= 1.Индуктивный переход. Предположим, что для некоторого n ≥ 1при всех k, 1 ≤ k ≤ n, утверждение теоремы верно.k=Рассмотрим n + 1.

Тогда Cn+1=(n + 1)!n+1n!n+1=·=· Cnk−1 .k!(n − k + 1)!k(k − 1)!(n − k + 1)!kВыборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадОценка биномиального коэффициентаДоказательство (продолжение). Воспользуемсяnnпредположением индукции, что Cnk−1 ≤ (k−1)k−1 (n−k+1)n−k+1 , ипроведем рассуждения:n + 1 k−1 n + 1nn(n + 1)n k k·Cn ≤··=·kk (k − 1)k−1 (n − k + 1)n−k+1 (n + 1)n k k(n + 1)n+1k k−1nn··=k k (n − k + 1)n−k+1 (n + 1)n (k − 1)k−1k−111+n+1k−1(n + 1)(n + 1)n+1= k·≤.nk (n − k + 1)n−k+1k k (n − k + 1)n−k+11 + n1=В завершающем переходе мы воспользовалисьтем, что1 nпоследовательность an = 1 + n возрастает.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадОценка суммы биномиальных коэффициентовТеорема 11.

При n ≥ 1 и 0 < k < b n2 c верно двойноенеравенствоkXn−k kkCn <Cnr <C .n − 2k nr =0Доказательство. Левое неравенство очевидно. ДокажемkPправое неравенство. Пусть k < b n2 c. Рассмотрим суммуCnr .r =0Сначала заметим, что для произвольного r , такого что0 ≤ r < k, верноCnrn!k!(n − k)!·==r !(n − r )!n!Cnk(k)k−rk · (k − 1) · · · · · (r + 1)==≤(n − r )k−r(n − r ) · (n − r − 1) · · · · · (n − k + 1)kn−kk−r.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадОценка суммы биномиальных коэффициентовДоказательство (продолжение). Т.к. k < b n2 c, верноТогдаkXr =0kXCnrrkCn = Cn≤ CnkCnk1+r =0kn−k+kn−kkn−k< 1.!2....В больших скобках стоит сумма бесконечно убывающейkгеометрической прогрессии со знаменателем n−k< 1.

Найдемее:1n−k=.kn − 2k1 − n−kОтсюда получаем оценку:kXr =0Cnr ≤n−k· Cnk .n − 2kВыборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадОценка суммы биномиальных коэффициентовСледствие 11.1. При n ≥ 1 и k >nXr =kCnr <n2верно неравенствоkCk.2k − n nДоказательство. По теореме и свойству Cnr = Cnn−r получаемnXr =kCnr =n−kXs=0Cns <n − (n − k) n−kkC=Ck.n − 2(n − k) n2k − n nВыборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадОценки сумм биномиальных коэффициентовМожно доказать следующие оценки сумм биномиальныхкоэффициентов.Теорема 12.

1. Пусть n ≥ 1, и k < b n2 c. ТогдаkXCnr <r =0nn.k k (n − k)n−k2. Пусть n ≥ 1, и k > n2 . ТогдаnXr =kCnr <nn.k k (n − k)n−kВыборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадАсимптотические оценкиПри решении задач довольно часто необходимо знатьасимптотическое поведение биномиальных коэффициентов иих сумм.Обычно находят асимтотику или порядок комбинаторныхчисел.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадO-символикаНапомним некоторые определения из математическогоанализа. Мы будем изучать поведение неотрицательныхфункций натурального аргумента n при n → ∞.Пишут ϕ(n) = O(ψ(n)), если существует такая положительнаяконстанта C , что ϕ(n) ≤ C · ψ(n).Если одновременно выполняются условия ϕ(n) = O(ψ(n)) иψ(n) = O(ϕ(n)), то говорят, что функции ϕ(n) и ψ(n) имеютодинаковый порядок (равны по порядку), и пишутϕ(n) ψ(n).Пишут ϕ(n) = o(ψ(n)), если существует такая функция χ(n),χ(n) → 0 при n → ∞, что ϕ(n) = χ(n) · ψ(n).Говорят, что функции ϕ(n) и ψ(n) эквивалентны(асимптотически равны), и пишут ϕ(n) ∼ ψ(n), еслиϕ(n) = ψ(n) + o(ψ(n)).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадАсимптотика биномиальных коэффициентов√При помощи формулы Стирлинга n! ∼ 2πnnn e −n , где eобозначает основание натурального логарифма (e = 2, 71 .

. . ),можно доказать следующие теоремы.Теорема 13. При k → ∞ и (n − k) → ∞ верно√nnnkCn ∼ p· k.2πk(n − k) k (n − k)n−kСледствие 13.1. При n → ∞ для четных значений n верноrn2 2n2·√ .Cn ∼πnВыборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадАсимптотика сумм биномиальных коэффициентов√Теорема 14. При n → ∞ если ϕ(n) → ∞, и ϕ(n) n = o(n), то√b 2n +ϕ(n) ncX√r =b 2n −ϕ(n) ncCnr ∼ 2n .Доказательство. Пусть k < b n2 c.

ТогдаkXr =0Cnr ≤n−k kC .n − 2k nВыборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадАсимптотика сумм биномиальных коэффициентовДоказательство (продолжение). Мы знаем, чтоCnk = Cnn−k для всех k,Cnk ≤ Cnr при k ≤ r ≤ b n2 c.Рассмотрим произведение Cnk · (n − 2k) и получим оценки:Cnk · (n − 2k) = Cnk + · · · + Cnk ≤|{z}n−2kbnc≤ Cnk + Cnk+1 + · · · + Cn 2 + · · · + Cnn−k ≤|{z}n−2k+1nXCnr = 2n .r =0Значит, нашли оценку:kXr =0Cnr ≤n−kn − k k n − 2kC ·≤ 2n ·.n − 2k n n − 2k(n − 2k)2Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадАсимптотика сумм биномиальных коэффициентовДоказательство (продолжение). Пусть теперь ϕ(n) → ∞,√√ϕ(n) n = o(n), и k = b n2 − ϕ(n) nc.Тогда√n − b n2 − ϕ(n) nc√≤≤2 ·(n − 2b n2 − ϕ(n) nc)2r =0√n − n2 + ϕ(n) n + 1n√≤2 ·=(n − 2 n2 + 2ϕ(n) n)2√n1n 2 + ϕ(n) n + 1=2 ·≤ 2n ·= o(2n ) при n → ∞,24ϕ (n)nC ϕ2 (n)где C , C > 0, некоторая постоянная величина.kXCnrnПо свойству биномиальных коэффициентов заключаем, чтоnPCnk = o(2n ).r =n−kТеорема 14 доказана.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЛитература к лекции1.

Яблонский С.В. Введение в дискретную математику. М.:Высшая школа, 2001. Ч. II.2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения подискретной математике. М.: Физматлит, 2004. Гл. VIII.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадКонец лекции.