В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 5
Текст из файла (страница 5)
Следовательно, что всего делителей ∏ (αi + 1). Далее, суммой всех делителей являетсяβββi=1∑βp1 1 · · · pβn n .(1.12)βi 6αii=1,nОчевидно, что эта сумма равнаn pαi +1 − 11 + p1 + · · · + pα1 1 · · · (1 + pn + · · · + pαn n ) = ∏ i,i=1 pi − 1(1.13)так как всякое слагаемое из (1.12) можно найти в (1.13) и наоборот.9.
Сколько можно составить перестановок из n элементов, в которых данные m элементов не стоят рядом в любомпорядке? Решение. Всего перестановок n!. Фиксированные m элементов можно поставить рядом m! способами. Оставшиеся элементы можно упорядочить (n − m)! различными способами. Разместить группу выделенных m элементов среди n элементов можно n − m + 1 способом. Таким образом, число искомых перестановок равноn! − m! (n − m + 1)!.10. Сколько существует чисел от 0 до 10n , в которые не входят две идущие друг за другом одинаковые цифры? Решение.
Рассмотрим k-разрядные числа, в которых никакие две подряд идущие цифры не повторяются. Найдем их количество. Первый разряд может быть произвольным из множества {1, 2, 3, 4, 5, 6, 7, 8, 9}. Второй разрядможет быть произвольным из этого же множества или нулем, но не равен первому и так далее. Таким образом,каждый разряд при построенном предыдущем принадлежит девятиэлементному множеству, то есть всего чиселдлины k, удовлетворяющих условию задачи 9n . Будем также считать число 0 состоящим их 0 разрядов. Поскольку искомые числа имеют в десятичной записи от 1 до n цифр (10n имеет n + 1 цифру, но не подходит при n > 2),всего чиселn9n+1 − 1∑ 9k = 8k=011.
Сколько существует n-значных натуральных чисел, у которых цифры расположены в неубывающем порядке? Решение. Каждому n-значному числу в десятичной системе счисления, у которого цифры расположены внеубывающем порядке, можно взаимно однозначно поставить в соответствие последовательность из нулей и единиц длины n + 9 следующим образом: числу 1| ·{z· · 1} · · · 9| ·{z· · 9} соответствует 1| ·{z· · 1} 0 1| ·{z· · 1} 0 · · · 0 1| ·{z· · 1}, то есть сначалаk1k9k1k2k9идет столько единиц, сколькими единицами начинается число, затем идет нуль, затем столько единиц, сколькодвоек, и так далее. Очевидно, что длина такой последовательности будет n+8, так как каждой из n цифр исходного14ГЛАВА 1.
КОМБИНАТОРИКАчисла соответствует одна единица, а разделителями выступают нули. Обратно, по каждой такой последовательности можно однозначно восстановить число: сначала пишем столько единиц, сколько единиц стоит перед первымнулем в последовательности, затем пропускаем нуль и пишем столько двоек, сколько стоит в последовательностимежду первым и вторым нулями и так далее. Итак, искомых чиселстолько же, сколько последовательностей изнулей и единиц длины n + 8, содержащих 8 нулей, то есть n+8.n12. Доказать свойство биномиальных коэффициентов nn−1n−1=+.kkk−1(1.14) Решение. Пусть n > 2, k > 1.
Тогда множество наборов длины n с k единицами распадается на два непересекающихся множества: заканчивающихся нулеми заканчивающихся единицей. Числонаборов длины n c k единиn−1цами, заканчивающихся нулем, равно n−1,азаканчивающихсяединицей.Таккакмощность объединенияkk−1двух непересекающихся множеств равна сумме их мощностей, свойство доказано.Все вышесказанное дает возможность рекуррентно определить биномиальные коэффициенты. Будем считать,что существует одна последовательность длины нуль, содержащая нуль единиц, и не существует ни одной последовательности той же длины, содержащей больше единиц.
Также, вполне естественно полагать, что существуетодна последовательность длины единица, содержащая нуль единиц, одна последовательность той же длины, содержащая одну единицу, и иных последовательностей той же длины не существует. Таким образом, биномиальныекоэффициенты могут быть определены следующей системой: 0= 1,0 n= 0,если n < 0 или k < 0,k nn−1n−1=+, иначеkkk−1или n= 1,n > 0,0 0= 0,k > 1, k n−1n−1n, n, k > 1.+=k−1kkНаглядно это можно представить на таблице:b kn b01234560111111110123456.........2001........3000........4000............5000....................................................n−1, n−1,k−1kn,kИногда бывает удобно представить в виде треугольника:1 ZZ11 Z ZZ Z121 Z ZZ ZZ Z1331 ZZ Z ZZ Z ZZ14641151.1.
ПРОСТЕЙШИЕ КОМБИНАТОРНЫЕ ЧИСЛАn13. Доказать равенство ∑k=1(−1)k−1 nkkn Решение. Обозначим ∗ = ∑k=1Z1 n∑ (−1)k−10 k=1= 1 + 12 + · · · + 1n .(−1)k−1 nkk .nРассмотрим функцию t ∑ (−1)k−1k=1n k−1k tи интеграл от нее: Z1Z1Z1n k−11 − (1 − t)n1 − tnt dt =dt =dt =1 + t + · · · + t n−1 dtkt1−t000=1t2t n 11t + +···+= 1+ +···+ .2n 02nС другой стороныZ1 n0 k−1 n k−1t dt =∑ (−1)kk=1 k 1n t ∑ (−1)k−1 k k = ∗.k=1n0Таким образом, равенство доказано.14. Доказать тождества:nn (a) ∑ 2k= ∑ 2k+1= 2n−1 .kk Решение. Это равенство отражает очевидный факт, что число наборов равной длины из нулей и единиц счетным числом единиц равно числу наборов из нулей и единиц с нечетным числом единиц и равно половинеполного числа наборов.(b) 4 ∑kn4k= 2n + 2n/2+1 cos πn4 .
Решение. Число в левой части равно учетверенному числу вершин n-мерного единичного куба, числоединиц в которых кратно четырем. Рассмотрим вспомогательную суммуS=1(1 + 1)n + (1 − 1)n + (1 + i)n + (1 − i)n .4Заметим, что4S = 2n + 2√ nnπnπn2 cos= 2n + 2 2 +1 cos .44Составим таблицу сумм степеней01231 −1i −i сумма111141 −1i −i011 −1 −101 −1 −ii0Получаемn4S = n n n n n−k kn n−kn n−k knk11+1(−1)+1i+∑ k∑ k∑ k∑ k 1n−k (−i)kk=0k=0k=0k=0 b 4n c n n−k knkkk=∑11 + (−1) + i + (−i) = 4 ∑.k4kk=0k=0n15.
При обследовании читательских вкусов студентов оказалось, что 60% студентов читают журнал A, 50% — журналB, 50% — журнал C, 30% — журналы A и B, 20% — журналы B и C, 40% — журналы A и C, 10% — журналы A, Bи C. Сколько процентов студентов:(a) не читает ни одного из журналов?16ГЛАВА 1. КОМБИНАТОРИКА Решение. Согласно принципу включения и исключенияN[0] = N(0) − N(1) + N(2) − N(3) =100% − (60% + 50% + 50%) + (30% + 20% + 40%) − 10% = 20%.(b) читает в точности 2 журнала? Решение.
Согласно принципу включения и исключения 23N[2] =N −N = 30% + 20% + 40% − 3 · 10% = 60%.2 (2)2 (3)(c) читает не менее 2 журналов? Решение. Согласно принципу включения и исключения 233N[2] + N[3] =N(2) −N(3) +N = 30% + 20% + 40% − 3 · 10% + 10% = 70%.223 (3)Упражнения.1. Имеется колода из 4n (n > 5) карт, которая содержит карты четырех мастей по n карт каждой масти, занумерованных числами 1, 2, . . .
, n. Подсчитать, сколькими способами можно выбрать пять карт так, что среди них окажутся:(a) три карты с одним номером и две карты с другим;(b) пять карт одной масти;(c) пять последовательно занумерованных карт;(d) три карты из пяти с одним и тем же номером;(e) не более двух карт каждой масти.2. Доказать следующие свойства биномиальных коэффициентов:n (a) nk = n−k; n(b) nk kr = n−rk−r r ;[k]rn n(c) k−rk = [n−k+r] ;rn(d)n(e)n−r nk−rk(f)(g)k= ∑ n−r−1k−r ;r=0=[k]r[n]r ;n+1 nn+1kk = n−k+1 ;nrn+1∑ k = k+1 .r=k3.
Доказать, что(a) nk возрастает по n при фиксированном k;(b) n−rk−r убывает по r при фиксированных n и k;(c) если n фиксировано, то nk возрастает по k при k 6 bn/2c и убывает при k > dn/2e;n (d) max nk = bn/2c;06k6n(e) минимальное значение суммыbn/sc , r = n − s bn/sc;n1 n2 ns k + k + ··· + ksпри условии ∑ ni = n равно (s − r)i=1qq+1r +r k ,где q =171.1.
ПРОСТЕЙШИЕ КОМБИНАТОРНЫЕ ЧИСЛА(f) максимальное значение суммыn∑j ;nnnk1 + k2 + · · · + ksпри условии 0 6 k1 < · · · < ks 6 n (1 6 s 6 n + 1) равноn−s 6 j< n+s22(g) при простом p и любом p > k > 1 число kp кратно p;2n(h)∏ pi 6 n , где произведение берется по всем простым числам pi (n < pi 6 2n).n<pi 62n4. Индукцией по n с использованием соотношения (1.14) доказать тождествоn n k(1 + t)n = ∑t .k=0 k(1.15)5. Пусть n и m — целые положительные числа. С использованием тождества (1.15) или иным способом доказатьследующие равенства:nnk(a) ∑k=0n= 2n ;(b) ∑ (−1)kk=0n(c) ∑ kk=1nnknk= 0;= n2n−1 ;(d) ∑ k (k − 1)nk= n (n − 1) 2n−2 ;(e) ∑ (2k + 1)nk= (n + 1) 2n ;k=2nk=0n(f) ∑1 nk+1 k=1n+11(g) ∑ (−1)k k+1nkk=0nk=0km m r k−r(h) ∑r=0n(i) ∑k=0nn2kn n−kk=0 r=0nnrr=knk+r(m) ∑r=0m(n) ∑k=n mr=2n2n ;=n n−kkr(l) ∑ (−1)k−rn−k1n+1 ;2nn ;=2(k) ∑ ∑=n+mk ;=(2n)!(k!)((n−k)!)2k=0(j) ∑2n+1 − 1 ;= 3n ;n−k= ∑ (−1)n−k−rr=0nr ;m+nn−k ; (−1)k−n nk mk(0 при m 6= n,=.1 при m = n.6.
Доказать тождества:m−1n= ∑ e−2πirν/m 1 + e2πiν/m , где i2 = −1;ν=0kπnn/2+12 +2cos 4 (n − 2r) , 0 6 r 6 3.(a) если 0 6 r < m, то m ∑(b) ∑kn 4k+r=14n mk+r7. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранныйязык. Десять человек знают английский, семеро — немецкий, шестеро — французский. Пятеро знают английскийи немецкий, четверо — английский и французский, трое — немецкий и французский.(a) Сколько человек знают все 3 языка?(b) Сколько человек знают ровно 2 языка?18ГЛАВА 1. КОМБИНАТОРИКА(c) Сколько человек знают только английский язык?8.(a) Показать, что количество целых положительных чисел, делящихся на n и не превосходящих x равно bx/nc.(b) Найти число целых положительных чисел, не превосходящих 1000, и не делящихся ни на одно из чисел 3, 5и 7.(c) Найти число целых положительных чисел, не превосходящих 1000, и не делящихся ни на одно из чисел 6, 10и 15.(d) Показать, что если n = 30m, то количество целых положительных чисел, не превосходящих n и не делящихсяни на одно из чисел 6, 10, 15, равно 22m.√(e) Пусть p1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
