Сочетания

  • 6 мин чтения
  • Послушать — 5 мин
  • 17 карточек

Алгебра, 9 класс · Л. Г. Петерсон, Н. Х. Агаханов, А. Ю. Петрович, О. К. Подлипский, М. В. Рогатова, Б. В. Трушин · § 1. Элементы комбинаторики и теории вероятностей

Иногда из n различных элементов выбирают k, но порядок выбранных не важен: выбрать в жюри Петрова, Орлову и Волкова — то же самое, что выбрать Волкова, Петрова и Орлову.

Определение. Набор из k элементов, взятых из n-элементного множества без учёта порядка (0 ≤ k ≤ n), называется сочетанием из n по k. Число сочетаний обозначают C_n^k (от французского combinaison).

Как найти C_n^k. Упорядоченных наборов (размещений) A_n^k. Каждый неупорядоченный набор встречается среди них P_k = k! раз — столько способов переставить его элементы. Поэтому

C_n^k = (A_n^k)/(k!) = (n(n - 1) · … · (n - k + 1))/(k!) = (n!)/(k! · (n - k)!).

Пример 1. Сколькими способами из 9 участников кружка можно выбрать 4 на олимпиаду? Порядок не важен: C₉⁴ = (9 · 8 · 7 · 6)/(1 · 2 · 3 · 4) = 126.

Пример 2. На окружности 12 точек. Сколько хорд с концами в этих точках? Хорда задаётся парой точек без порядка: C₁₂² = (12 · 11)/2 = 66.

Размещения или сочетания? Спроси себя: если переставить выбранные элементы, получится новый вариант? Да — размещения (места, роли, порядок); нет — сочетания (команда, набор, комиссия).

Свойства. C_n⁰ = C_nⁿ = 1, C_n¹ = n, C_n^k = C_n⁽n - k) (выбрать k элементов — то же, что выбрать n - k, которые не возьмём), C_n^k + C_n⁽k + 1) = C₍n + 1)⁽k + 1) — по этому правилу строится треугольник Паскаля, например C₈² + C₈³ = 28 + 56 = 84 = C₉³. Сумма C_n⁰ + C_n¹ + … + C_nⁿ = 2ⁿ — это число всех подмножеств n-элементного множества: для n = 6 получаем 64. Числа C_n^k называют биномиальными коэффициентами.

Типичная ошибка — делить на k! там, где порядок важен (места, должности), или не делить там, где не важен (команда, набор).

Зачем это

1 / 17

Порядок не важен

Иногда из n различных элементов выбирают k, но порядок выбранных не важен.

Выбрать в жюри Петрова, Орлову и Волкова — то же самое, что выбрать Волкова, Петрова и Орлову: жюри одно и то же.

Определение

2 / 17

Сочетание

Набор из k элементов, взятых из n-элементного множества без учёта порядка (0 ≤ k ≤ n), называют сочетанием из n по k.

Число сочетаний обозначают C_n^k (от французского combinaison).

Жюри из 3 человек, выбранное из 5, — сочетание из 5 по 3.

Разбор

3 / 17

Почему делим на k!

Сколько способов выбрать 2 буквы из А, Б, В, Г, если порядок не важен?

  1. Размещения

    Упорядоченных пар A₄² = 4 · 3 = 12: АБ, БА, АВ, ВА, …

  2. Повторы

    Каждая пара встречается P₂ = 2! = 2 раза: АБ и БА — одна пара.

  3. Ответ

    12 : 2 = 6: АБ, АВ, АГ, БВ, БГ, ВГ.

Формула

4 / 17

Число сочетаний

C_n^k = (A_n^k)/(k!) = (n!)/(k! · (n - k)!)

Или: C_n^k = (n(n - 1) · … · (n - k + 1))/(k!)

Упорядоченных наборов A_n^k, и каждый неупорядоченный встречается среди них k! раз.

Проверь себя

5 / 17

Два дежурных

Из 6 учеников выбирают 2 дежурных; обязанности у них одинаковые.

Сколько способов?

301536
Ответ и объяснение

C₆² = (6 · 5)/(1 · 2) = 15.

Пример

6 / 17

Команда на олимпиаду

Сколькими способами из 9 участников кружка можно выбрать 4 на олимпиаду?

Порядок не важен — это сочетания:

C₉⁴ = (9 · 8 · 7 · 6)/(1 · 2 · 3 · 4) = 126

Пример

7 / 17

Хорды окружности

На окружности 12 точек. Сколько хорд с концами в этих точках?

Хорда задаётся парой точек, порядок не важен: хорда AB — то же, что BA.

C₁₂² = (12 · 11)/2 = 66

Правило

8 / 17

Размещения или сочетания?

Спроси себя: если переставить выбранные элементы, получится новый вариант?

  • Да — размещения A_n^k: места, роли, порядок.
  • Нет — сочетания C_n^k: команда, набор, комиссия.

Проверь себя

9 / 17

Председатель и секретарь

Из 10 человек выбирают председателя и секретаря собрания.

Что здесь считать?

C₁₀²A₁₀²10²
Ответ и объяснение

Роли разные, порядок важен: A₁₀² = 10 · 9 = 90.

Свойства

10 / 17

Свойства сочетаний

  • C_n⁰ = C_nⁿ = 1, C_n¹ = n
  • C_n^k = C_n⁽n - k)
  • C_n^k + C_n⁽k + 1) = C₍n + 1)⁽k + 1)
  • C_n⁰ + C_n¹ + … + C_nⁿ = 2ⁿ

Числа C_n^k называют биномиальными коэффициентами.

Свойство

11 / 17

Взять или оставить

C_n^k = C_n⁽n - k)

Выбрать k элементов — то же, что выбрать n - k, которые не возьмём.

C₁₂¹⁰ = C₁₂² = 66

Свойство

12 / 17

Правило сложения

C_n^k + C_n⁽k + 1) = C₍n + 1)⁽k + 1)

C₈² + C₈³ = 28 + 56 = 84 = C₉³

По этому правилу строится треугольник Паскаля.

Наглядно

13 / 17

Треугольник Паскаля

1 ; 1 1 ; 1 2 1 ; 1 3 3 1 ; 1 4 6 4 1 ; 1 5 10 10 5 1

Строки нумеруем с 0: в строке n стоят C_n⁰, C_n¹, …, C_nⁿ; каждое число — сумма двух над ним.

Свойство

14 / 17

Все подмножества

C_n⁰ + C_n¹ + … + C_nⁿ = 2ⁿ

Это число всех подмножеств n-элементного множества.

n = 3: 1 + 3 + 3 + 1 = 8 = 2³; n = 6: 2⁶ = 64.

Частая ошибка

15 / 17

Делить или не делить

Капитан и заместитель из 8: «C₈² = 28» — неверно! Роли разные: A₈² = 56.

Двое в команду из 8: «A₈² = 56» — неверно! Каждая пара посчитана дважды: C₈² = 28.

На k! делим, только если порядок не важен.

Проверь себя

16 / 17

Быстрый счёт

C₂₀¹⁸

Чему равно?

19038020
Ответ и объяснение

C₂₀¹⁸ = C₂₀² = (20 · 19)/2 = 190.

Главное

17 / 17

Главное

  • Сочетание из n по k — k элементов без учёта порядка.
  • C_n^k = (A_n^k)/(k!) = (n!)/(k! · (n - k)!)
  • C_n^k = C_n⁽n - k), C_n^k + C_n⁽k + 1) = C₍n + 1)⁽k + 1)
  • C_n⁰ + C_n¹ + … + C_nⁿ = 2ⁿ
  • Переставили — новый вариант? Да — A_n^k, нет — C_n^k.

Проверь себя: тест по теме

Несколько заданий по этой теме из того же учебника. Каждый ответ проверяется сразу, а начать можно без регистрации.

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест