ВЫВОД ФОРМУЛЫ ЧИСЛА СОЧЕТАНИЙ С ПОВТОРЕНИЯМИ. ПРИМЕНЕНИЕ ФОРМУЛЫ

Кирьянен Александр Иванович

+7812 498 2739 дом, +7921 7979 890 мобил.

kirjanen@mail.ru домашняя почта

Корпоративная почта a.kiriyanen@spbu.ru

 

Формулы сокращённого умножения

 

) разность n-x степеней

=

 сумма геометрической прогрессии

при , так как q ⁿ стремится к нулю.

 

Если n нечётное, то возможно разложение суммы нечётных степеней

Треугольник Лапласа и бином Ньютона

 

 

 

 

 

 

 

n ! ф акториал– это произведение чисел от 1 до n. Определён только для целых неотрицательных чисел. Формула факториала:
n!= 1*2*…n

 

 

 

 

 

 

 

 

483 x 236

 

А как вычислить факториал нуля? Если вернуться к определению, то видно, что применять его в случае «0» нет смысла Однако было решено,

что 0! = 1.

 

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

n=2

a₁, a₂             a₂, a₁

2 перестановки Обозначим P_n – число перестановок из n элементов. P₂=2=2!

 

n=3

a₃ можно вставить перед каждым элементом и после последнего. 3 способа, следовательно P₃= P₂*3=6=3!

Аналогично P_n= P_n-1*n=n!

 

Число сочетаний – это число способов

выбрать из n различных элементов к штук без

упорядочивания (в кучу)

 

= = .

 

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

1. =1 =1

2. =n =n

3.

 

Размещения

Имеем n разных элементов. Выбираем к элементов и упорядочиваем их.

Число размещений

Обозначение

Берём один элемент. Его можно выбрать n способами. Следовательно =n.

Берём второй элемент. Его можно выбрать n-1 способами и размещаем второй за первым Тогда =n*(n-1) и так далее

=n(n-1)…(n-k+1)

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

Перестановкой с повторениями называется размещение с повторениями по n из n элементов со следующим дополнительным условием: различные k элементов повторяются соответственно n₁,…,n _k раз n₁+…+n _k=n.

Теорема 1. Число перестановок с повторениями различных k элементов n₁,…,n _k раз, +…+n _k=n, равно =

Задача 1. Найти число всех перестановок букв слова «баобаб».

Решение. n₁=3 (буква «б»), n₂=2 ( «а»), n₁=1 («о»), значит, .

ВЫБОРКИ ЭЛЕМЕНТОВ С ПОВТОРЕНИЯМИ

 

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

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

Пример 1.  Сколько различных трехзначных чисел можно составить из цифр 1 и 2?

Решение. Примерами таких трехзначных чисел могут служить 111, 112, 221 и т.д.

Найдем п – число элементов исходного множества, n =2 (т.к. числа состоят только из цифр 1 и 2).

Найдем т – число элементов в каждой выборке, т=3 (т.к. составляются трехзначные числа).

Определяем, важен ли порядок элементов в каждой выборке. Числа 112 и 211  состоят из одних и тех же цифр, но эти числа различны, т.к. порядок цифр в них разный. Следовательно, порядок элементов в каждой выборке важен. Значит, мы имеем дело с размещениями, а поскольку цифры 1 и 2 в каждом трехзначном числе могут повторяться, то перед нами размещения с повторениями:

Ответ: из цифр 1 и 2 можно составить 8 трехзначных чисел.

 

Пусть в исходном множестве содержится п элементов, при этом первый элемент встречается т₁ раз, 2-й – т₂ раз, а k-й – m_k раз (т₁+ т₂+…+ m_k = п), то число перестановок с повторениями Р_{т1,т2,…,тk} находится следующим образом: Р_{т1,т2,…,тk} =

Пример .2. Сколько «слов» можно получить, переставляя буквы в слове «МАТЕМАТИКА»?

Решение. Исходное множество состоит из букв слова «МАТЕМАТИКА». Их ровно 10, следовательно п=10.

Заметим, что если бы все буквы были различны, то получили бы Р₁₀ новых «слов». Но буква «М» употребляется в «слове» 2 раза, «А» – 3 раза, «Т» – 2 раза, оставшиеся три буквы – по разу. Следовательно, т₁ = 2, т₂ = 3, т₃ = 2, т₄ = т₅ = т₆ = 1. В данном примере порядок в каждом наборе 10 букв важен, значит, мы имеем дело с размещениями всех 10 элементов или с перестановками с повторением.

Искомое число перестановок будет равно 151200.

Ответ: 151200 «слов» можно получить, переставляя буквы в слове «МАТЕМАТИКА».

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

А сколько получится способов, если шары одинаковые (в ящике может быть любое число шаров)?

Поступим следующим образом. Обозначим шары нулями, их будет k, а также введем n−1 единиц, которые будут обозначать "перегородки". Тогда любая последовательность из k нулей и n−1 единиц однозначно зафиксирует способ разложения шаров: число нулей до первой единицы - это число шаров в первом ящике, число нулей между первой и второй единицей - это число шаров во втором ящике и так далее. А расставить k единиц в последовательности из k+n−1 объектов можно (мы уже знаем - это число сочетаний)

=Ck+n−1=(k+n−1)!/(n−1)!⋅k!

способами.

Эта формула носит название числа сочетаний с повторениями из n объектов по k. Она описывает, сколькими способами можно составить комбинацию по k элементов из элементов n типов (элементы в комбинации могут повторяться, но порядок их не важен).

Пример 3. 8 студенток решили купить себе по одному пирожному. Они зашли в кафе, где в продаже имеются 5 сортов пирожных. Сколько различных заказов официантке могут сделать студентки?

Решение. Исходное множество содержит 5 элементов (идет выбор из 5 пирожных), следовательно п=5.

Так как каждая студентка заказывает себе по одному пирожному, то каждая выборка включает в себя 8 элементов (8 пирожных), т.е. k=8. Смотрим, важен ли порядок элементов в каждой выборке. Поскольку официантке важно лишь сколько пирожных какого вида она должна принести, а порядок пирожных в каждом заказе не важен, то мы имеем дело с сочетаниями. Т.к. пирожные в одном и том же заказе могут повторяться, то перед нами сочетания с повторениями.

Таким образом, =

Ответ: студентки могут сделать 495 различных заказов.

ВЫВОД ФОРМУЛЫ ЧИСЛА СОЧЕТАНИЙ С ПОВТОРЕНИЯМИ. ПРИМЕНЕНИЕ ФОРМУЛЫ

Сочетания с повторениями – это сочетание n объектов по k в предположении, что каждый объект может участвовать в сочетании несколько раз. Таким образом, сочетание с повторениями из n элементов по k элементов (при этом допускается, что k>n) может содержать любой элемент сколько угодно раз от 1 до k включительно или не содержать его совсем, т. е. каждое сочетание с повторениями из n элементов по k элементов может состоять не только из k различных элементов, но и k каких угодно и как угодно повторяющихся элементов.

Существует специальная формула для вычисления числа сочетаний с повторениями. Выведем эту формулу, используя пример. Пусть в кондитерском магазине продаются пирожные 4 видов: корзиночки, наполеоны, песочные и эклеры. Если куплено 3 корзиночки (к), 1 наполеон (н), 2 песочных (п) и 1 эклер (э), то получим такую запись:111|1|11|1.

В этой записи палочки отделяют одну группу пирожных от другой. Если же куплено 2 корзиночки и 5 песочных, то получим запись 11||11111|. Ясно, что разным покупкам соответствуют при этом разные комбинации из 7 единиц и 3 палочек. Обратно, каждой комбинации единиц и палочек соответствует какая-то покупка. Например, комбинации |111|1111| соответствует покупка 3 наполеонов и 4 песочных (крайние группы отсутствуют).

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

Итак, число сочетаний с повторениями из элементов n типов по k равно числу P(k, n–1) перестановок с повторениями из n–1 палочек и k единиц, то есть , поэтому

Рассмотрим задачу. Сколько можно построить различных прямоугольных параллелепипедов, длина каждого ребра которых является целым числом от 1 до 10? Ответ:

 

Тема: Комбинаторика Задание 1. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Решение. Имеем набор {я, я, г, г, г}. Всего перестановок пятиэлементного множества 5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! · 3!. Получаем в итоге 5!/( 2! · 3!) = = 10.

Ответ: 10 способов

 

Задача 2. Предприятие может предоставить работу по одной специальности 4 женщинам , по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Решение. Имеем 14 претендентов и 13 рабочих мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6:  = 6!/( 4! · 2!) = 15. Далее независимо аналогичным образом выберем мужчин на вторую специальность: = 8! /(6! · 2!) = 28. Осталось 2 женщины, 2 мужчин и 3 вакантных места, которые, по условию, могут занять любые из четырех оставшихся человек. Это может быть сделано 2 вариантами: 1. 1 женщина и 2 мужчин (выбираем женщину = 2 способами) 2. 1 мужчина и 2 женщины (выбираем мужчину 2 способами). В итоге получаем 15 · 28(2 + 2) = 1680 способов. Ответ: 1680 способов.

 

ЗАДАНИЕ 3. В пассажирском поезде 9 вагонов. Сколькими способами можно рассадить в поезде 4 человека, при условии, что все они должны ехать в различных вагонах?

РЕШЕНИЕ. Т.к. все пассажиры должны ехать в разных вагонах, требуется отобрать 4 вагона из 9 с учетом порядка (вагоны отличаются №), эти выборки – размещения из n различных элементов по m элементов, где n=9, m=4. Число таких размещений находим по формуле: A = n ⋅(n −1)(n -2) ... ⋅(n − m + ). Получаем: 9 8 7 6 = 3024 .

 ОТВЕТ. 3024 способами можно рассадить в поезде 4 человека.

 

ЗАДАНИЕ 4. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать.

РЕШЕНИЕ. Создавая первую бригаду, отбирают 3 человека из 20, создавая вторую – 5 из оставшихся 17, создавая третью – 12 из оставшихся 12. Для выборок важен только состав (роли членов бригады не различаются). Эти выборки - сочетания из n различных элементов по m элементов. Создавая сложную выборку (из 3-х бригад), воспользуемся правилом умножения: .

ОТВЕТ. 7054320 способов.

ЗАДАНИЕ 5. Для участия в команде тренер отбирает 5 мальчиков из 10. Сколькими способами он может сформировать команду, если 2 определенных мальчика должны войти в команду?

РЕШЕНИЕ. Т.к. известно, что двое мальчиков войдут в команду, то остается отобрать 3 из 8. Для выборки важен только состав (по условию все члены команды не различаются по ролям). Следовательно, выборки – сочетания из n различных элементов по m элементов, их число: =56 способов сформировать команду.

ЗАДАНИЕ 7. В шахматном турнире принимали участие 15 шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире?

РЕШЕНИЕ. Способ 1. В одной игре участвуют 2 человека, следовательно, нужно вычислить, сколькими способами можно отобрать 2-х человек из 15, причем порядок в таких парах не важен. Воспользуемся формулой для нахождения числа сочетаний (выборок, отличающихся только составом) из n различных элементов по m , при n=15, m=2. В процессе решения исключили 13! из15!, т.е. сократили произведение !15 = 1⋅ 2 ⋅3⋅...⋅15 на 13! = 1⋅ 2 ⋅ 3⋅...⋅13, остались после сокращения множители 14 и 15).

Способ 2. Первый игрок сыграл 14 партий (с2-м, 3-м, 4-м, и так до 15-го), 2- ой игрок сыграл 13 партий (3-м, 4-м, и т.д. до 15-го, исключаем то, что с первым партия уже была), 3-ий игрок − 12 партий, 4-ый − 11 партий, 5 – 10 партий, 6 – 9 партий, 7 – 8 партий, 8 – 7 партий, 9 – 6 10 – 5 11 – 4 12 – 3 13 – 2 14 – 1, а 15-ый уже играл со всеми. Итого: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 партий ОТВЕТ. 105 партий.

ЗАДАНИЕ 8. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?

РЕШЕНИЕ. Различных дробей из 6 чисел: 3, 5, 7, 11, 13, 17 можно составить 2 6 6! 2 2 5 6 30 4!2! C ⋅ = ⋅ = ⋅ = штук ( 2  способами, то есть выбираем два числа из 6, и двумя способами составляем из них дробь: сначала одно число – числитель, другое знаменатель и наоборот). Из этих 30 дробей ровно 15 будут правильные (т.е., когда числитель меньше знаменателя): 15 способами выбираем два числа из 6, и единственным образом составляем дробь так, чтобы числитель был меньше знаменателя. ОТВЕТ. 30; 15.

Задача 9. Сколько слов можно получить, переставляя буквы в слове Гора и Институт?

ЗАДАНИЕ 9. Сколько слов можно получить, переставляя буквы в слове Гора и Институт?

РЕШЕНИЕ. 1) В слове «гора» четыре буквы, все они различны, поэтому можно получить всего 1) N =4! 1 2 3 4 24 различных слова. 2) В слове «институт» 8 букв, из них две буквы «и», три буквы «т» и по одной букве «н», «с» и «у». Поэтому всего можно получить перестановками букв  различных слов. ОТВЕТ. 24 и 3360 слов.

 

---

Дата добавления: 2021-11-30; просмотров: 108; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!