Как найти количество вариантов комбинаций без повторений

Сочетания

1. Сочетания без повторений
2. Сочетания с повторениями
3. Биномиальные коэффициенты и их свойства
4. Примеры

п.1. Сочетания без повторений

Сочетаниe без повторений – это неупорядоченная ⟨n,k⟩-выборка без повторений,     k ≤ n. Общее количество сочетаний без повторений: $$ mathrm{ C_n^k=frac{n!}{(n-k)!k!} } $$

Внимание! Главным отличием сочетаний от размещений является неупорядоченность выборок. Если для размещения выборки (a,b)≠(b,a) не равны, то для сочетания (a,b)=(b,a) – одна и та же выборка.
Сочетания используются тогда, когда порядок выборки не важен.

Например:
Из 10 программистов нужно отобрать 4 для участия в проекте. Сколькими способами это можно сделать?
$$mathrm{ n = 10, k=4 }$$ В данном случае, порядок отбора не важен (выборка неупорядоченная); каждый кандидат может войти только один раз в выборку (выборка без повторений). Поэтому рассматриваем неупорядоченные ⟨10,4⟩ –выборки без повторений. Количество способов отбора равно: $$mathrm{ C_{10}^4=frac{10!}{6! 4!}=frac{10cdot 9cdot 8cdot 7}{1cdot 2cdot 3cdot 4}=210 }$$ Ответ: 210.

п.2. Сочетания с повторениями

Сочетаниe с повторениями – это неупорядоченная ⟨n,k⟩-выборка с повторениями. Общее количество сочетаний с повторениями: $$ mathrm{ overline{C}_n^k=frac{(n+k-1)!}{(n-1)k!} } $$

$$ mathrm{ overline{C}_n^k=C_{n+k-1}{k} } $$

Например:
Нужно отобрать 4 программистов для участия в проекте. Многочисленных претендентов можно разделить на две категории: желающих работать удаленно и предпочитающих работу в офисе. Сколько всего комбинаций из любителей офиса и удалёнки может оказаться в выбранной четвёрке? $$mathrm{ n = 2, k=4 }$$ Порядок отбора не важен; кандидатов из каждой категории может быть несколько или ни одного. Поэтому рассматриваем неупорядоченные ⟨2,4⟩ –выборки с повторениями: $$ mathrm{ overline{C}_2^4=frac{(2+4-1)!}{(2-1)4!}=frac{5!}{4!}=5 } $$ Всего – 5 комбинаций: OOOO,OOOD,OODD,ODDD,DDDD
где O – любитель офиса; D – любитель удалёнки. Напоминаем, что порядок не важен – важен только состав группы.
Ответ: 5.

п.3. Биномиальные коэффициенты и их свойства

Подробно о биноме – см. §28 справочника для 7 класса.
Для n-й степени бинома справедливо выражение: $$ mathrm{ (apm b)^n=a^n+C_n^1a^{n-1}bpm C_n^2a^{n-2}b^2+…+C_n^{n-1}b^n } $$ где (mathrm{C_n^k}) – биномиальные коэффициенты, к оторые одновременно являются количествами сочетаний без повторений из n по k: $$ mathrm{ C_n^k=frac{n!}{(n-k)!k!} } $$ Таким образом, биномиальные коэффициенты можно определять как с помощью треугольника Паскаля, так и с помощью данной формулы.
Заметим, что в литературе также часто встречается обозначение (mathrm{left(_k^nright)}) для биномиальных коэффициентов (mathrm{left(C_n^kright)}).

Свойства биномиальных коэффициентов

Свойство симметрии

$$mathrm{ C_n^k=C_n^{n-k} }$$

Свойство Паскаля

$$mathrm{ C_n^k=C_{n-1}^{k-1}+C_{n-1}^k }$$

Замена индексов

$$mathrm{ C_n^mC_m^{n-k}=C_{n}^{k}C_{k}^{n-m} }$$

Вынесение за скобки

$$mathrm{ C_n^k=frac{n}{k}C_{n-1}^{k-1} }$$

Рекуррентные формулы

begin{gather*}mathrm{ C_n^k=frac{n-k+1}{k}C_{n}^{k-1} }\ mathrm{ C_n^k=frac{n}{n-k}C_{n-1}^k } end{gather*}

Свойство суммы

$$mathrm{ C_n^0+C_n^1+C_n^2+…+ C_n^n=sum_{k=0}^nC_n^k=2^n }$$

Свойство разности

$$mathrm{ C_n^0-C_n^1+C_n^2-…+(-1)^nC_n^n=sum_{k=0}^n(-1)^kC_n^k=0 }$$

Свойства максимума

Если n – четное, то максимальное значение (mathrm{C_n^k}) имеет при (mathrm{k=frac{n}{2}}).
Если n – нечетное, то максимальное значение имеют два коэффициента (mathrm{C_n^k}), при (mathrm{k=frac{n-1}{2}}) и (mathrm{k=frac{n+1}{2}})

Свёртка Вандермонда

$$mathrm{ sum_{r=0}^kC_n^rC_m^{k-r}=C_{n+m}^k }$$

Сумма квадратов

$$mathrm{ sum_{k=0}^n(C_n^k)^2=C_{2n}^n }$$

Взвешенное суммирование

begin{gather*} mathrm{ sum_{k=0}^nnC_n^k=n2^{n-1} }\ mathrm{ sum_{k=0}^nn^2C_n^k=n(n+1)2^{n-2} } end{gather*}

Связь с числами Фибоначчи

$$mathrm{ C_n^0+C_{n-1}^1+…+C_{n-k}^{k}+…+C_{0}^{n}=F_{n+1} }$$

п.4. Примеры

Пример 1. На столе лежит 10 яблок и 5 груш.
1) Сколькими способами можно выбрать 7 фруктов?
2) Сколькими способами можно выбрать 7 фруктов, чтобы среди них было 3 груши?

1) Всего у нас n = 10 + 5 = 15 фруктов. Нужно выбрать k = 7 фруктов.
Порядок выбора не важен, т.е. выборка неупорядоченная. Находим: $$ mathrm{ C_n^k=C_{15}^7=frac{15cdot 14cdot 13cdot 12cdot 11cdot 10cdot 9}{1cdot 2cdot 3cdot 4cdot 5cdot 6cdot 7}=6435 } $$ Существует 6435 способов выбрать 7 фруктов из 15.

2) Выбираем 4 яблока из 10 и 3 груши из 5.
Для яблок: $$ mathrm{ C_{10}^4=frac{10cdot 9cdot 8cdot 7}{1cdot 2cdot 3cdot 4}=210 } $$ Для груш: $$ mathrm{ C_3^5=C_{5}^2=frac{5cdot 4}{1cdot 2}=10 } $$ По правилу произведения, общее количество способов выбрать 4 яблока и 3 груши: $$ mathrm{ C_{10}^3cdot C_{5}^3=210cdot 10=2100 } $$ Ответ: 1) 6435; 2) 2100.

Пример 2. В кондитерском магазине продаётся 4 вида пирожных. Сколькими способами можно купить 7 пирожных? $$ mathrm{ n=4, k=7 } $$ Порядок выбора пирожных неважен – выборка неупорядоченная; пирожные одного вида могут повторяться. Значит, находим количество сочетаний с повторениями: $$ mathrm{ overline{C}_4^7=C_{7+4-1}^7=C_{10}^7=C_{10}^3=frac{10cdot 9cdot 8}{1cdot 2cdot 3}=120 } $$ Ответ: 120

Пример 3. Рота состоит из 3 офицеров, 6 сержантов и 15 рядовых. Сколькими способами можно выбрать из них отряд, состоящий из 1 офицера, 2 сержантов и 5 рядовых?

По всем трём множествам делаем неупорядоченную выборку (т.е., сочетания) без повторений.
Выбираем офицеров: (mathrm{C_3^1=frac31=3})
Выбираем сержантов: (mathrm{C_6^2=frac{6cdot 5}{1cdot 2}=15})
Выбираем рядовых: (mathrm{C_{15}^6=frac{15cdot 14cdot 13cdot 12cdot 11}{1cdot 2cdot 3cdot 4cdot 5}=3003})
По правилу произведения, отряд можно выбрать:
(mathrm{3cdot 15cdot 3003=135135}) способами.
Ответ: 135135.

Пример 4. Найдите сумму
a) (mathrm{C_6^1+C_6^2+C_6^3+C_6^4+C_6^5+C_6^6})
По свойству суммы (mathrm{sum_{k=0}^6C_6^k=2^6}). Получаем: $$ mathrm{ C_6^1+C_6^2+C_6^3+C_6^4+C_6^5+C_6^6=sum_{k=0}^6C_6^k-C_6^0=2^6-1=64-1=63 } $$
б) (mathrm{C_n^1+6C_n^2+6C_n^3}) $$ mathrm{ C_n^1=n, C_n^2=frac{n(n-1)}{2}, C_n^3=frac{n(n-1)(n-2)}{6} } $$ Получаем begin{gather*} mathrm{ C_n^1+6C_n^2+6C_n^3=n+6cdot frac{n(n-1)}{2}+6cdot frac{n(n-1)(n-2)}{6}=}\ mathrm{ =n(1+3(n-1)+(n-1)(n-2))=n(3n-2+n^2-3n+2)=n^3 } end{gather*} Ответ: а) 63; б) n³.

Пример 5. Рассчитайте все (mathrm{C_{10}^k}) по рекуррентной формуле (mathrm{C_{n}^k=frac{n-k+1}{k}C_n^{k-1}}).
Постройте график (mathrm{C_{10}^k(k)}). Сделайте выводы.

Начальное значение (mathrm{C_{10}^0=1}).

0 $$mathrm{ C_{10}^0=1 }$$ 1 $$mathrm{ C_{10}^1=frac{10-1+1}{1}C_{10}^0=10 }$$ 2 $$mathrm{ C_{10}^2=frac{10-2+1}{2}C_{10}^1=45 }$$ 3 $$mathrm{ C_{10}^3=frac{10-3+1}{3}C_{10}^2=120 }$$ 4 $$mathrm{ C_{10}^4=frac{10-4+1}{4}C_{10}^3=210 }$$ 5 $$mathrm{ C_{10}^4=frac{10-5+1}{5}C_{10}^4=252 }$$ 6 $$mathrm{ C_{10}^6=frac{10-6+1}{6}C_{10}^5=210 }$$ 7 $$mathrm{ C_{10}^7=frac{10-7+1}{7}C_{10}^6=120 }$$ 8 $$mathrm{ C_{10}^6=frac{10-8+1}{8}C_{10}^7=45 }$$ 9 $$mathrm{ C_{10}^9=frac{10-9+1}{9}C_{10}^8=10 }$$ 10 $$mathrm{ C_{10}^{10}=frac{10-10+1}{10}C_{10}^9=1 }$$

На графике видно симметрию коэффициентов: (mathrm{C_{10}^k=C_{10}^{10-k}}).
Т.к. n = 10 – чётное, максимальный коэффициент при (mathrm{k=frac{n}{2}=5, C_{10}^5=252}).
Можем также проверить свойство суммы: (mathrm{sum_{k=0}^{10}C_{10}^k=1024=2^{10}}).

Рейтинг пользователей

Сочетания без повторений

Похожие калькуляторы

Для
построения соответствующих математических
моделей комбинаторных задач будем
использовать математический
аппарат теории множеств.
Может случиться, что в данном множестве
порядок следования элементов не важен,
а важен только состав множества. Но есть
задачи, в которых прядок элементов
является существенным.

Определение
1: Порядок
во множестве
изэлементов – это нумерация его элементов
натуральными числами, т.е. отображение
множествана множество.

Определение
2: Множество
с заданным на нем порядком называется
упорядоченным
множеством.

Очевидно,
что множество, содержащее более одного
элемента, можно упорядочить не единственным
способом.

Например,
из двух букв
иможно построить упорядоченное множество
двумя различными способами:

и
.

Три
буквы
,иможно расположить в виде последовательности
шестью способами:

,
,,,,.

Для четырех букв
путем перебора получим уже 24 различных
упорядоченных последовательностей.

Упорядоченные
последовательности элементов некоторого
множества можно рассматривать как
распределения или расстановки этих
элементов в последовательности.

Определение
3: Пусть
дано конечное множество
изэлементов. Всякий набор изэлементов данного множества (при этом
элементы в наборе могут и повторяться)
будем называть–расстановками.

Через
понятие расстановки вводятся основные
определения комбинаторики: сочетания,
размещения и перестановки.
При этом каждое из этих понятий может
быть с повторениями и без повторений.
В данном параграфе будут рассмотрены
комбинаторные формулы без повторений.

Перестановки
без повторений.

Определение
4: Пусть
– конечное множество изэлементов.Перестановками
из
различных элементов множестваназываются все расположенияэлементов в определенном порядке.
Обозначается:(от французского словаpermutation
– перестановка).

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

Определение
5: Различные
упорядоченные множества, которые
отличаются лишь порядком элементов,
называются перестановками
этого множества.

Последнее определение
сформулировано с позиции теории множеств.

Определение
6: Произведение
последовательных натуральных чисел в
математике обозначаюти называютфакториалом.

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

Теорема
1: Число
перестановок из
различных элементов вычисляется по
формуле:

(1)

Доказательство.
Рассмотрим произвольное множество из
элементов. Построим всевозможные
расстановки из этихэлементов.
На первое
место
расстановки можно поставить любой из
элементов (способов выбора первого элемента). После
того, как первый элемент выбран и
независимо как он выбран, второй элемент
можно выбратьспособом. Для выбора третьего элемента
остаетсяспособа и т.д. Последний элемент выбирается
соответственно одним способом. Тогда,
в силу комбинаторного принципа умножения,
количество таких расстановок будет
равно:

Теорема доказана.

Пример
1: Сколькими
способами трое друзей могут занять в
кинотеатре места с номерами 1, 2 и 3.

Решение.
Количество искомых способов будет равно
числу перестановок без повторений из
трех элементов:
способов. При необходимости эти способы
можно перебрать.

Перестановки
букв некоторого слова называют
анаграммами.
Открытые еще в ІІІ
веке до
нашей эры греческим грамматиком
Ликофроном анаграммы до сих пор привлекают
внимание языковедов, поэтов и любителей
словесности. Мастера словесных игр
помимо эрудиции и большого запаса слов
знают много секретов, связанных с
комбинаторными навыками, один из которых
– анаграммы. Часто требуется среди всех
перестановок выбрать те, которые обладают
определенным свойством. Например, среди
анаграмм слова «крот»,
которых всего
,
только одна, не считая самого слова«крот»,
имеет смысл в русском языке – «корт».

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

Теорема
2: Число
круговых перестановок из
различных элементов равно

Пример
2: Сколькими
способами 7 детей могут стать в хоровод?

Решение.
Число линейных перестановок 7 детей
будет равно
.
Если хоровод уже сформирован, тогда для
него существует 7 круговых перестановок,
переходящих друг в друга при повороте.
Эти перестановки не должны быть засчитаны,
поэтому круговых перестановок из 7
элементов будет.

Размещения без
повторений.

Определение
7: Пусть
имеется
различных предметов. Расстановки изэлементов поэлементов ()
называютсяразмещениями
без повторений.
Обозначают:
.
Здесь имеется в виду, что элементы в
расстановках не повторяются.

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

Приведем
еще одно определение размещений,
эквивалентное исходному, более простое
для понимания.

Определение
8: Конечные
упорядоченные множества называются
размещениями.

Теорема
3: Количество
всех размещений из
элементов поэлементов без повторений вычисляется
по формуле:

. (2)

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

Выбор
элементов осуществляется поэтапно.
Первый элемент расстановки можно выбрать
различными способами. Тогда из оставшихся
элементов множествавторой элемент расстановки выбираетсяспособом. Для выбора третьего элемента
возможноспособа и т.д. Тогда для выбора–
го элемента имеемспособ. Следовательно, согласно правилу
умножения, количество таких расстановок
будет равно:

.

По
определению, такие расстановки являются
размещениями. Что и требовалось доказать.

Пример
3: Собрание
из 25 человек выбирает президиум из 3
человек: 1) председатель, 2) заместитель,
3) секретарь. Сколько возможно вариантов
выбора президиума?

Решение.
Выбирая трех человек из 25, замечаем, что
важен порядок выбора, поэтому количество
президиумов будет равно:

.

Замечание:
Число размещений без повторений можно
также находить по формуле:

. (3)

Если
в знаменателе дроби из формулы (3)
,
то принято считать.

Замечание:
Формула (3) отличается компактностью,
но при решении задач удобнее использовать
формулу (2). Дробь, стоящая в правой части
формулы (3), может быть сокращена до
целого числа. Это число равно числу из
правой части формулы (2).

Пример
4: Сколько
можно составить двухбуквенных слов
(буквы не повторяются) из 33 букв русского
алфавита?

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

Тогда количество
различных комбинаций из 2 букв, выбранных
из 33 букв алфавита, будет равно:

.

В
данном случае важен порядок букв. Если
поменять 2 буквы в слове, то получим
новое слово.

Замечание:
Перестановка без повторений – это
частный случай размещений без повторений
при
.
Можно сказать, что перестановка изэлементов – это размещение изэлементов поэлементов:

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

Сочетания без
повторений.

Определение
9: Сочетания
без
повторений из
элементов некоторого множества поэлементов ()
– это расстановки, отличающиеся друг
от другасоставом,
но не порядком
элементов. Обозначают:
(от французского словаcombinaison
– сочетание).

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

С
точки зрения теории множеств определение
сочетаний можно сформулировать иначе.

Определение
10: Конечные
неупорядоченные множества называются
сочетаниями.

Таким образом,
сочетания – это такая выборка элементов,
при которой их порядок совершенно не
важен.

Сочетаний
из
элементов поэлементов должно быть меньше, чем
соответствующих размещений. Это следует
из того, что не надо засчитывать
расстановки одинакового состава.

Теорема
4: Число
сочетаний
находится по следующей формуле:

. (4)

Доказательство.
Если из произвольного
-элементного
множества выбраныэлементов, то их можно пронумеровать
номерамичислом способов, равным.
Оставшиесяэлементов можно занумеровать номерами,,
…,всегоспособами. Кроме того, сам отборэлементов изэлементов можно осуществитьспособами. Таким образом, мы получили

вариантов нумерации полного множества
из
элементов, которых всего.
Поэтому имеем,
откуда получаем:

.

Теорема доказана.

Замечание:
Дробь, стоящая в правой части (4), может
быть сокращена до целого числа.

Из формулы числа
сочетаний следует:

,
,.

Формула
(4) может быть преобразована к виду:
.
Отсюда видно, что число размещенийвраз больше числа соответствующих
сочетаний.
Другими словами, чтобы посчитать все
сочетания,
нужно исключить из всех размещенийподмножества, отличающиеся порядком
(их будетштук), т.е.делят на.

Пример
5: Сколькими
способами можно выбрать 3 различные
краски из имеющихся пяти.

Решение.
Порядок выбора красок не важен. Важно
только какие краски выбраны. Поэтому
количество вариантов равно:
.

Пример
6: Сколькими
способами можно пошить трехцветные
полосатые флаги, если имеется материал
пяти различных цветов.

Решение.
Порядок выбора полос важен, поэтому
количество таких флагов равно:
.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #