Основные формулы комбинаторики.

	0	2	4
1	10	12	14
2	20	22	24
4	40	42	44
5	50	52	54
9	90	92	94

Пример 1.

Сколько четных двузначных чисел можно составить из цифр 0, 1, 2, 4, 5, 9?

Решение:

1-й способ. Выпишем по порядку все числа от 10 до 99 и выберем те, что нам нужны: 10, 12, 14, 20, 22, 24, 40, 42, 44, 50, 52, 54, 90, 92, 94. Всего 15 пар.

2-й способ. Изобразим таблицу вариантов:

	0	2	4
1	10	12	14
2	20	22	24
4	40	42	44
5	50	52	54
9	90	92	94

Всего чисел.

ПРАВИЛО УМНОЖЕНИЯ

В теории вероятностей понятие выборки обобщается. Вместо него используют понятие испытание. Поэтому полезно знать правило умножения и на «языке» теории вероятностей.

ПРАВИЛО УМНОЖЕНИЯ:

Замечание: Независимость событий А и В означает, что в такой паре (a,b) возможны абсолютно все комбинации исходов этих испытаний: при любом выборе «координаты» a в качестве «координаты» b можно выбрать любой исход события В.

3-й способ решения примера 1: Испытание А состоит в выборе первой цифры числа, и у него имеется 5 возможных исходов, а испытание В состоит в выборе второй цифры, и у него имеется 3 возможных исхода. Так как выбор первой цифры независим от выбора второй, то по правилу умножения, всего получается исходов.

Ответ: 15.

Пример 2.

Сколько может быть различных комбинаций выпавших граней при бросании двух игральных костей?

Решение:

На первой кости может быть: 1,2,3,4,5 и 6 очков, т.е. 6 вариантов (исходов). На второй — 6 вариантов. Бросают и первую, и вторую, значит, применяем правило умножения. Всего: вариантов.

Ответ: 36.

Пример 3.

Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6?

Решение:

Число всех возможных перестановок цифр 0, 2, 4, 6 будет 4!, но нужно обратить внимание на 0 из этого числа перестановок нужно исключить те числа, которые начинаются с 0. Это всевозможные перестановки цифр 2, 4, 6, их количество равно 3!. Таким образом, число искомых чисел будет равно 4! - 3! = 24 – 6 = 18

Ответ: 18.

Пример 4.

Сколько всего исходов в опыте бросания двух монет одновременно?

Решение:

При бросании первой монеты возможны два исхода (орел или решка), при бросании второй монеты имеем тоже два исхода (орел или решка). По правилу умножения: .

Ответ: 4.

Пример 5.

Сколько всего исходов, если бросают одну и ту же монету два раза?

Решение:

При бросании первый раз у монеты возможны два исхода (орел или решка), при бросании второй раз у монеты имеем тоже два исхода (орел или решка). Тогда .

Ответ: 4.

Пример 6.

Имеется 9 различных книг, 4 из которых — учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом?

Решение:

Сначала рассмотрим все учебники как одну книгу. Тогда на полке надо расставить не 9, а 6 книг. Это можно сделать Р₆ =6! способами. В каждой из полученных комбинаций можно выполнить Р₄ = 4! перестановок учебников. По правилу умножения независимых событий искомое число способов расположения книг на полке равно произведению .

Ответ: 17 280.

Пример 7.

У Пети есть 7 монет по 1 рублю и 3 монеты по 2 рубля. Петя случайным образом выбирает 1 монету номиналом 1 рубль и 1 монету номиналом 2 рубля. Сколькими способами он может это сделать?

Решение:

Для начала выясним, сколькими способами Петя может выбрать 1 монету из 7 имеющихся номиналом 1 рубль:.

Аналогично, найдем число способов выбрать 1 монету номиналом 2 рубля из имеющихся 3 монет: .

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

Ответ: 21.

Пример 8.

В корзине лежат 8 белых шаров и 12 черных. Сколькими способами можно достать из этой корзины 2 белых шара и 2 черных?

Решение:

Всего в корзине n = 8 белых шаров, из которых надо выбрать k = 2 шара. Это можно сделать C₈² = … = 28 различными способами.

Кроме того, в корзине имеется n = 12 черных шаров, из которых надо выбрать опять же k = 2 шара. Число способов сделать это равно

C₁₂² = … = 66.

Поскольку выбор белого шара и выбор черного — события независимые, общее число комбинаций считается по правилу умножения:

28 · 66 = 1848. Как видим, вариантов может быть довольно много.

Ответ: 1848.

Пример 9.

В 10 «Б» классе в среду 7 уроков: алгебра, геометрия, литература, физкультура, русский язык, английский, биология.

А) сколько можно составить различных вариантов расписания на среду?

Б) В скольких расписаниях физкультура будет последним уроком?

В) В скольких вариантах расписания естественно-математические и гуманитарные предметы будут идти блоками, разделенными уроком физкультуры?

Решение:

А) Каждое возможное расписание задает нумерацию семи названных предметов числами 1 2 3 4 5 6 7 в соответствии с порядковым номером урока. Таких нумераций всего 7! = 5040.

Б) 6 уроков (кроме физкультуры) надо распределить по номерам 1 - 6. Всего имеется 6! =720 вариантов.

В) Физкультуру следует поставить 4-м уроком. Расписание будет составлено, как только мы проведем следующие три независимых испытания.

Во-первых, выбор блока (1-й - 3-й или 5-й – 7-й уроки) для гуманитарных предметов. Тут возможны 2 исхода: поставить этот блок до урока физкультуры или после него. Алгебра, геометрия и биология автоматически окажутся в другом блоке.

Во-вторых, выбор порядка гуманитарных предметов в уже выбранном блоке: Р3 = 3! = 6 различных перестановок.

В-третьих, следует посчитать и все перестановки для естественно-математических предметов — их тоже 6. По правилу умножения получаем:

Ответ: 72.

Пример 10.

Собрание из 80 человек выбирает председателя, секретаря и трех членов редакционной комиссии. Сколькими способами это можно сделать?

Решение:

Председателем может быть любой из участников собрания — 80 вариантов. Если председатель выбран, секретарем может оказаться любой из оставшихся 79 человек — 79 вариантов. По правилу умножения получим ( в предположении независимости выбора секретаря и председателя), что выбор председателя и секретаря осуществляется способами.

Если испытание А — выбор председателя и секретаря — завершено, то следует заняться испытанием В — выбором трех членов комиссии из оставшихся 78 участников собрания. Редакционную комиссию выбирают списком, т.е. порядок отбора не имеет значения. Сделать это можно С₇₈³способами. Имеем: . Поскольку А и В предполагаются независимыми, применим правило умножения: способов.

Ответ: 480 800 320.

Пример 11.

Сколько существует всего исходов, если друг за другом из колоды вынимают три карты, возвращая карту обратно (выбор с возвращением).

Решение:

Для первой карты возможно 36 возможностей выбора. Когда первую карту вытащили, то положив ее обратно, в колоде стало снова 36 карт, значит для второй карты тоже 36 возможных исходов. Для третьей карты все то же самое. По правилу умножения имеем n = 36 · 36 · 36 = 46 656.

Ответ: 46 656.

Пример 12.

Из 3-х экземпляров учебника алгебры, 7-ми экземпляров учебника геометрии, 6-ти экземпляров учебника физики надо выбрать один комплект, содержащий все три учебника по одному разу. Сколькими способами это можно сделать?

Решение:

Пусть А — «выбор 1 учебника алгебры», N(A)=3, В — «выбор 1 учебника геометрии», N(B)=7, С — «выбор 1 учебника физики», N(C)=6. Применяя правило умножения, получим: 3·7·6=126 способов.

Ответ: 126.

ПРАВИЛО СЛОЖЕНИЯ:

Если правило умножения оперирует «изолированными» событиями, которые не зависят друг от друга, то в правиле сложения все наоборот. Здесь рассматриваются взаимоисключающие события, которые никогда не случаются одновременно.

Например, «Петя вынул из кармана 1 монету» и «Петя не вынул из кармана ни одной монеты» — это взаимоисключающие события, поскольку вынуть одну монету и при этом не вынуть ни одной невозможно.

Аналогично, события «Выбранный наугад шар — белый» и «Выбранный наугад шар — черный» также являются взаимоисключающими.

Можно сказать, что закон сложения — это логическое «ИЛИ» в комбинаторике, когда нас устраивает любой из взаимоисключающих вариантов. И наоборот, закон умножения — это логическое «И», при котором нас интересует одновременное выполнение и первого, и второго действия.

Пример 13.

В коробке находится 10 шаров: 3 белых, 2 черных, 1 синий и 4 красных. Сколькими способами можно взять из ящика цветной шар?

Решение:

Цветной шар — это синий или красный. Выбрать синий можно одним способом, а выбрать красный шар — 4 варианта, поэтому по правилу сложения: 1 + 4 = 5 способов.

Ответ: 5.

Пример 14.

Из 20 вопросов к экзамену ученик 12 выучил, 5 совсем не смотрел, а в остальных что-то знает, а что-то нет. На экзамене будет три вопроса.

а) Найти количество возможных вариантов билета.

б) Сколько из них тех, в которых ученик знает все вопросы?

в) Сколько из них тех, в которых есть вопросы всех трех типов?

г) Сколько из них тех, в которых ученик выучил большинство вопросов?

Решение:

а) Порядок вопросов в билете не важен. Поэтому возможны вариантов билета.

б) Тут все три вопроса надо выбирать из тех 12, которые выучил ученик: .

в) Билет подобного типа составляется так: следует выбрать независимо друг от друга по одному вопросу – из блока выученных 12 вопросов, из блока тех 5-ти, что он не смотрел и из оставшихся 3-х вопросов. По правилу умножения получим: 12·5·3 = 180.

г) Большинство вопросов из трех – это два или три. Выбрать два из 12 выученных вопросов и один из оставшихся 8 вопросов можно (по правилу умножения) способами. А билеты, в которых все вопросы выучены, уже посчитаны в пункте б), их всего 220. В итоге, применяя правило сложения, получим 528 + 220 = 748 билетов.

Ответ: а) 1140, б) 220, в) 180, г) 748.

Пример 15.

Из класса нужно выделить одного дежурного, мальчика или девочку. Сколько существует способов для выбора дежурного, если в классе 22 девочки и 18 мальчиков?

Решение:

Выбрать одну девочку из 22 мы можем 22 способами, а одного мальчика из 18 можно 18 способами. Тогда выбрать одного дежурного мальчика или девочку можно 18 + 22 = 40 способами.

Ответ: 40.

Пример 16.

В классе из 25 человек 19 красивых и 13 умных. Все дети являются или (и) красивыми, или (и) умными. Сколькими способами можно выбрать 5 человек среди красивых и умных?

Решение:

Пусть Х – количество и красивых и умных, тогда применим 2-ю формулу сложения: 25 = 19 + 13 – Х, откуда найдем Х = 32 – 25 = 7 человек и красивых и умных. Порядок не важен, тогда .

Ответ: 21.

Пример 17.

В корзине лежат 9 черных шаров и 7 красных. Мальчик достает 2 шара одинакового цвета. Сколькими способами он может это сделать?

Решение:

Если шары одинакового цвета, то вариантов немного: оба они либо черные, либо красные. Очевидно, что эти варианты — взаимоисключающие.

В первом случае мальчику предстоит выбирать k = 2 черных шара из n = 9 имеющихся. Число способов сделать это равно C₉² = … = 36.

Аналогично, во втором случае выбираем k = 2 красных шара из n = 7 возможных. Число способов равно C₇² = … = 21.

Осталось найти общее количество способов. Поскольку варианты с черными и красными шарами — взаимоисключающие, по закону сложения имеем: X = 36 + 21 = 57.

Ответ: 57

Пример 18.

В ларьке продаются 15 роз и 18 тюльпанов. Ученик 9-го класса хочет купить 3 цветка для своей одноклассницы, причем все цветы должны быть одинаковыми. Сколькими способами он может составить такой букет?

Решение:

По условию, все цветы должны быть одинаковыми. Значит, будем покупать либо 3 розы, либо 3 тюльпана. В любом случае, k = 3.

В случае с розами придется выбирать из n = 15 вариантов, поэтому число сочетаний равно C₁₅³ = … = 455. Для тюльпанов же n = 18, а число сочетаний — C₁₈³ = … = 816.

Поскольку розы и тюльпаны — это взаимоисключающие варианты, работаем по закону сложения. Получаем общее число вариантов X = 455 + 816 = 1271. Это и есть ответ.

Ответ: 1271.

Пример 19.

Встретились 11 футболистов и 6 хоккеистов и стали играть друг с другом по одному разу в шашки. Сколько было встреч:

а) между футболистами,

б) между хоккеистами,

в) между теми и другими,

г) всего?

Решение:

а) .

б) .

в) Тут надо действовать по правилу умножения. Одно испытание — выбор футболиста, а другое испытание — выбор хоккеиста. Испытания предполагаются независимыми, и у них соответственно 11 и 6 исходов. Значит, получится 11 · 6 = 66 игр.

г) Можно сложить все предыдущие ответы: 55 + 15 + 66 = 136, но можно использовать формулу: .

Дополнительные условия и ограничения

Очень часто в тексте задачи присутствуют дополнительные условия, накладывающие существенные ограничения на интересующие нас сочетания. Сравните два предложения:

1. Имеется набор из 5 ручек разных цветов. Сколькими способами можно выбрать 3 ручки для обводки чертежа?

2. Имеется набор из 5 ручек разных цветов. Сколькими способами можно выбрать 3 ручки для обводки чертежа, если среди них обязательно должен быть красный цвет?

Чувствуете разницу? В первом случае мы вправе брать любые цвета, какие нам нравятся — дополнительных ограничений нет. Во втором случае все сложнее, поскольку мы обязаны выбрать ручку красного цвета (предполагается, что она есть в исходном наборе).

Очевидно, что любые ограничения резко сокращают итоговое количество вариантов. Ну и как в этом случае найти число сочетаний? Просто запомните следующее правило:

Другими словами, если из 5 ручек надо выбрать 3, при этом одна из них должна быть красной, то выбирать придется из n = 5 – 1 = 4 элементов по k = 3 – 1 = 2 элемента. Таким образом, вместо C₅³ надо считать C₄².

Теперь посмотрим, как это правило работает на конкретных примерах:

Пример 20.

В группе из 20 студентов, среди которых 2 отличника, надо выбрать 4 человека для участия в конференции. Сколькими способами можно выбрать этих четверых, если отличники обязательно должны попасть на конференцию?

Решение:

Итак, есть группа из n = 20 студентов. Но выбрать надо лишь k = 4 из них. Если бы не было дополнительных ограничений, то количество вариантов равнялось числу сочетаний C₂₀⁴.

Однако нам поставили дополнительное условие: 2 отличника должны быть среди этих четырех. Таким образом, согласно приведенному выше правилу, мы уменьшаем числа n и k на 2. Имеем: .

Ответ: 153.

Пример 21.

У Пети в кармане есть 8 монет, из которых 6 монет по рублю и 2 монеты по 10 рублей. Петя перекладывает какие-то три монеты в другой карман. Сколькими способами Петя может это сделать, если известно, что обе монеты по 10 рублей оказались в другом кармане?

Решение:

Итак, есть n = 8 монет. Петя перекладывает k = 3 монеты, из которых 2 — десятирублевые. Получается, что из 3 монет, которые будут переложены, 2 уже зафиксированы, поэтому числа n и k надо уменьшить на 2. Имеем: .

Ответ: 6.

Бином Ньютона

Бином Ньютона — это формула, представляющая выражение ( a + b )n при положительном целом n в виде многочлена:

.

Заметим, что сумма показателей степеней для a и b постоянна и равна n.

Числа С_n⁰,C_n¹, C_n², …, C_n-1ⁿназываются биномиальными коэффициентами.

Запишем известные нам формулы в виде:

Знаком умножения отделены числовые коэффициенты при одночленах. Заметим, что 1 = С₃⁰, 3 = С₃¹, 3 = С₃², 1 = С₃³ (в формуле куба суммы).

Для чисел С_n^k имеется красивый и удобный способ их записи в виде треугольной таблицы. Ее называют треугольником Паскаля:

Их можно вычислить, применяя только сложение, если пользоваться следующей схемой. В верхней строке пишем две единицы. Все последующие строки начинаются и заканчиваются единицей. Промежуточные числа в этих строках получаются суммированием соседних чисел из предыдущей строки.

Некоторые биномиальные формулы полезно запомнить:

Замечание. Сумма коэффициентов в разложении (a + b )n равна 2n.

Пример 22.

Разложить выражение: ( a + b )⁷.

Мы можем получить результат моментально, используя таблицу:

Для того чтобы получит формулу бинома Ньютона для 3-х и более слагаемых в скобках, необходимо вспомнить формулы комбинаторики, использующие повторения.

Пример 23.

Сколькими способами можно разложить 28 различных предметов по четырем различным ящикам, так, чтобы в каждом ящике, оказалось, по 7 предметов?

Решение:

способов.

Ответ: 189 635 846 400.

В примере 11 было существенно, что ящики можно отличить друг от друга (например, они покрашены в разные цвета).

Пример 24.

Сколькими способами можно положить 28 различных открыток в 4 одинаковых конверта так, чтобы в каждом конверте лежало по 7 открыток?

Решение:

Сначала пометим конверты цифрами 1, 2, 3, 4. Тогда согласно примеру 18 число различных раскладок равно P(7,7,7,7). После этого сотрем пометки. Теперь конверты можно произвольным образом переставлять друг с другом, не меняя результата раскладки (ведь теперь они неотличимы друг от друга). Так как число различных перестановок четырех конвертов равно Р4 = 4!, то число раскладок уменьшается в 4! Раз, и потому оно равно

Ответ: 7 901 493 600.

Легко доказать, используя в формулу числа сочетаний, что C_n^k=C_n^n-k.

Заметим, что так как

,

То формулу бинома Ньютона можно записать следующим образом:

.

Такая запись обобщается на случай большего числа слагаемых в скобке. Именно для любых k и t верна формула

,

где сумма распространяется на все числовые кортежи (k₁,k₂,…,k_n ) из неотрицательных целых чисел, такие, что k=k₁ + k₂ + … + k_t .

Замечание. Сумма коэффициентов в разложении (a₁ + a₂ + … + a_t)k равна t^k.

Пример 25.

Раскрыть скобки в выражении (a+b+c)³.

Решение:

Ответ имеет вид:

,

где сумма распространяется на все кортежи (k₁,k₂,k₃ ) такие, что 3=k₁ + k₂ + k₃ .

Ими являются кортежи (3,0,0,), (0,3,0), (0,0,3), (2,1,0), (2,0,1), (1,2,0), (1,0,2), (0,1,2), (0,2,1), (1,1,1). Так как

то получим ответ:

Пример 26.

Найти сумму коэффициентов в разложении (a + b + c)⁴.

Решение:

Зная, что сумма коэффициентов в разложении (a + b + c)⁴ равна 3⁴=81.

Ответ: 81.

Пример 27.

Найти сумму коэффициентов в разложении (a + b + c + d)⁵.

Решение:

Зная, что сумма коэффициентов в разложении (a + b + c + d)⁵ равна 4⁵ = 1024.

Ответ: 1024.

Перейти к выполнению теста: Тест. Формулы числа сочетаний. Бином Ньютона