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

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

Задачи, в которых речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Область математики, в которой рассматриваются комбинаторные задачи, называют комбинаторикой.

Комбинаторика – область математики, в которой рассматриваются задачи о тех или иных комбинациях объектов.

Правило суммы

Пусть имеется n попарно непересекающихся множеств A₁, A₂,…A_n, содержащих m₁, m₂,…, m_n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно

m₁ m₂ … m_n.

Пример. На курсе имеется 3 группы. В первой – 25 человек, во второй – 30, в третьей – 20. Сколькими способами из них можно выбрать одного студента?

Решение. Из первой группы одного человека можно выбрать 25 способами, из второй – 30, из третьей – 20. Чтобы найти ответ, нужно сложить все эти способы:

25 30 20=75.

Ответ: выбрать одного студента из трех групп можно 75 способами.

Правило произведения

Пусть имеется ^.n множеств A₁, A₂,…A_n,содержащих m₁, m_2,,…, m_n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества

m₁ּm_{2 ּ}…ּm_n.

Пример. На курсе имеется 3 группы. В первой – 25 человек, во второй – 30, в третьей – 20. Сколькими способами из каждой из них можно выбрать по одному студенту?

Решение. Из первой группы одного человека можно выбрать 25 способами, из второй – 30, из третьей – 20. Чтобы найти ответ, нужно перемножить эти числа:

25ּ30ּ20=15000.

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

^ Если выбираем один элемент из нескольких множеств, то применяем правило суммы.

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

Факториаломчислаn называется последовательное произведение натуральных чисел от единицы до самого числа n:

Примечание: 0!=1.

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

Перестановками из n различных элементов называются размещения из этих n элементов по n. Перестановки — частный случай размещений.

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

Решение. Число способов есть число перестановок из 25 элементов, то есть:

P₂₅ = 25ּ24ּ23ּ…ּ1=25!=1,55ּ10²⁵.

Ответ: расставить в шеренгу студентов группы из 25 человек можно 1,55ּ10²⁵ способами.

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

Различные упорядоченные подмножества по m элементов данного множества, содержащего n элементов, называются размещениями из n по m. Их число равно:

В частности: .

Пример. Из группы, состоящей из 25 человек, надо выбрать шахматную команду из четырех человек на I, II, III и IV доски. Сколькими способами это можно сделать?

Решение. Так как из 25 человек выбираются 4 и порядок важен, то число способов есть число размещений из 25 по 4, то есть:

.

Ответ: выбрать из 25 человек шахматную команду из четырех человек на I, II, III и IV доски можно 303600 способами.

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

Различные неупорядоченные подмножества по m элементов из данного множества, содержащего n элементов, называются сочетаниями из n по m. Их число равно:

В частности, .

Пример. Сколькими способами из группы в 25 человек можно выбрать баскетбольную команду из пяти человек?

Решение. Так как из 25 человек выбираются 5 и порядок не важен, то число способов есть число сочетаний из 25 по 5, то есть:

Ответ: из группы в 25 человек можно выбрать баскетбольную команду 53130 способами.

Рекомендуемые страницы:

poisk-ru.ru

Число размещений без повторений

Число размещений без повторений из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k различными координатами.

Число размещений без повторений находится по формуле:

.

Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?

Количество цифр , размерность вектора с различными координатами

Число размещений с повторениями

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

Число размещений с повторениями находится по формуле:

Пример: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?

Количество букв , размерность вектора

Число перестановок без повторений

Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов.

Число перестановок без повторений находится по формуле:

.

Замечание: Мощность искомого множества А удобно искать по формуле: , гдех – число способов выбрать нужные места;

Пример. Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом?

Всего способов расставить 5 книг на 5-ти местах – равно = 5! = 120.

В задаче х – число способов выбрать два места рядом, х = 4; у – число способов расположить две книги на двух местах, у = 2! = 2; z – число способов расположить остальные 3 книги на оставшихся 3-х местах,  z = 3! = 6. Значит = 48.

Число сочетаний без повторений

Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k

Число сочетаний без повторений находится по формуле:

.

Свойства:

1) ; 2); 3);

4) ; 5); 6).

Пример. В урне 7 шаров. Из них 3 белых. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет ровно один белый.

Всего способов . Чтобы получить число способов выбрать 1 белый шар (из 3-х белых) и 2 черных шара (из 4-х черных), надо перемножить

Упражнения

1. Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

2. В группе из 30 студентов каждый знает, по крайней мере, один иностранный язык – английский или немецкий. Английский знают 22 студента, немецкий – 17. Сколько студентов знают оба языка? Сколько студентов знают немецкий язык, но не знают английский?

3. В 20 комнатах общежития института Дружбы Народов живут студенты из России; в 15 – из Африки; в 20 – из стран Южной Америки. Причем в 7 – живут россияне и африканцы, в 8 – россияне и южноамериканцы; в 9 – африканцы и южноамериканцы; в 3 – и россияне, и южноамериканцы, и африканцы. В скольких комнатах живут студенты: 1) только с одного континента; 2) только с двух континентов; 3) только африканцы.

4. Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике и астрономии. Три спецкурса посещают 10 студентов, по математике и физике – 30 студентов, по математике и астрономии – 25; спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по астрономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?

5. Староста курса представил следующий отчет по физкультурной работе. Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек. При этом, 16 человек одновременно посещают футбольную и баскетбольную секции, 18 – футбольную и шахматную, 17 – баскетбольную и шахматную, 15 человек посещают все три секции. Объясните, почему отчет не был принят.

6. В аквариуме 11 рыбок. Из них 4 красных, остальные золотые. Наугад выбирают 4 рыбки. Сколькими способами это можно сделать? Найти число способов сделать это так, чтобы среди них будет: 1) ровно одна красная; 2) ровно 2 золотых; 3) хотя бы одна красная.

7. В списке 8 фамилий. Из них 4 – женские. Сколькими способами их можно разделить на две равные группы так, чтоб в каждой была женская фамилия?

8. Из колоды в 36 карт выбирают 4 . Сколько способов сделать это так, чтобы: 1) все карты были разных мастей; 2) все карты были одной масти; 3) 2 красные и 2 черные.

9. На карточках разрезной азбуки даны буквы К, К, К, У, У, А, Е, Р. Сколько способов сложить их в ряд так, что бы получилось «кукареку».

10. Даны карточки разрезанной азбуки с буквами О, Т, О, Л, О, Р, И, Н, Г, О, Л, О, Г. Сколько способов сложить их так, что бы получилось слово «отолоринголог».

11. Даны карточки нарезной азбуки с буквами Л, И, Т, Е, Р, А, Т, У, Р, А. Сколько способов сложить их в ряд так, что бы получилось слово «литература».

12. 8 человек становятся в очередь. Сколько способов сделать это так, что бы два определенных человека А и Б оказались: 1) рядом; 2) на краях очереди;

13. 10 человек садятся за круглый стол на 10 мест. Сколькими способами это можно сделать так, чтоб рядом оказались: 1) два определенных человека А и Б; 2) три определенных человека А, Б и С.

14. Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: 1) все цифры были разными; 2) на последнем месте четная цифра.

15. Из 26 букв латинского алфавита (среди них 6 гласных) составляется шестибуквенное слово. Сколькими способами это можно сделать так, чтобы в слове были: 1) ровно одна буква «а»; 2) ровно одна гласная буква; ровно две буквы «а»; в) ровно две гласные.

16. Сколько четырехзначных чисел делятся на 5?

17. Сколько четырехзначных чисел с различными цифрами делятся на 25?

19. Брошены 3 игральные кости. В скольких случаях выпала: 1) ровно 1 «шестерка»; 2) хотя бы одна «шестерка».

20. Брошены 3 игральные кости. В скольких случаях будет: 1) все разные; 2) ровно два одинаковых числа очков.

21. Сколько слов с различными буквами можно составить из алфавита а, в, с, d. Перечислить их все в лексикографическом порядке: abcd, abcd….

studfiles.net

Число сочетаний без повторений

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

Число сочетаний без повторений находится по формуле:

.

Свойства:

1) ; 2); 3);

4) ; 5); 6).

Пример. В урне 7 шаров. Из них 3 белых. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет ровно один белый.

Всего способов . Чтобы получить число способов выбрать 1 белый шар (из 3-х белых) и 2 черных шара (из 4-х черных), надо перемножитьиТаким образом искомое количество способов

Упражнения

1. Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

2. В группе из 30 студентов каждый знает, по крайней мере, один иностранный язык – английский или немецкий. Английский знают 22 студента, немецкий – 17. Сколько студентов знают оба языка? Сколько студентов знают немецкий язык, но не знают английский?

3. В 20 комнатах общежития института Дружбы Народов живут студенты из России; в 15 – из Африки; в 20 – из стран Южной Америки. Причем в 7 – живут россияне и африканцы, в 8 – россияне и южноамериканцы; в 9 – африканцы и южноамериканцы; в 3 – и россияне, и южноамериканцы, и африканцы. В скольких комнатах живут студенты: 1) только с одного континента; 2) только с двух континентов; 3) только африканцы.

4. Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике и астрономии. Три спецкурса посещают 10 студентов, по математике и физике – 30 студентов, по математике и астрономии – 25; спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по астрономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?

5. Староста курса представил следующий отчет по физкультурной работе. Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек. При этом, 16 человек одновременно посещают футбольную и баскетбольную секции, 18 – футбольную и шахматную, 17 – баскетбольную и шахматную, 15 человек посещают все три секции. Объясните, почему отчет не был принят.

6. В аквариуме 11 рыбок. Из них 4 красных, остальные золотые. Наугад выбирают 4 рыбки. Сколькими способами это можно сделать? Найти число способов сделать это так, чтобы среди них будет: 1) ровно одна красная; 2) ровно 2 золотых; 3) хотя бы одна красная.

7. В списке 8 фамилий. Из них 4 – женские. Сколькими способами их можно разделить на две равные группы так, чтоб в каждой была женская фамилия?

8. Из колоды в 36 карт выбирают 4 . Сколько способов сделать это так, чтобы: 1) все карты были разных мастей; 2) все карты были одной масти; 3) 2 красные и 2 черные.

9. На карточках разрезной азбуки даны буквы К, К, К, У, У, А, Е, Р. Сколько способов сложить их в ряд так, что бы получилось «кукареку».

10. Даны карточки разрезанной азбуки с буквами О, Т, О, Л, О, Р, И, Н, Г, О, Л, О, Г. Сколько способов сложить их так, что бы получилось слово «отолоринголог».

11. Даны карточки нарезной азбуки с буквами Л, И, Т, Е, Р, А, Т, У, Р, А. Сколько способов сложить их в ряд так, что бы получилось слово «литература».

12. 8 человек становятся в очередь. Сколько способов сделать это так, что бы два определенных человека А и Б оказались: 1) рядом; 2) на краях очереди;

13. 10 человек садятся за круглый стол на 10 мест. Сколькими способами это можно сделать так, чтоб рядом оказались: 1) два определенных человека А и Б; 2) три определенных человека А, Б и С.

14. Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: 1) все цифры были разными; 2) на последнем месте четная цифра.

15. Из 26 букв латинского алфавита (среди них 6 гласных) составляется шестибуквенное слово. Сколькими способами это можно сделать так, чтобы в слове были: 1) ровно одна буква «а»; 2) ровно одна гласная буква; ровно две буквы «а»; в) ровно две гласные.

16. Сколько четырехзначных чисел делятся на 5?

17. Сколько четырехзначных чисел с различными цифрами делятся на 25?

19. Брошены 3 игральные кости. В скольких случаях выпала: 1) ровно 1 «шестерка»; 2) хотя бы одна «шестерка».

20. Брошены 3 игральные кости. В скольких случаях будет: 1) все разные; 2) ровно два одинаковых числа очков.

21. Сколько слов с различными буквами можно составить из алфавита а, в, с, d. Перечислить их все в лексикографическом порядке: abcd, abcd….

studfiles.net

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

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

Пример 4. Сколько существует различных прямоугольных параллелепипедов, длина каждого ребра которых есть любое число от 1 до 10?

Решение: Всякий параллелепипед определяется тремя взаимно перпендикулярными ребрами и не зависит от их порядка. Тогда применима формула числа сочетаний с повторением: .

Перестановки с повторением

Пусть дано множество X = {x₁, x₂, …, x_r}. Составим кортеж длиной n, в который элемент x₁ входит n₁ раз, x₂ – n₂ раза,…, x_r — n_r раз. Назовем составом этого кортежа новый кортеж (n₁, n₂, …, n_r). Кортежи данного состава называют перестановками с повторением из n₁ элементов х₁, n₂ элементов х₂,…, n_r элементов x_r. Их число выражается формулой

,

где .

Лекция 2. Пространство элементарных событий. Классическое определение вероятности

Реализация некоторой совокупности условий называется испытанием, а результат испытания – событием. События будем обозначать большими латинскими буквами A, B, C, D,… Все события делят на три вида: достоверные, невозможные и случайные.

Достоверным называется событие, которое обязательно произойдет при выполнении данного комплекса условий.

Пример 1. При бросании игральной кости выпало число очков не более 6 – есть достоверное событие.

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

Пример 2. При бросании игральной кости выпало число очков равное 8 – есть событие невозможное.

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

Пример 3. При бросании игральной кости выпало 5 очков – это случайное событие.

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

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

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

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

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

studfiles.net

§2. Комбинаторика без повторений.

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

Определение 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: Сколькими способами можно пошить трехцветные полосатые флаги, если имеется материал пяти различных цветов.

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

studfiles.net

Число сочетаний без повторений