А.Я.ХАЛАМАЙЗЕР
о о
о

А. Я. ХАЛАМАЙЗЕР
КОМБИНАТОРИКА
И БИНОМ НЬЮТОНА
ПОСОБИЕ ДЛЯ УЧАЩИХСЯ 9—10 КЛАССОВ
ϋ
МОСКВА «ПРОСВЕЩЕНИЕ» 1980

22.141
X17
СОДЕРЖАНИЕ
Введение
1. Волейболисты меняются
местами
2. Проверка гипотез
3. Четырехбуквенные «слова»
4. Упорядоченные и
неупорядоченные подмножества
5 Два состава из общего спи-
ска
6. Выбор делегации
7. Три вида соединений
8. Баскетболисты тренируются в
зале
9. Треугольник Паскаля
4
7
8
10
12
14
16
18
10. Коэффициенты многочлена 18
11. Биномиальная формула 19
12. Решение задач 20
13. Некоторые приближенные
формулы 21
14. Наташа нанизывает бусы 22
15. Сережа штампует номера 23
16. В государственном совете
Швамбрании 24
17. Азбука Морзе 26
18. Из истории комбинаторики 28
Ответы и указания 31
Литература для дополнительного
чтения 32
Халамайзер А. Я.
Х17 Комбинаторика и бином Ньютона: Пособие пря
учащихся 9—10 кл.— М.: Просвещение, 1980.—
32 с, ил.
В брошюре посредством задач раскрывается содержание
основных понятии комбинаторики. Предназначена для учащихся старших
классов.
60601—183 ББК 22.141
х „„,^ лл 263—80 4306020400
103(03)—80 ·, 512
© Издательство «Просвещение», 1980 г.

ВВЕДЕНИЕ
В Большой советской энциклопедии говорится, что
комбинаторика — это раздел математики, в котором изучаются
некоторые операции над конечными множествами, т. е. над
определенным числом предметов (или точнее, объектов). Сами эти
объекты называются элементами множества. Основными и
типичными операциями и связанными с ними задачами
комбинаторики являются следующие:
1) Образование упорядоченных множеств, состоящее в
установлении определенного порядка следования элементов
множества друг за другом,— составление перестановок.
2) Образование подмножеств, состоящее в выделении из
данного множества некоторой части его элементов,—
составление сочетаний.
3) Образование упорядоченных подмножеств — составление
размещений.
В учебной и научной литературе элементы комбинаторики
включаются обычно в виде отдельной главы в курс алгебры.
Понимание проблем комбинаторики, умение подсчитывать число
различных возможностей, связанных с упорядочением множеств
и выделением из них подмножеств (как упорядоченных, так и
неупорядоченных), является весьма важным для правильного
восприятия статистических закономерностей, проявляющихся
в природе и технике, для восприятия законов природы, носящих
вероятностный характер, и в конечном итоге Для формирования
личности сознательного строителя коммунистического общества.
Поэтому настоящее пособие представляется полезным как
для самостоятельного чтения любознательными
старшеклассниками, так и для использования на факультативных и кружковых
занятиях. Упражнения, приводимые для самостоятельного
решения в конце каждого раздела, помогут учителю уяснить
детали. Выполнение их поможет сознательному усвоению темы.
Автор не считает целесообразным при первоначальном
знакомстве с предметом излагать строгие доказательства вводимых
правил и формул. Предполагается, что «правдоподобные
рассуждения»^ аналогии, приводящие как бу к самостоятельному
выводу нужных предложений, являются достаточно
убедительными и будут легче восприняты читателем. Вполне строгие
доказательства (если они вообще окажутся необходимыми) лучше
отложить на следующий этап изучения.
Автор

1. ВОЛЕЙБОЛИСТЫ МЕНЯЮТСЯ МЕСТАМИ
Тренер волейбольной команды решил изменить расположение
игроков.
— Следующую встречу будем начинать по-другому,—
объявил он после очередного проигрыша.— Ты, Сергей, встанешь на
подачу; Володя — на четвертый номер, в нападение, а ты,
Николай...
— А если опять проиграем? — спросил капитан.
— Тогда опять переставлю,— хладнокровно ответил
тренер.— Пока не перепробуем всех возможных расположений.
— Долговато пробовать будем,— усмехнулся Сергей,
который был не только перворазрядником, но и
инженером-расчетчиком в конструкторском бюро.—г Ты даже не представляешь
себе, сколько игр пройдет, пока все способы перепробуем...
Как же подсчитать, сколькими способами можно расставить
6 волейболистов на 6 различных мест? И сколько потребуется
времени, если, например, каждый месяц пробовать 10 различных
способов?
Представьте себе две геометрические фигуры: квадрат и
треугольник. Если говорить о порядке их расположения, то можно
найти два способа: сначала квадрат, потом треугольник (рис. 1, а)
или сначала треугольник, а потом квадрат (рис. 1,6).
Точно так же из двух букв А и Б можно составить два двух-
буквенных «слова» АБ и БА. Вообще, множество из двух
элементов можно расположить (упорядочить) ровно двумя
способами.
Третий элемент (букву) В можно поместить впереди пары —
получим «слово» из трех букв ВАБ; можно поместить посреди
пары — получим АВБ; можно поместить позади пары —
получим АБВ. Точно так же из пары БА можно получить ВБА, БВА
и БаВ. Значит, для трех элементов существует 2· 3=6 способов
расположения по порядку; из
трех элементов можно
составить 6 «перестановок» —
комбинаций, отличающихся друг Г 1
от друга порядком расположен I I
ния элементов. Или иначе: мно- 1 I
жество, содержащее 3 элемен- а) 6)
та, можно упорядочить шестью
различными способами. Рис. 1
Δ Δ
4

Установленный в конечном множестве порядок расположения
его элементов называется перестановкой.
Число перестановок обозначается латинской буквой Р.
Значит,
Р2=2; Р3=2-3=6.
Символ Р3 читается так: «Число перестановок из трех
элементов».
Пусть теперь у нас имеется k предметов (элементов), из
которых составлены всевозможные Рь, перестановок. Возьмем одну
из них:
&и а>2\ Яз; · · ·; я*.
Добавим еще один (/Н-1)-й элемент. Его можно поместить:
1) впереди первого элемента αϊ;
2) впереди второго элемента а2;
3) впереди третьего элемента а3;
k) впереди k-το элемента ан\
/Н-1) позади всех имеющихся k элементов, т. е. всего
£+1 способом. Значит, количество перестановок из £+1
элементов в (&+1) раз больше, чем число перестановок из k
элементов, т. е.
Ρ*+ι = Ρ*.(Λ+1).
Заметим, что Р2 и Р3 вычислены нами непосредственно;
продолжим наши рассуждения, добавляя для симметрии
множитель 1:
Р2=Ь2=2;
Р3 = Ь2.3=6;
Р4=Ь2-3.4=24;
Р5=Ь2.3-4.5=120;
ΡΛ=1·2·3· ... ·£;
ΡΛ+1=1·2·3. ... ·£.(Μ-1),
Замечание. Произведение натуральных чисел от 1 до
данного натурального числа m называется факториалом числа m
и обозначается т!
Например: Р2= 1-2 = 2!
РБ=Ь2-3.4.5=5!
ΡΛ = 1.2·3. . . . -k = k\ (1)
Итак, из k элементов можно составить РЛ=Ь2· ... -k = k\
различных перестановок, или, иначе, k\ различных
упорядоченных множеств.
Подсчитаем теперь число перестановок из 6 элементов
(столькими способами можно расставить на площадке 6
волейболистов) ;
Ρ6=1.2·3·4·5·6=720.
Б

Согласно условию тренер может
пробовать 10 различных способов
расстановки волейболистов в месяц.
Значит, на проверку всех способов
уйдет 72 месяца, или 6 лет.
Если считать различными
только те расстановки, при которых
меняется порядок следования
волейболистов, то разных порядков
следования окажется только (6—1)1 =
= 120; в этом случае на проверку
всех способов расстановки тренеру
достаточно будет одного года.
Вообще, когда важен только порядок
следования элементов (начальный элемент безразличен), то для
упорядочения множества из k элементов существует (k— 1)!
способов.
Изменение расположения элементов, не меняющее порядка
их следования (первый элемент «следует» за последним),
иногда называют циклической перестановкой. Так, например, слово
«осел» циклической перестановкой может быть преобразовано
в «село». Другой пример циклических перестановок изображен
на рисунке 2.
Факториал иногда рассматривают как функцию,
определенную на множестве натуральных чисел. В таблице 1 приведены
значения факториала для небольших значений п. Для больших η
вычисление факториала оказывается затруднительным; однако
приближенное значение можно вычислить с хорошей точностью
по формуле Стйрлинга:
П{~ ("7)Я -"^ (*«2,718...)\
Таблица 1
я
1
2
з
4
5
6
7
8
9
10
til
1
2
6
24
120
720
5040
40320
362 880
3 628 800
η
Π
12
13
14
15
16
17
18
• 19
20
η!
39 916800
479 001600
. 6 227 020 800
87 178 291200
1 307 674 368 000
20 922 789 888 000
355 687 428 096 000
6 402 373 705 728 000
121645 100 408 832 000
2 432 902 008 176 640 000
б

2. ПРОВЕРКА ГИПОТЕЗ
При нахождении количества различных перестановок (или
числа перестановок) мы воспользовались принципом
математической индукции. Для этого пришлось:
а) непосредственно подсчитать число перестановок из двух
(или трех) элементов;
б) подметить закономерность изменения числа перестановок
при добавлении еще одного элемента (при увеличении числа
элементов на единицу); сформулировать гипотезу1;
в) доказать эту гипотезу.
Рассмотрим еще один пример применения математической
индукции. Пусть требуется найти сумму дробей следующего
вида:
с Ϊ 1 1 1
Ь2 2-3 ' 3-4 ' ' k(k+l)
Выпишем суммы для одного, двух, трех, четырех
слагаемых:
1 1
Si*
1-2 2 '
S2= —— +
2 12 ^
5з= -А- + -
54= —1— +
1 2
2-3 3 '
1 ■ 1 _ 3 .
2-3. "*" 3-4 4 *
_J_ + _1_+_L·
2-3 3-4 4-5
4
5 *
Ь2
А
Ь2
Нетрудно подметить закономерность: каждая из этих сумм —
дробь, числитель которой равен числу слагаемых, а
знаменатель— на одну единицу больше; значит, суммы имеют вид:
k
Предположим, что для k слагаемых выполняется равенство
5л= —г-т—I—7ΓΖ—Ь..*+
Ь2 2-3 k(k+l) k+l
и докажем, что в этом случае равенство выполняется и для
(β+l) слагаемых, т. е.
1-2 2-3 k(k+l) (k+l)(k+2) k+2
1 Гипотезой называется предположение, объясняющее какую-либо
закономерность; проверка или доказательство гипотезы — рассуждение, в
результате которого гипотеза - становится законом (правилом, формулой) или
отвергается как ошибочная. Одной из форм доказательства гипотез является
применение математической индукции.
7

Для доказательства достаточно заменить первые k дробей
их суммой (исходя из подмеченной закономерности) и сделать
упрощения. Рекомендуем читателю самостоятельно проделать
необходимые действия.
Иногда закономерность (гипотеза) предполагается заранее
и дается в готовом виде; это несколько облегчает задачу.
Проверьте следующие гипотезы:
1+3+5+7+, ... +(2£-1) =£2.
1.
2.
3.
4.
5.
6.
7.
12+22+32+ ... [+&= Н*+1Н2*+1) ^
6
ЬЗ^З.5^5.7^···^
1
Вычислите: а)
(2k— 1). (2*+1) k+\
81
6!
7!
Найдите сумму цифр во всех пятизначных числах,
составленных из цифр 1, 4, 6, 7, 8 (без повторений).
Сколько различных пятизначных чисел можно составить
из цифр 2, 4, 6, 8, 0 (без повторений)?
Найдите сумму всех пятизначных чисел из упражнения 5.
3. ЧЕТЫРЕХБУКВЕННЫЕ «СЛОВА»
Тридцать букв русского алфавита изображены на карточках
(рис. 3) без повторений. Сколько различных четырехбуквенных
«слов» можно из них составить? 1
Для решения задачи подготовим «наборную доску» для
четырехбуквенного «слова» (рис. 4). Очевидно, первую букву
можно выбрать 30 способами: каждая из 30 имеющихся картси
чек может быть уложена в первую клетку. Вторая буква
выбирается из оставшихся 29 букв: буква, которая заняла первое
место, не может быть использована вторично. Таким образом,
с буквы А начинается 29 двухбуквенных «слов», с буквы Б —
тоже 29..., с буквы Я —тоже 29, от ЯА до ЯЮ. Всего получится
30-29 двухбуквенных «слов».
ι I
Б
В
ЬукЬы; 1-Я 2-Я 3-Я 4-Я
Рис. 3
Рис. 4
1 Разумеется, многие «слова», например «ФРЦХ», не будут иметь
смыслового значения. Но мы хотим подсчитать все «слова». Отметим еще, что
слово «МИША» мы из этих букв составить можем, а слово «МАША»—не
можем, так как по условию буквы не должны повторяться.
8

Продолжая рассуждение, заметим, что третью букву можно
выбрать 28 способами (так как две буквы уже заняли первое и
второе места); значит, получим 30-29-28 трехбуквенных и
30-29-28-27=657 720 четырехбуквенных «слов». Вот некоторые
из них:
КРАН БРАК
КРАБ ФРАК
Первые два из этих «слов» отличаются выбором одной
буквы; второе и третье состоят из одних и тех же букв, но
отличаются порядком их расположения; третье и четвертое
отличаются выбором одной буквы. Вообще, различные слова могут
отличаться друг от друга либо выбором букв, либо порядком их
расположения.
Наши четырехбуквенные «слова» представляют собой четы-
рехэлементные упорядоченные подмножества, входящие в
множество из 30 элементов — букв русского алфавита.
Упорядоченные подмножества данного конечного множества называются
размещениями.
Как видно, различные размещения (в нашей задаче — по
4 элемента из 30) отличаются друг от друга либо выбором
элементов, либо порядком их расположения. Количество
размещений (или число размещений) обозначается буквой А с
соответствующими индексами. Следовательно, число размещений из
30 элементов по 4: Α304=30·29·28·27.
8. Сформулируйте правило: как найти число размещений из m
элементов по η (естественно, что п^.гп)—и напишите
соответствующую формулу.
9. Вычислите: а) А\0; б) А\2 ; в) А\.
10· Сколько различных четырехзначных чисел можно составить
из цифр: а) 2, 3, 4, 5; б) 2, 3, 4, 5, 6; в) 2, 3, 4, 5, 6, 7; г) 2,
3, 4, 5, 6, 7, 0?
Для записи числа размещений иногда удобно использовать
факториалы, например
Л* =30-29.28.27= 30-29-28-27-(26-25. ... -3-2-1) =ЗШ
зо 12-3- ... -25-26 26!
или в общем виде
т\
д" =m(m-l)-(m-2).(m-3). ... .(m-n+l)= ——-. (2)
П. Вычислите: а) 0 ; б) -±~ , где п<10.
12. Решите уравнения: а) А2Х=90; б) Л2 =42; в) Αχ =56*,
9

4. УПОРЯДОЧЕННЫЕ И НЕУПОРЯДОЧЕННЫЕ
ПОДМНОЖЕСТВА
Сколько различных трехзначных чисел можно составить
из цифр 1, 2, 3, 4, 5, 7 (без повторений)?
Решение. Сгруппируем (столбцами) числа, записанные
одними и теми же цифрами:
123
231
312
132
213
321
В каждом столбце ровно 6 различных трехзначных чисел,
составленных из одних и тех же цифр, но в различном порядке
(объясните, почему именно 6). Эти трехзначные числа
отличаются друг от друга либо выбором цифр в различных столбцах,
либо порядком их расположения в одном и том же столбце. Как
уже известно, такие соединения называются размещениями;
значит, для ответа на вопрос задачи нужно найти число
размещений из 7 элементов по 3:
Α] =7·6·5=210.
Сколько различных произведений по 3 сомножителя можно
составить, используя те же *цифры в качестве множителей?
Решение. Воспользуемся написанными выше столбцами.
Одно'из возможных произведений будет 1·2·3; все другие
произведения, записанные по образцу этого же столбца (2-3-1
и т. д.) отличаются только порядком множителей и,
следовательно, не являются различными произведениями х. Различных
же произведений будет лишь столько, сколько выше было
столбцов, т. е. во столько раз меньше, чем различных
трехзначных чисел, сколькими способами можно переставлять эти три
цифры. Значит, ответ на вопрос получается делением:
л3 η Α7 7·6·5
А на Р31 т. е. _L = =
Различные произведения, о которых шла речь в этой задаче,
представляют собой различные трехэлементные неупорядоченные
подмножества, входящие в множество из семи элементов: I, 2,
3, 4, 5, 7, 9.
1 Если бы в этом примере в качестве сомножителей были и числа б и 8,
то разные сомножители могли бы дать одно и то же произведение
(например, I-8=2-4; 2-6=3-4 и т. д.), так что подсчет числа различных
произведений был бы сложнее.
124 ... 579
241 795
412
10

Произвольные неупорядоченные подмножества данного мно~
жества называются сочетаниями. Различные сочетания
отличаются друг от друга только составом (выбором) элементов.
Количество сочетаний (или число сочетаний) обозначается
латинской буквой С с соответствующими индексами.
Возвращаясь к предыдущему примеру, получим, что число сочетаний
из 7 элементов по 3:
Р3 1-2-3
В классе 10 юношей-допризывников. Сколькими способами
они могут избрать четверых для участия в слете ДОСААФ?
Решение. Порядок, в котором будут избраны 4 делегата
на слет, безразличен. Значит, речь идет о сочетаниях из 10
элементов по 4:
123-4
13. Сформулируйте правило: как найти число сочетаний из пг
элементов по η (n^tn)—и напишите соответствующую
формулу.
14. Вычислите: а) С£; б) С*; в) С|.
15. Решите уравнения: а) С2Х=21; б) 5С^=С^.+2;
в) Ci+CJ=15 (*-l); г) С^+С]^ -15(0-2).
16. В некотором коллективе 20 комсомольцев. Сколькими
способами можно выбрать из них трех членов комитета?
17. Агрохимик проверяет 6 типов минеральных удобрений; ему
нужно провести несколько опытов по изучению
совместного влияния любой тройки удобрений. Для каждого
опыта берется участок 0,25 га. На какой площади проводится
все исследование?
18. На окружности отмечено 8 различных точек, а) Сколько
хорд можно провести, соединяя любые 2 из этих точек?
* б) Сколько различных треугольников с вершинами в
данных точках можно построить? в) Сколько выпуклых
четырехугольников с вершинами в этих точках можно
построить? г) Сколько невыпуклых четырехугольников?
19. Очевидно, что Cj? = Cj?. Проверьте также равенстваС\2 = С*2;
СЦ=С ^.Сформулируйте аналогичное свойство в общем
виде.
^ ■ ι ι I ■
1 Иногда встречается обозначение числа сочетаний из 7 элементов по 3
в форме (з) ;этот символ имеет то же значение, что и С.
11

Таблица 2
5. ДВА СОСТАВА ИЗ ОБЩЕГО СПИСКА
Шестеро ребят во дворе большого
дома часто играли в лапту «трое на трое».
Однажды один из мальчиков уехал, и
наши друзья остались впятером. Стали
играть вдвоем против троих. А чтобы
никому не было обидно, стали составлять
команды всеми возможными способами.
Сколько различных команд по три
участника и сколько — по два участника
можно составить из пяти человек?
Решение. Назовем наших ребят
Андреем, Борисом, Виктором,
Григорием и Дмитрием и попробуем составить
всевозможные команды (в таблице 2
оставлены лишь начальные буквы имен).
Легко понять, что команд по 2 человека существует ровно С|,
а команд по 3 человека — ровно С5. Но каждой команде
из двух человек соответствует одна и только одна (часто
говорят: ровно одна) команда из трех человек. И обратно:
каждой команде из трех человек соответствует ровно одна команда
из двух человек. А это и означает, что количество тех и других
команд совпадает, т. е.
Если бы т спортсменов нужно было разбить на 2 команды,
в одной из которых η человек, а в другой — остальные т—п
человек, то, дословно повторив наше рассуждение, мы пришли бы
к выводу, что число сочетаний из т элементов по η равно числу
сочетаний из т элементов по т—п, т. е. получили бы ту же
формулу в общем виде:
° т = ^т·
Рассмотрим еще один пример. 20 выпускников одной школы
подали заявления на механико-математической факультет
Московского университета. После сдачи вступительных экзаменов
в алфавитном списке принятых оказались семеро из них.
Сколько разных списков по 7 человек в каждом можно составить из
20 выпускников нашей школы?
Очевидно, два разных (алфавитных) списка счастливцев
должны отличаться друг от друга хотя бы одной фамилией.
Значит, разных списков существует столько, сколько есть сочетаний
из 20 элементов по 7, или С720.
В алфавитном списке непринятых, конечно, остальные 13
выпускников нашей школы. Им предстоит выполнить неприятную
1 Команды 1
по 2
человека
АБ
АВ
АГ
АД
БВ
БГ
БД
ВГ
вд
гд
по 3
человека
БТД
БГД
БВД
БВГ
АГД
АВД
АВГ
АБД
АБГ
АБВ
12

обязанность! забрать обратно аттестаты ή другие документы.
Разумеется, разных списков таких неудачников столько, сколько
есть сочетаний из 20 элементов по 13, или СЦ.
Но каждому списку принятых соответствует один и только
один список непринятых. И обратно: каждому списку
непринятых соответствует ровно один список будущих студентов.
Множество X (различные списки принятых) и множество У
(различные списки непринятых) находятся во
взаимно-однозначном соответствии. Каждому элементу первого множества
соответствует ровно один -элемент второго множества, и обратно.
Очевидно, оба эти (конечные) множества содержат одинаковое
число элементов. Отсюда сразу же вытекает, что СЦ =С^0.
Если бы в университет поступали т абитуриентов, η из
которых приняты, а остальные т—п не приняты, то, дословно
повторив наше рассуждение, мы сделали бы вывод, что
т — υ/η· \ό1
Заметим, что эти выводы получены без вычислений, на
основе одних только логических рассуждений. Впрочем, этот же
результат можно получить непосредственно из формулы для числа
сочетаний, если.записать ее с помощью факториалов:
сп _А™ = ml и\
т~]Г (т-п)\пГ *'
В нашем случае СЦ= : ; Ц70 д - ^ „,,„,» от-
J№ . & 2° _
(20—13)! 13! ' 20 (20—7)! 7! *
куда непосредственно следует, что С^ = С£0.
20. Решите системы уравнений: а) С%+1 : С% t C^r1 =5 : 5 : 3;
б)
\А\Аух '=8, Μ'ι^-ιο,
Су: с1Г1-1>*1 В) \СУ-1 : Cl=((fi;
_2ί. На кафедре математики 9 преподавателей. Сколькими
способами можно составить расписание консультаций на 9 дней,
если каждый преподаватель дает консультацию ровно один
раз?
22. В комитете комсомола 9 членов. Сколькими способами
можно составить из них делегацию в составе трех человек для
поездки к шефам?
13

23. 9 членов профсоюзного комитета должны избрать из своего
состава председателя, секретаря и казначея. Сколькими
способами это можно сделать?
24· Проверьте равенства: a) Cl+Cl^C*; б) С*2,'+С* г —
Гк
6. ВЫБОР ДЕЛЕГАЦИИ
В комитете комсомола 7 членов (включая секретаря). Из них
решено выбрать тройку — делегацию к шефам. Сколькими
способами это можна сделать?
Решение. Различные тройки должны отличаться хотя бы
одним- делегатом. Значит, ответом на вопрос будет число
сочетаний из семи элементов по &
Сколько различных троек (делегаций) включают секретаря
комитета и сколько — не включают?
Решение. Если секретарь — один из делегатов, то еще
двоих можно выбрать из остальных шести членов комитета; для
этого существует
С β = ~ =15 способов,
1 ·2
Если же секретарь не входит в делегацию, то всех троих
делегатов придется выбирать из шести членов комитета (кроме
самого секретаря). Для этого существует
cJ^^Li =20 способов.
1-2-3
Итак, делегаций, включающих секретаря, существует С| = 15,
не включающих секретаря — С|=20. Таким образом, общее
число делегаций, равное С|, разбилось на 2 группы, а именно С\
и Cg. Значит, С1+С\ = С1
Если бы в составе комитета было η комсомольцев, а в
делегацию избрали k членов, то, дословно повторив наше
рассуждение, мы получили бы общую формулу, которую иногда
называют правилом Паскаля:
7. ТРИ ВИДА СОЕДИНЕНИЙ
Итак, мы рассмотрели 3 вида соединений: перестановки,
размещения и сочетания (без повторений). Напомним, что:
перестановки отличаются друг от друга только порядком
расположения элементов;
14

размещения отличаются либо выбором элементов, либо
порядком их расположения;
сочетания отличаются только выбором элементов.
В следующих упражнениях сначала определите вид
соединения, а потом произведите вычисления.
25. 25 учителей, встретившись перед педсоветом, обменялись
рукопожатиями. Сколько было сделано всего рукопожатий?
26. 25 выпускников школы решили обменяться
фотокарточками. Сколько было всего заказано фотокарточек?
27. Ученики изучают 9 различных предметов. 1 сентября в
классе должно быть 5 уроков. Сколькими способами
можно составить расписание уроков для этого класса на 1
сентября, чтобы в этот день было 5 различных предметов?
28. Для передачи сигналов вывешиваются одно под другим три
разноцветных полотнища. Сколько разных сигналов
можно передать при наличии белого, желтого, красного,
зеленого, синего и черного полотнищ?
29. Решите уравнение С|£-{ = 120.
30. Сколько существует различных четырехзначных чисел с
неповторяющимися цифрами?
31. На железной дороге 25 станций. На каждом билете
печатаются станция отправления и станция назначения. Сколько
всего различных билетов нужно печатать: а) Если каждый
билет действителен только в указанном направлении?
б) Если каждый билет годен либо на поездку «туда», либо
на поездку «обратно»? в) Если, кроме билета на одну
поездку «туда», нужно печатать билет на поездку «туда и
обратно»?
32. а) Сколькими способами можно назначить в патруль трех
солдат и одного офицера, если имеется 15 солдат и 4
офицера?
б) В спортобществе 10 сильных лыжников и 8 сильных
лыжниц. Сколькими способами можно сформировать
команду из четырех лыжников и трех лыжниц?
в) Футбольная команда составляется из вратаря, трех
защитников, двух полузащитников, пятерых нападающих.
Сколько разных команд может составить тренер, если
в клубе 3 хороших вратаря, 6 защитников, 5 полузащитни-
крв, 8 нападающих (команды считаются разными, если
они отличаются хотя бы одним участником, причем
предполагается, что нападающий не может играть в
полузащите, но может играть на любом м^сте в линии нападения)?
33. Автомобильные номера состоят из трех букв, за которыми
идут 4 цифры, например МКМ 07-37. Сколько машин можно
снабдить различными номерами, если используется 25 букв
(буквы Ь,Ъ, Е, И и Ы не используются)?
15

34· Аня, Вера, Галя, Дина, Жанна, Зоя, Ира и Катя
отправились в путешествие на двух лодках, в меньшей из которых
могли поместиться не более четверых, а в большей — не
более шестерых. Сколькими различными способами они
могут распределиться в разные лодки? (Распределения
считаются различными, если хотя бы одна из девушек
окажется в другой лодке.)
8. БАСКЕТБОЛИСТЫ ТРЕНИРУЮТСЯ В ЗАЛЕ
Зимой баскетболисты приходили на тренировки
неаккуратно. Иногда собирались все 9 членов секции, а порой только двое-
трое. Однажды тренер решил подсчитать, сколько же всего
вариантов появления в зале разных составов.
— Вот сегодня пока никто не явился. Один вариант. А
может, кто-то один еще придет, хоть мяч в сетку покидает. 9
человек— 9 вариантов.— И тренер записал: 1+9=10.
— Могут прийти двое,— продолжал он размышлять.— Вчера
были Алексей и Борис, позавчера — Борис и Виктор. Опять
разные составы.
Считал, считал тренер и сбился.
Сколько разных составов баскетболистов может собраться в
зале? Составы считаются разными, если они различаются числом
участников* или самими участниками.
Решение I. Чтобы подсчитать число разных составов,
разобьем их на группы по числу явившихся участников:
1) не явился никто—1 вариант;
2) явился один участник — 9 вариантов (т. е. С\=9);
3) явились двое из девяти — число вариантов равно С ;
10) явились все 9 участников — число вариантов равно Сэ = 1·
Общее число вариантов получается сложением:
с10+ с1 + с* + с3 + с4 + с5 +6 + с1 + с8+ с9
Ъ 9 ' 9 9 9 9 9 ' 9 9 9
Это же выражение можно записать короче, если воспользовать·
ся знаком суммы:
Здесь суммирование ведется при изменении k от k=0 до 9.
Решение II. Первый из баскетболистов (например, по
алфавиту) может либо явиться, либо не явиться; имеем два
варианта. Второй спортсмен также может либо присутствовать,
либо отсутствовать. Для двоих участников имеем 4 варианта (см·
табл. 3).
Третий участник может при этом либо отсутствовать
(остаются имеющиеся 4 варианта), либо присутствовать (еще 4 ва«
18

Таблица 3 рианта). Таким образом,
присутствие или отсутствие
каждого следующего
баскетболиста увеличивает число
возможных вариантов вдвое; для
девяти членов секции будет
29=512 различных составов,
в том числе юдин вариант,
когда явятся все 9
участников, и один вариант — пустой
зал.
Обобщая это рассуждение на η спортсменов, можно получить
важную формулу:
С« + Сп+^+...+С2=2», (6)
или
пк η
Σ С = 2 . (6а)
35. Каждого из семи студентов можно направить для
прохождения практики на один из двух заводов. Сколькими
различными способами можно это сделать?
36. В классе 29 учеников. Сколько существует различных
вариантов присутствия (отсутствия) этих учеников в классе?
37. Сколькими различными способами можно разложить 8
монет различного достоинства в два кармана?
38. Сколько различных четных делителей имеет число 2310?
39. Имеются катушки с омическим сопротивлением 1, 3, 5, 10
и 20 ом. Сколько цепей с различным сопротивлением
можно получить, соединяя некоторые из этих катушек
последовательно?
40. Выполните упр. 35, е<уш для практики можно выбрать
любой из трех заводов.
41. После окончания всех экзаменов бывшие десятиклассники
устроили вечер, на котором к чаю предлагали торты
«Чародейка», фруктовый, шоколадный, ореховый и вафельный.
Оказалось, что каждый отобрал себе разный набор
кусочков тортов, а Сережа, которому врач запретил сладкое, пил
чай без торта. Сколько выпускников было в X классе?
На сколько кусочков пришлось разрезать каждый торт?
42. В городе /V автобусы ходят без кондукторов.
Φ # · Пассажиры заранее приобретают талоны,
пробиваемые компостером, причем вид про-
ф φ # бивки меняется два раза в день. Сколько
различных пробивок можно установить на
φ φ φ компостере, если он пробивает отверстия не
менее чем на трех из девяти возможных мест,
Рис. 5 но не на всех девяти (рис, 5)?
№
варианта
1
2
3
4
Первый
участник
нет
да
нет
да
Второй
участник
нет
нет
да
j да
17

9. ТРЕУГОЛЬНИК ПАСКАЛЯ
Выше доказана справедливость важной формулы
Паскаля (5), которую можно записать в виде С*+1 = Ck+x + С*.
Замечая, что С£ = С£==1 и C\=k, получим последовательно:
С2 = С1 + С3 =2+1=3;
3 2 2
С2= С1 + С2 =3+3=6 и т. д.
4 3 3 '
Объединим найденные числа в таблицу 4 (чисел сочетаний):
Таблица 4
Из
скольких
элементов
1
2
з '
4
5
6
7
8
0 1
1 1
1 1 2
! 1 3
1 4
1 5
1 6
1 7
1 8
По
2
1
3
6
10
15
21
28
сколько
3
1
4
10
20
35
56
элементов
4 5
1
5 1
15 6
35 21
70 56
6
1
7
28
7
■
1
8
Полученная нами таблица обычно называется
арифметическим треугольником или треугольником Паскаля. В качестве
упражнения продолжите эту таблицу до 12-й строки
включительно (для контроля: среднее число в 12-й строке должно быть
равно 924).
10. КОЭФФИЦИЕНТЫ МНОГОЧЛЕНА
Легко найти произведение двучленов:
(х—а) (х—b)=x2— (a-{-b)x-\-ab.
Можно найти произведение трех двучленов:
(х-~ а) (х—Ь) (х—с) =*3— (a+&+c)x2+ (ab-\-ac-\-bc)x—abc.
Пусть теперь требуется найти произведение η таких
двучленов: ,
Рп(х) = (х-а) (x-b) (x-c) (x-d) ... (х-р). (7)
Раскрывая скобки и группируя члены с одинаковыми
степенями х9 получим многочлен, расположенный по убывающим
степеням х: Рп(х)=хп—лг*-1(а+&+с+ ... +ρ)+χη~2(α&+α£+
+ &с+ ...)— xn-*(abc+abd+ ...) + ... +(— \)*(abcd ,,. ρ),
или, короче, Pn(x)=s0xn-\-SiXn-l+s2xn-2+ ·.. +sn. (7a)
18

Нетрудно заметить, что:
старший коэффициент s0 многочлена Рп(х) равен 1;
члены имеют знакочередующиеся коэффициенты;
каждый коэффициент Sk равен сумме всевозможных
произведений вторых членов, стоящих в скобках,— по. k сомножителей
в каждом произведении.
43. Раскройте скобки и расположите получившиеся многочлены
по убывающим степеням х:
а) (х—2).(х-4)(х-3);
б) (х+1)(х+2)(х+3)(х+4);
в) (jc—I) (jc+2) (ж—5) (лг+4);
г) {х-1)(х-2)(х-3)(х+1)\х+2).
Замечание. Если Яп(Х)=0, то, раскрывая скобки,
получим уравнение степени η относительно х. Orto, очевидно, имеет
ровно η корней: хх=а, х2=Ь и т. д., так как эти корни обращают
в нуль одну из скобок в выражении (7). Решение таких
уравнений здесь не рассматривается.
11. БИНОМИАЛЬНАЯ ФОРМУЛА
Предположим, что в выражении (7) все вторые члены равны
между собой, т. е. Р(х) = (х—а)п. Тогда $0=1; $ι = — (α+α+
+ ... -\-а) ——па; s2=(a2-fa2+ ... +а2) — С2па2, ибо
слагаемых в скобках будет столько, сколько существует всевозможных
парных произведений из η сомножителей, а именно С2п\
следующие коэффициенты будут 53=—C^a3; s4=C*a4 и т. д. «Общий»
коэффициент, стоящий на (&-Н)"м месте, будет (— l)*C*-afe;
наконец, последний коэффициент будет (—\)пап.
Окончательно получим:
(x—a)n—xn—naxn~l+C2n a2*n~2—С* a3xn~z + ... +
+ (-1)*С*а*х*-*+ ... +(_l)nfln. (8)
Формула (8) называется формулой разложения бинома
Ньютона 1 и применяется для возвышения в натуральную степень
бинома (х—а). В этой формуле (&+1)-й член имеет вид:
Th+i = (-l)hcl a***-\ (9)
1 Впрочем, формула (8) была известна в Европе уже М. Штифелю
(середина XVI в.), а на Востоке, вероятно, еще раньше. В 1678 г, Ньютон
обобщил эту формулу, показав возможность разложения в «биномиальный
ряд» степени (1+х)а при любом действительном значении а. Подобные
ряды изучаются в вузовских курсах математического анализа. Формулу (8)
часто называют просто биномиальной формулой или биномиальной теоремой.
19

В некоторых задачах все члены разложения, кроме одного,
обращаются в нуль. По формуле (9) можно находить
требуемый член, не выписывая всего разложения"целиком.
Замечания. 1) Если в натуральную степень возвышается
сумма (х-\-а), то все члены разложения становятся
положительными, например:
(х+а)б=*6+6a*5+ 15α2*4+20α3Λ*+15α4*2+6α5*+α6;
2) под χ и под а можно понимать любое число или любое
алгебраическое выражение, например:
(3*-2а)*= (3;с)5-5.2а(3х)4+10(2а)2(3^)3-10(2а)3. (3*)2-h
+5(2α)43χ-(2α)5=243χ5-810α^+1080α2χ3-
—720α3*2+240α4*—32a5.
Отметим некоторые свойства формулы (8):
1) число членов разложения на единицу больше
показателя п\
2) показатели степени первого числа (х) убывают, а
показатели степени второго числа (а) возрастают от члена к члену
на одну единицу; сумма показателей в каждом члене равна п\
3) коэффициенты членов разложения, равноудаленных от
концов, равны между собой (они совпадают с числами
соответствующей строки треугольника Паскаля);
4) сумма всех биномиальных коэффициентов равна 2П
(сравните с формулой (6));
5) сумма биномиальных коэффициентов, стоящих на четных
местах, равна сумме биномиальных коэффициентов, стоящих
на нечетных местах; каждая из этих сумм, равна 2П~1.
44. Докажите сформулированные выше свойства (1), (3), (4),
(5).
Указание. Для доказательства свойств· (4) и (5)
примените формулу бинома к двучленам (1 + 1)п и (1—1)п. '
45. Найдите разложения: а) (2у2—3у)5; б) (1— У2)6;в) (2|Л*—
-4У*)4,
46. Найдите: а) девятый член разложения (я+У*)12; б) шестой
член разложения (а2—я3)13.
12. РЕШЕНИЕ ЗАДАЧ
Найдите член разложения (У у— Ϋυ)20, содержащий у7.
Решение: Сначала запишем общий вид разложения .
Гж-С^/у ) iVyf =C20y* .» 2 =СоУ 4 .
0 40—k - 40—* -
По условию у = */ > т. е. =7,
20

Отсюда находим k — \2 и искомый член ^i2+i = C^#7=C!)i/8="
= 216970 у7.
В разложении (у^^—Υ коэффициент пятого члена
относится к коэффициенту третьего члена, как 7: 2. Найдите член
разложения, содержащий χ в первой степени.
Решение (получается в три этапа).
1) Из условия следует, что
4
СР_ J_ /»(Р-1)(Р-2)(Р-3) 12 = ^
с* 2 ' ИЛИ 1.2-3-4 'р(/>-1) 2 '
откуда находим ρ=9;
2)" записываем общий член разложения
. / j \ k 2k 9—k
Так как ищется член, содержащий χ в первой степени, то
2k , 9—ft ,
~Т+ 1 '·
откуда находим £=3;
3) искомый член Т3-н = Сз9х1 = 84 я.
47. В разложении ( \-у\ коэффициент четвертого члена
относится к коэффициенту шестого члена, как 5: 18. Найдите
в этом разложении член* не содержащий у.
48. Найдите член разложения (яуя+ -jt^) » который после
упрощений содержит а5, если сумма биномиальных
коэффициентов этого разложения составляет 128.
49. Имеется многочлен x(l—x)l0+x2(l— 2х)20+х3(1— За:)30.
Определите коэффициент при члене, содержащем я4, если
выполнить все указанные действия.
50. Второй, третий и четвертый члены разложения (*+ί/)ρ
равны соответственно 240, 720 и 1080. Найдите х, у, и р.
51. Выведите формулу для, (х-\-а)п методом математической
индукции по п.
13. НЕКОТОРЫЕ ПРИБЛИЖЕННЫЕ ФОРМУЛЫ
Вычислим 1,0025 с точностью до 0,000001.
Решение. Воспользуемся формулой бинома:
(1+0,002)5=15+5·14·0,002+10.13.0,0022Η-10·12·0,0023+
+5· 1 ·0,0024+0,0025 = 1+0,01+0,00004+0,00000008+
+0,000000000000032» 1,010040.
21

Когда второе число бинома значительно меньше единицы, то
члены разложения (l+x)n, содержащие высокие степени х,
становятся очень малыми. При вычислениях, не требующих
высокой точности, можно отбросить эти малые члены, если они
меньше допустимой погрешности* вычислений. В частности,
пренебрегая второй и более высокими степенями х, получаем
приближенные формулы:
(l+*)*«l±fe*. 0°ϊ
52. Вычислите: а) 1,04е (с точностью до 0,0001); б) 0,9974
(с точностью до 0,000001).
Вычислим приближенно 10,025.
Решение. 10,025= 10- (1,002)5= 105· 1,0025= 105Х
X 1,010040 ... «101004,0 (с точностью до 0,1).
53. Вычислите: а) 6,034 (с точностью до 0,1); б) 4,975 (с
точностью до 1).
Вычислим приближенно У 1,012.
Ρ еш ен и е. 'Приближенная формула (10) применяется для
любых, значений к (а не только для натуральных)1. Поэтому
1,012= (1+0,012)°'5= 1+0,5-0,012= 1,006.
54. Вычислите приближенно: а) 4/1,02; б) |/"'8,024; в) ^999.
14. НАТАША НАНИЗЫВАЕТ БУСЫ
В самом начале книги было сказано, что из трех букв можно
составить 3!=6 различных трехбуквенных «слов». Вот,
например, слова, составленные из букв К, О, Т:
КОТ, КТО, ОКТ, ОТК, ТКО, ТОК.
Составим теперь трехбуквенные слова из букв К, К, О.
Если бы одинаковые буквы можно было различить (например, К2
и Κι), то мы тоже получили бы 6 «слов»:
1) К1К2О; 2) К2К1О; 3) KiOKs; 4) К2ОКг, 5) ОК1К2;
6) ОК2Кь
Легко заметить, что «слова» (1) и (2), а также (3) и (4),
(5) и (6) отличаются только индексами; без индексов эти пары
слов неразличимы. Поэтому из букв К, К, О можно составить не
6, а только 3 различных «слова»: ККО, КОК, ОКК.
Можно рассуждать так: перестановка одинаковых букв не
меняет «слова»; поэтому общее число перестановок с
повторениями во столько раз меньше числа перестановок без
повторений, сколькими способами можно переставлять повторяющиеся
буквы (элементы). В нашем простейшем примере было всего
3 элемента, из которых 2 повторяющихся; поэтому число
перестановок оказалось равным
Сравните с замечанием о биномиальном ряде.
22

Наташа получила в подарок 10 просверленных шариков из
оргстекла: 5 белых, 2 красных и 3 голубых. Она продела в них
нитку и надела как ожерелье на шею. Потом стала менять
порядок расположения шариков,ч и каждый день ожерелье
принимало другой вид. Сколько разных видов ожерелья может
получить Наташа?
Решение. Если бы шарики одного и того же цвета были
различимы (индексированы), то общее число разных
расположений составило бы 101=3 628 800 способов. Однако при любой
перемене мест пяти белых шариков ожерелье не меняет своего
вида, поэтому разных видов ожерелья будет меньше в 5! =120 раз.
Те же соображения относятся и к двум красным и к трем
голубым шарикам.
Ответ. — =2520 видов.
5! 2! 3!
Если еще учесть, что ожерелье замкнуто, т. е. последний
шарик примыкает к первому, и циклическая перестановка шариков
не меняет вида ожерелья, то окажется, что в действительности
возможны только 252 различных вида.
Рассуждая точно так же в общем случае, можно получить
формулу для числа перестановок из η элементов, среди которых
пг — первого вида, п2 — второго вида, ... n* — fc-ro вида. Это
число оказывается равным —;——-. — · здесь η=/ι14-/ι2+ ....
-f/z/t, а некоторые элементы могут и не повторяться, так что
может быть, например, пг = 1. Общепринятого символа для этого
выражения нет; количество видов Наташиного ожерелья
можно было, например, обозначить
Р(10\ 5, 2, 3)= -12!—.
V ; 5! 2! 3!
55. Подсчитайте число перестановок из букв слова
МИССИСИПИ.
56· Женщина, оставшаяся в захваченной врагом деревне,
постоянно передавала информацию о вражеских войсках. Для
этого она развешивала в условленном порядке выстиранное
белье: 4 синих полотенца, 2 белые рубашки и 3 черных
трусов. Сколько различных сигналов она могла передавать?
57. Решите задачу 56, если развешиваются 4 белых полотенца
и одна, или две, или три голубые рубашки.
15. СЕРЕЖА ШТАМПУЕТ НОМЕРА
У Сережи остались от набора для настольной игры штампы
с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести
на все книги пятизначные номера — оставить каталог. Первая
книга получила номер 11 111, следующая 11 ИЗ, потом 11 117,
23

Π 131 и т. д. Сколько различных пяти- Таблица 5
значных номеров может составить
Сережа?
Решение. Составим сначала
всевозможные двузначные номера из цифр
1, 3, 7 (см. табл. 5).
Таких чисел оказывается 3-3=9.
Третья цифра может быть добавлена к
каждому из этих девяти двузначных
чисел ровно тремя способами, получится 9-3 = 27 трехзначных
чисел. Точно так же можно* тремя способами добавить
четвертую и пятую цифры, получится 27-3=81 четырехзначное и
81-3 = 243 пятизначных числа.
.Эти пятизначные числа отличаются друг от друга либо
самими цифрами (например, 11 113 и 11 117), либо порядком их
расположения (например, 11 113 и 31 111). Таким образом мы
составили размещения с повторениями; их число оказалось
равным
^=3.3'.3-3-3=35.
Если различных штампов будет не 3, а п и если Сережа
составит ими не 5, a k знаков, то общее число различных
обозначений окажется пк. Это и есть формула для числа размещений
с повторениями из η элементов по k.
58. В двоичной системе счисления, применяемой в ЭВМ,
существует только 2 знака: 0 и 1 (иначе: включено —
выключено, соединено — разъединено, есть ток — нет тока). В
одной из ЭВМ каждое «машинное слово» записывается в
ячейке «памяти», содержащей 37 пронумерованных
двоичных разрядов. Сколько различных «слов» можно записать
в такой ячейке?
16. В ГОСУДАРСТВЕННОМ СОВЕТЕ ШВАМБРАНИИ
В домино играют двойными фишками, на каждой половинке
которых изображены точки в количестве от нуля (пустая) до
шести. Сколько всего разных фишек в полном наборе домино?
Решение. Обозначим фишки, изображенные на рисунке 6,
2 4
через — и —. Фишки с одинаковым числом очков на обеих
половинках назовем дублями, а с разным
числом очков — простыми. Все простые фишки
можно обозначить правильными дробями, т. е.
в случае, изображенном на рисунке, обозначим
именно ■—, а не —· Значит, нужно найти
число правильных дробей со знаменателями не
Рис. 6 более шести и добавить к ним 7 дублей. Но чис-
1
Первое
число
1
з
7
Второе число 1
ι | з
11
31
71
13
33
73
I 7
17
37
77
24

ло правильных дробей со знаменателями не более шести равно
числу сочетаний из семи элементов (0, 1, 2, 3, 4, 5, 6) по 2, т. е.
7'JL
2
С =—=21.
4 ы
Ответ. Разных костей домино всего 21+7=28.
Каждая кость домино соответствует паре чисел, одинаковых
или разных, выбираемых из множества {0, 1, 2, 3, 4, 5, 6}.
Любую фишку можно обозначить последовательностью нулей и
единиц, причем 'единицы будут стоять на тех местах, которые
соответствуют числам, изображаемым на фишке: для нуля—на
первом месте, для единицы — на втором, для двойки — на
третьем... Если фишка — дубль, то две единицы окажутся
записанными подряд, в противном случае после единицы пишем
дополнительный нуль, которым отделяются символы разных элементов.
Например, фишке— соответствует запись (0, 0, 0, 0, 1, 1, 0, 0),
4 2
фишке — запись (0, 0, 0, 0, 1, 0, 1, 0), фишке запись
5 5
(0, 0, 1, 0, 0, 0, 1, 0); выделенный здесь дополнительный нуль
является разделительным.
Нетрудно убедиться, что каждому способу записи двух
единиц и шести нулей соответствует ровно одна фишка домино.
Значит, количество разных фишек равно числу перестановок из
двух единиц и шести нулей, или
Р<8;2.6)=^=<=28.
Государственный совет Швамбрании подал в отставку.
Предстоит формирование нового совета из семи человек, причем в
него могут быть избраны представители четырех политических
.партий: 1) Желтой, 2) Оранжевой, 3) Синей и 4) Фиолетовой
(сокращенно: Ж, О, С, Ф). Сколько различных советов можно
составить, если иметь в виду только численное
представительство партий?
Решение. Обозначим совет из трех членов Желтой партии,
двух — Оранжевой и двух — Фиолетовой последовательностью
(1, 1, 1, 0, 1, 1, 0, 0, 1, 1); три первые единицы указывают трех
членов первой партии, следующие после нуля две единицы —
двух членов второй партии, затем после нуля нуль членов
третьей партии и две единицы — двух членов четвертой партии. В
итоге у нас получилось 7 единиц и 3 нуля. Аналогично запись (1,0,
1, 1, U 0, 1, 0, 1, 1) обозначает одного члена Ж, трех членов О,
одного члена С и двух членов Ф. Для перестановок из семи
единиц и трех нулей существует
Рпо.73)= —- =С способов.
25

Вообще, а единиц и Ь нулей можно расположить числом
способов, равным
(а+Ь)! ' ~ *
а! Ы
Ρ(α+6;α,6)== —^t С a+Q .
При составлении последовательностей нулей и единиц,
соответствующих фишкам домино, нам пришлось добавить один
нуль, чтобы отделить единицы, соответствующие различному
числу очков на половинках фишек домино. При составлении
последовательностей, соответствующих числам членов четырех
политических партий в совете, пришлось добавить 3 нуля;
вообще, составляя обозначения из единиц и нулей для сочетаний с
повторениями по η элементов, среди которых есть т различных,
придется добавить т— 1 разделительных нулей. Полученное
после этого количество различных перестановок с повторениями
из η единиц и т—\ нулей в точности совпадает с количеством
сочетаний с повторениями из т элементов по п. Значит, число
сочетаний с повторениями выражается формулой
Примечание. Сводка формул всех видов соединений
приведена в таблице 6.
59. В школьный комитет комсомола избирают 9 членов,
которые могут быть учениками VIII А, или VIII Б, или IX, или
X класса, причем из одних десятиклассников комитет
составить нельзя. Сколько различных комитетов,
отличающихся представительством классов, можно избрать?
60. Сколько существует различных целых чисел, меньших
10 000, в написании которых содержатся цифры 1, 2, 3
(каждая цифра не менее одного раза)?
17. АЗБУКА МОРЗЕ
В азбуке Морзе, которая используется для телеграфных
сообщений, содержится только два знака: точка и тире. Каждая
буква или цифра кодируется определенной последовательностью
точек и тире. Например:
А — 1
Б 2
В 3
Г 4
Д —· ' +
Ε - -
Э и т. д.
26

со
ев
ST
Χ
о
СО
Η
«
s
χ
<u
cu
о
пов
го
из
*»»^
ε
'η!
""^
С
1
ε
^
к 1
«6
X
2
к
S
я
а»
о,
о
н
BQ
О
с
■ as
S
X
Си
о
Η
CQ
О
С
го
ι-ч:
я
2
Я ·
Ε
ω
α
! ο
Η
κ
ί U
"2:
с
-
с
*Γ
•0,
с
Ι
*"··
■*
£
•
*^·
£

Некоторые символы передаются одним знаком, как буква Е,
другие — двумя, тремя и даже пятью знаками. Попробуем
подсчитать, сколько различных символов можно передать.
Одним знаком можно, очевидно, передать ровно два
различных символа: «·» (буква Е) или «—» (буква Т). Двумя
знаками можно передать «· ·», или «—», или «—», или « », т. е.
четыре различных символа. Присоединяя к каждому из этих
четырех символов точку или тире, получим еще восемь символов.
Далее, присоединение каждого нового знака дает возможность
увеличить число различных символов вдвое; с помощью k
знаков можно передать 2Л различных символов. Таким образом,
используя код, содержащий от одного до пяти знаков, можно
передать 21+22+23+24-Ь25=62 различных символа, которых и
оказалось достаточно для телеграфной азбуки Морзе. Позднее
для некоторых знаков были присоединены шестизначные
символы (например, минус, кавычки, двоеточие, восклицательный
знак, запятая, дробная черта и т. п.).
61. В азбуке Брайля (для слепых) каждый символ
обозначается шестью точками; на некоторых из них имеются
выпуклости, которые легко определяются осязанием (на
нашей схеме выпуклости обозначены плюсом):
+ О + О + + + +1
ОО +0 +0 + +
ОО ОО +0 +0
А Б Π Ч
Ощупывая пальцами эти знаки, слепые могут «читать» любой
текст. Сколько различных символов может быть в азбуке
Брайля?
62. В телефонной сети города Безпятска запрещен набор
цифры 5. Сколько различных «безпятских» абонентов можно
вызвать набором четырехзначного номера, если ни один
номер не должен начинаться с нуля?
18. ИЗ ИСТОРИИ КОМБИНАТОРИКИ
Уже в школе пифагорейцев (VI—IV вв. до н. э.) изучались
«треугольные числа», которые представляют собой сочетания
по 2 элемента.
В документах, относящихся к началу нашей эры,
упоминаются «четырехгранные» или «пирамидальные» числа,
представляющие собой С\. «Треугольными» называются числа вида
2-^—-; придавая η значения 1, 2, 3, 4 ..., получим
треугольные числа 1, 3, б, 10, ... .
Если одинаковые шары выложить на плоскости в виде
треугольника, в верхнем ряду которого один шар, в следующем т-
28

два, затем — три, четыре и т. д.,
то общее количество шаров в
первых рядах выразится
треугольными числами. Можно
представить себе также
несколько одинаковых кругов (например,
монет), выложенных на стол
вплотную друг к другу (рис. 7).
Точно так же
«пирамидальные» или «четырехгранные»
числа связаны с числом шаров,
сложенных в виде пирамиды, в
Рис, 7 верхнем ряду которой один шар,
лежащий в углублении между
тремя касающимися друг
друга шарами следующего ряда (слоя); каждый следующий слой
содержит следующее «треугольное» число шаров (1, 3, 6, 10,
15, ...), так что первыми пирамидальными числами служат 1,
4, 10, 20, 35, . ♦., представляющие собой числа сочетаний из
трех, четырех, пяти и т. д. элементов по три.
Во всех странах мира люди с давних времен играли в кости.
Особенно широкое распространение получили азартные игры
с развитием денежного обращения. Сиятельные графы и морские
пираты, византийские купцы и золотоискатели Невады,
блистательный д'Артаньян и его товарищи-мушкетеры — все были
заражены азартом этой древней игры. Атос оценил своего слугу
Гримо в десять ставок; выигрыш и проигрыш состояний,
дворцов, поместий хорошо известны в истории. Игра
распространилась настолько, что христианской церкви пришлось
издавать указы и постановления, запрещавшие или
ограничивающие игру. Участникам третьего крестового похода
не разрешалось проигрывать более 20 шиллингов в сутки.
Людовик IX (XIII в.) запретил не только игру, но даже
изготовление костей. Издавались законы о запрещении игры и
на Руси (царь Алексей Михайлович — в 1649 г., Екатерина II —
в 1782 г.).
В XVII в. в Европе стали распространяться таблицы, в
которых перечислялись возможности получения разного числа очков
на двух и трех костях. Математики стали анализировать
комбинации, получающиеся при бросании костей. Наиболее полно
сделали это Галилей, Паскаль и Ферма.
Паскаль и Ферма излагали свои результаты в письмах.,
В 1653 г. Паскаль писал друзьям о подготовленной им
рукописи; однако его «Трактат об арифметическом треугольнике» был
опубликован посмертно лишь в 1665 г. Рукописи Галилея
увидели свет только в 1718 г.
Вероятно, систематическое изложение формул и законов
комбинаторики было впервые опубликовано в 1666 г. Г. Лейбницем
29

в книге «Рассуждения о комбинаторном искусстве»; в 1713 г,
появилась книга Я. Бернулли «Искусство предположения»,
содержавшая также формулы комбинаторики; наконец, великий
Л. Эйлер рассмотрел ряд комбинаторных задач, из которых
впоследствии развились самостоятельные отрасли науки,
находящие в наши дни оамое широкое применение.
Уже много сотен лет люди пользуются различными формами
тайнописи — криптографии. Чтобы текст не могли прочитать
непосвященные, слова иногда записывали в обратном порядке,
т. е. от конца к началу; иной раз пользовались заменой одних
букв алфавита другими; чтобы прочитать такую запись, нужно
было знать «ключ»— способ замены букв.
Развитие комбинаторных методов позволило
расшифровывать такие записи. Победа Кромвеля в гражданской войне
(Англия, середина XVII в.) была в значительной мере облегчена
раскрытием намерений монархистов. Заговорщики думали, что
их планы выданы тайным агентом Кромвеля. А после
реставрации Стюартов стало известно, что один из лучших английских
математиков того времени сумел очень быстро разгадать
несложные шифры заговорщиков.
Несколько сотен лет назад ученый, сделавший какое-либо
открытие, публиковал об этом сообщение или даже книгу.
Если же открытие было еще недостаточно проверено, то
публикация могла оказаться преждевременной, а задержка публикации
грозила потерей приоритета. Поэтому многие ученые
публиковали (или посылали другим ученым в письмах) краткое
сообщение в форме анаграммы.
Анаграмма — слово (или фраза), составленное из тех же
букв, но в другом порядке. «Нева» и «Вена» — анаграммы.
Получивший сообщение «Вена» может довольно быстро
составить остальные 23 четырехбуквенных слова из тех же букв
и догадаться, что зашифровано «Нева». А если в анаграмме,
скажем, 30 букв (причем некоторые повторяются от двух до шести
раз), то существует , или около 7-Ю22,
v ' J * 2! 2! 31 3! 4! 5! 5! 6! * .
способов их перестановки.
Галилей, наблюдая в 1610 г. Сатурн с помощью
построенного им телескопа, заметил у него два спутника. Однако, не будучи
уверен в своем открытии, он возвестил об этом анаграммой,
зашифровав по-латыни сообщение, которое можно перевести так:
«Высочайшую планету тройною наблюдал».
Полвека спустя голландский ученый Христиан Гюйгенс с
помощью более мощного телескопа обнаружил кольцо Сатурна
и поместил в очередной брошюре анаграмму своего открытия.
А английский математик Уоллис (тот самый, который помогал
Кромвелю дешифровать переписку монархистов) сумел
расшифровать ее и, шутки ради, послал в свою очередь Гюйгенсу
сообщение, также в форме анаграммы, о своем аналогичном от-
30

крытии. Говорят, что Гюйгенс, сам большой любитель и знаток
комбинаторики, не захотел принять шутки и рассердился.
Современный вид формулы комбинаторики приняли к началу
XIX в.; в это время уже почти полностью сформировалась и
современная алгебраическая символика.
В наши дни комбинаторные задачи приходится решать
физикам, химикам, биологам, экономистам, специалистам самых
разнообразных профессий.
ОТВЕТЫ И УКАЗАНИЯ
1. 1) Проверяем гипотезу, например, для й = 2 : 1+3 = 4. 2) Пусть
гипотеза верна для некоторого числа k слагаемых, т.. е. верно, что 1+3+5+ ...
+ (2ft—l) = й2; докажем, что в этом случае гипотеза (формула) верна и для
(ft+Ι) слагаемых, т. е. что 1+3+5+ ... +(2ft-l) + (2fe+l) — (fe+1)2. В
самом деле, сумма первых k слагаемых по предположению равна ft2; остается
доказать, что k2+(2k+l) = (ft+1)2, а это проверяется непосредственно.
120 1
4. а) 90; б) 49; в) — = —\ 5. 3120. 6. 5! — 4! = 96. 7. Выпишем некоторые
из рассматриваемых пятизначных чисел, например,
14 6 7 8 и подсчитаем сумму только единиц во всех 120 слагае-
4 6 7 8 1 мых; эта сумма будет, состоять из 24 единиц, 24 четве-
6 7 8 14 рок, 24 шестерок, 24 семерок и 24 восьмерок,, что со-
7 8 14 6 ставит 24(1+4+6+7+8) =624 единицы; точно так же
получим 624 десятка, 624 сотни и т. д., а всего 624+6420+62 400+624 000+
+6 240 000 = 6 933 264. 8. См. формулу (2) в пункте 3. 9. а) 720; б) 132;
в) 3024. 10. а) Л^ = Р4=-24; б) Л|= 120; в) /1^=360; г) обшее количество
«четырехзначных» чисел составило бы /4^=840; однако, например, число
0123, начинающееся с нуля, не является «четырехзначным»; с нуля
начинается ровно — общего .количества «четырехзначных» чисел; значит,
собственно четырехзначных остается 840——-840 = 720 чисел. Возможен и
другой способ рассуждения: на первом месте в собственно четырехзначном* числе
может стоять любая из шести цифр, кроме нуля; на следующем месте —
любая из оставшихся шести цифр (включая и нуль), далее — любая из
оставшихся пяти, а на последнем месте — любая из оставшихся четырех цифр.
Ответ. 6-6.5.4 = 720. П.-а) 100; б) 10. 12. а) 10; б) 7; в) 9. 14. а) 126;^
ОМ.1Q.1Q
б) 56; в) 56. 15. а) 7; б) 14; в) 9; г) 10. 16. q = *" " " =1140. 17. Чи-
ело опытов С^=20; площадь 5 га. 18. а) Cj=28\ б) Cjj = 56; в) 70.
Указание. Любые четыре точки, выбранные на окружности, могут служить
вершинами трех различных четырехугольников, лишь один из которых —
выпуклый. 19. См. формулу (3) в пункте 5. 20. а) х=7, у=3; б) *=12, (/=5;
в) х=\5, (/=6. 21. ^ = Р9=362 880. 22. С*=84. 23. Л^=504. 25. С^5=300.
26. Als—Ш. 27. /19 = 15 120. 28. Л^=120. 29. х=5. 30. 4536. См. указание
кзадаче10(г).31.а) Л^5=600; б) С*5=300; в) 1200. 32. a) C?5.Cj = 1820.
33. 253- Ю4= 156 250 000. 34. В меньшей лодке могут находиться либо двое
(число' вариантов С\), либо трое (число вариантов С\), либо четверо (число
вариантов С\). Ответ. C2s+Cl+C*=m. 35. £ С*=Я7=128. 36. 2*>.
/2=0 ?
37. 28 = 256. 38. Заметим, что 2310 = 2-3*5-7-11; различные четные делители
31

получаются, если единственный четный простой делитель 2 умножить на
некоторые из остальных четырех простых делителей, в том числе на все четыре
простых делителя (это будет число 2310, которое, конечно, является
делителем самого себя) и ни на один из остальных делителей (это будет число 2,
4 к
которое тоже является делителем числа 2310). Ответ. J] С — 24=16.
& 4
39. 25— 1 = 31 (32-я цепь не содержала бы ни одной катушки). 40. З7;
каждого студента можно направить 4ча практику не двумя, а тремя способами.
41. 25=32; на 16. 42. С^+^+С^+Сд+С^+С» =84+126+126+84+36+
+9 = 465. 45. а) 32#10-240^+720*/8-1080*/Ч-810*/6-243*/5; б) 99-70У2.
46.а)Г8^ = С?2(*)8а*=495а4**; б) Т$+1 = С6гг (χψ(αψ=1287α"χπ. 47. Задача
С3х 5
решается в три этапа: 1) —— = -— > откуда лг= 12; 2) Γα+ι =
С5 *8
/ 1 \ х
= с\2 (iy)h ("" )12""A=Cf2i/0'5fti/fe-12; так как искомый член не должен
содержать у, то 0,5/г+А—12 = 0, откуда k=8\ 3) 7,8+1 = С^2 = 495. 48. 35а5. Задача
решается в три этапа аналогично предыдущей. 49. Следует найти четвертый
член в разложении первого бинома, третий член в разложении второго
бинома, второй член в разложении третьего бинома; затем умножить их
соответственно на х, на х2, на хъ и сложить с учетом знаков. Ответ. 550.
50. Выписав названные члены, получим систему: рух*-1 = 240,
£fcii ^Ρ-ί=720, Pip-llifT2) •„-._ 1080,
которая решается почленным делением. Ответ. х=2, #=3, р=5.
52. а) 1,2653; б) 0,908054. 53. а) 1322,115; б) 3032,368. 54. а) 1 005; б) 2,002;
9! 91
в) 9,997. 55. /Wi.o-4| 3| ц „"2520, 56. р(9;4Ла)«_—- —1260.
51 6!
57. При одной рубашке: Ρ(5;4,ΐ)= 7Γ7, β5ί ПРИ ДВУХ рубашках: Ρ(6.4ι2)=——==
41 11 41 2!
71
= 10; при трех рубашках: Р(7;4>3)= ——г: =35. Ответ. Всего 5+10+35 =
41 31
= 50 различных сигналов. 58. 237 «слов»; в каждом разряде может быть
записан либо 0, либо 1. 59. Пусть в комитете а,\ учеников VIII А класса, ач —
из VIII Б, а3 — из IX и а4-из X класса, причем αι-\-α2+αζ+α^=9\ тогда
состав комитета может быть охарактеризован последовательностью,
состоящей из 9 единиц и 3 нулей, а число таких различных последовательностей
12!
составляет Р(12;9,з) = =220. Однако комитет, характеризующийся по-
У! о!
следовательностью (0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1), состоит из одних
десятиклассников, что запрещено условием. Ответ. 219. 60. 204. 61. 26=64;
каждый символ состоит из шести знаков в двух вариантах. 62. 5832 абонента.
Литература для дополнительного чтения
1. Петер Р. Игра с бесконечностью. М., Просвещение, 1968.
2. Мостеллер Ф., Рурке Р. и Томас Дж. Вероятность. М., Мир,
1969.
3. Виленкин Н. Я. Комбинаторика. М., Наука, 1969.
4. Виленкин Н. Я. Популярная комбинаторика. М., Наука, 1975.
5. Ежов И. И, Скороход А. В., Я д ρ е н к о М. И. Элементы
комбинаторики. М., Наука, 1977.

А. Я. Халамайзер
КОМБИНАТОРИКА И БИНОМ НЬЮТОНА
Редактор В. И. Ефимов
Художник В. Л. Николаев
Художественный редактор Ε. Η. Карасик
Технический редактор Л. Е. Пухова
Корректор В. Я. Громова
ИБ № 4962
Сдано в набор 12.03.79. Подписано к печати 04.07.79. Формат 60Χ90!/ιβ.
Бум. газетная. Гарнит. литерат. Печать высокая. Усл. печ. л. 2. Уч.-изд. л.
1,84. Тираж 100 тыс. экз. Заказ № 3266. Цена 05- коп.
Ордена Трудового Красного Знамени издательство «Просвещение»
Государственного комитета РСФСР по делам издательств, полиграфии и книжной
торговли.
Москва, 3-й проезд Марьиной рощи, 41.
Типография им. Смирнова Смоленского облуправления издательств,
полиграфии и книжной торговли, г. Смоленск, пр. им. Ю. Гагарина, 2.