Дискретно-непрерывная математика (стр. 35 )

Число таких слагаемых равно Сп(r1 ..., rk) - числу способов представления множества из п элементов {1,2, ..., п} в виде суммы k множеств В1, В2, ,,., Вk так, чтобы множество Bs имело rs элементов

(rs ≥0, r1 +...+ rk = п множество Bs — это множество тех і, для которых dі= as).

В п. 5.5 было показано, что

Следовательно,

При k = 2 равенство (5.11) имеет вид

Следовательно, мы получили формулу бинома Ньютона.

5.8.3. Биномиальные тождественности.

Числа Сkn имеют ряд важных свойств. Укажем некоторые из них и установим ряд интересных тождеств, которым удовлетворяют биномиальные коэффициенты.

Напомним в первую очередь следующие равенства:

Сkn =Сn-kn, (5.12)

Сkn+1 = Сkn + Сk-1n ', (5.13)

С0n + С1n + ... + Спп=2п, (5.14)

С0п – С1п + С2п – ... +(-1)n Спп = 0. (5.15)

Равенство (5.12) легко проверяется вычислением. Оно следует также из того, что число k-элементных подмножеств множества из п элементов равно числу (n —k)-элементных подмножеств. Равенство (5.13) мы доказали в п. 5.3.1. Равенство (5.14) получим, взяв в формуле бинома a = b = 1. Оно следует также из комбинаторных соображений, которые были проведены в п. 5.3.1. Если в формуле бинома Ньютона положить а = 1, b = — 1, получим равенство (5.15).

Иногда при доказательстве некоторых тождеств полезно иметь в виду геометрическую интерпретацию чисел Сkn, которая была приведена в п. 5.3.1.

Докажем еще несколько важных биномиальных тождеств.

Задача 1. Доказать, что

(5.16)

Доказательство 1. Рассмотрим все r-элементные подмножества множества

А = {а1,....., ап}.

Число их равно Сrп. Разобьем все эти подмножества на классы Т1,.,Tn-r+1 отнеся к классу Tk все те r-элементные подмножества множества А, в которых элемент с наименьшим индексом равен аk.

Поскольку каждое подмножество из класса Tk может быть получено присоединениям к аk некоторого (r—1)-элементного подмножества множества { аk+1, аk+2, .... an}, то класс Tk состоит из Сr-1n-k подмножеств. Следовательно, получаем равенство (5.16).

Доказательство 2. Рассмотрим все кратчайшие ламаные, которые соединяет точку (0; 0) с точкой (r; п - r).

Число всех таких ламаных равно Сrп. Отнесем к классу Bk те ламаные, которые пересекают прямую х = 1/2 в точке (1/2; k) (k = 0, ..., n— 1). Очевидно, класс Bk состоит из ломаных (рис. 5.6).

Рис. 5.6

Поэтому

Задача 2. Доказать, что

(5.17)

Доказательство 1. Все k-элементные подмножества множества

А = {а1 ..., ап, ап+1, ..., ап+т}

(число их равно Сk п+т) разобьем на k+1 класс V0, V1, ..., Vk, отнеся к классу Vі все те подмножества, в состав которых входит ровно i элементов с индексами, не большими чем п. Каждое подмножество из класса Vі можно получить, присоединяя к некоторому i-элементному подмножеству множества {а1, ..., an} (k — i)-элементное подмножество множества {ап+1, ..., ап+т}. Поэтому в состав Vi входит Сіп Сk-іт подмножеств. Следовательно,

Считая в (5.17) k = n = m, имеем тождество

(5.18)

которое уже было доказано с помощью геометрических соображений в п. 5.3.1 (задача 6).

Доказательство 2. Воспользуемся следующим замечанием: если два многочлена Р(х) и Q(x) равны при всех х, то коэффициенты этих многочленов при одинаковых степенях х равны. Действительно, если P(x)≡Q(x) и при некоторой степени х коэффициенты не равны, то многочлен Р(х)—Q(x) будет многочленом с ненулевыми коэффициентами, имеющим бесчисленное множество действительных корней, что противоречит основной теореме алгебры.

Запишем равенство

(1+x)n(1+x)m = (1+x)m+n. (5.19)

Используя формулу бинома Ньютона, убеждаемся, что коэффициент при xk в правой части равенства (5.19) равен Сkт+п, а

коэффициент при xk в левой части этого равенства имеет вид

Равенство (5.17) доказано.

Микромодуль16

Примеры решения типовых задач

Задача 1. Сколько четырехзначных чисел можно сложить из цифр 0, 1,2, 3, 4, 5, если:

а) ни одна из цифр не повторяется боле одного раза;

б) цифры могут повторяться;

в) числа должны быть нечетными (цифры могут повторяться)?

Решение. а) Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5 (0 не может быть первой цифрой, потому что в таком случае число не является четырехзначным); если первая цифра выбрана, то друга может быть выбранная 5 способами, третья - 4 способами, четвертая - 3 способами. Согласно правилу умножения общее число способов равно 5×5×4×3 = 300.

б) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5 (5 возможностей), для каждой из следующих цифр имеем 6 возможностей (0, 1, 2, 3, 4, 5). Следовательно, число искомых чисел равно 5×6×6×6=5×63=1080.

в) Первой цифрой может быть одна из цифр 1, 2, 3, 4, 5, а последней - одна из цифр 1, 3, 5 (числа должны быть нечетными). Следовательно, общее количество чисел равно 5×6×6×3 = 540.

Задача 2. Каждый студент группы - либо девушка, либо блондин, либо любит математику. В группе 20 девушек, из них 12 блондинок, и одна блондинка любит математику. Всего в группе 24 студента-блондина, математику из них любят 12, а всего студентов (ребят и девушек), которые любят математику, 17, из них 6 девушек. Сколько студентов в данной группе?

Решение. Если А - множество девушек, В - блондинов, С — студентов, которые любят математику, то N(A В С) - искомое число. А В — множество блондинок, А С — множество девушек, которые любят математику, В С — множество всех блондинов (ребят и девушек), которые любят математику, А В С — множество блондинок, которые любят математику. Тогда

Задача 3. В турнире принимали участие п шахматистов, и каждые 2 шахматиста встретились 1 раз. Сколько партий было сыграно в турнире?

Решение. Партий было сыграно столько, сколько можно выделить

2-элементных подмножеств в множестве из п элементов, т. е.

Задача 4. В скольких точках пересекаются диагонали выпуклого

n-угольника, если никакие 3 из них не пересекаются в одной точке?

Решение. Каждой точке пересечения двух диагоналей соответствует 4 вершины n-угольника, а каждым 4 вершинам n-угольника соответствует 1 точка пересечения (точка пересечения диагоналей четырехугольника с вершинами в данных 4 точках). Поэтому число всех точек пересечения равно числу способов, которыми среди п вершин можно выбрать 4 вершины

Задача 5. Сколько можно составить перестановок из п элементов, в которых данные 2 элемента не стоят рядом?

Решение. Определим число перестановок, в которых данные 2 элемента а и b стоят рядом. Могут быть следующие случаи: а стоит на первом месте, а стоит на втором месте, ..., а стоит на (п—1)-в месте, а b стоит правее а; число таких случаев равно п— 1. Кроме того, а и b можно поменять местами, и, следовательно, существует 2(п—1) способов размещения а и b рядом. Каждому из этих способов соответствует (п — 2)! перестановок других элементов. Следовательно, число перестановок, в которых а и b стоят рядом, равно 2• (п — 1) • (п — 2)! = 2• (п - 1)!. Поэтому искомое число перестановок равно

п! - 2• (п - 1)! = (п - 1)! • (п - 2).

Задача 6. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить лруг друга?

Решение. При указанном расположении ладей на каждой вертикали и каждой горизонтали стоит лишь одна ладья. Рассмотрим одно из таких расположений ладей. Пусть a1 — номер вертикали, в которой стоит ладья из первой горизонтали, а2 — номер вертикали, в которой стоит ладья из второй горизонтали, .... а8 — номер вертикали, в которой стоит ладья из последней, восьмой, горизонтали. Тогда (а1 ..., а8) есть некоторая перестановка чисел 1, .... 8. Среди чисел а1, .... а8 нет ни одной пары равных, иначе 2 ладьи попали бы в одну вертикаль. Следовательно, каждому расположению ладей соответствует определенная перестановка чисел 1, ..., 8. Наоборот, каждой перестановке чисел 1, ..., 8 соответствует такое расположение ладей, при котором они не бьют друг друга. Следовательно, число искомых расположений ладей равно Р8 = 8! = 40 320.