В ящике 9 яблок сколькими способами можно выбрать 3 яблока из ящика

Добавил пользователь Alex
Обновлено: 24.09.2024

Презентация на тему: " Решение комбинаторных задач с помощью формулы сочетания." — Транскрипт:

1 Решение комбинаторных задач с помощью формулы сочетания.

2 ЦЕЛЬ: Решение комбинаторных задач с помощью формулы сочетания.

3 С ОЧЕТАНИЯ Комбинации из n элементов по k, отличающиеся друг от друга лишь составом элементов, называются сочетаниями из n элементов по k., (k n)

4 Задача : На столе лежат 5 разноцветных карандашей. Сколько существует способов для выбора 3 из них? Ответ: 10 способов

5 Задача: Из 12 учеников нужно выбрать 3 ученика на улусный новогодний бал. Сколькими способами можно сделать этот выбор? Ответ: 220 способов

6 Задача: Сколько диагоналей в выпуклом десятиугольнике? Ответ: 45 диагоналей.

7 Задача: Сколько существует способов выбора трёх ребят из 4-х желающих дежурить в столовой? Ответ: 4 способа.

8 Задача: В корзине имеются 15 груш и 7 яблок. Нужно выбрать 5 груш и 3 яблока. Сколькими способами это можно сделать? Ответ: способа. Подсчитаем способы выбора 5 груш: Подсчитаем способы выбора 3 яблок: =105105

Общую задачу сформулируем следующим образом.

Имеется n элементов k различных типов: n1 элементов первого типа, n2 элементов второго типа, …, nk элементов k-го типа, . Сколько можно составить различных перестановок из этих элементов?

Число перестановок c повторениями обозначают . Сколько же их? Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В первой группе элементы (первого типа) можно переставлять друг с другом n1! способами. Но так как все эти элементы одинаковы, то перестановки ничего не меняют. Точно также ничего не меняют n2! перестановок элементов во второй группе и т. д. Перестановки элементов в разных группах можно делать независимо друг от друга. Поэтому (из принципы умножения) элементы можно переставлять друг с другом способами так, что она остаётся неизменной.

Число различных перестановок с повторениями, которые можно составить из данных элементов, равно

, (11.1) где .

Замечание. Отметим, что формула числа сочетаний из n элементов по k элементов совпадает с формулой для числа перестановок с повторениями из k элементов одного типа и n–k элементов другого типа:

Пример 11.1. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение. Речь идет об отыскании числа перестановок с повторениями, которые можно сделать из k1=4 элементов первого типа (зеленых бус), k2=5 элементов второго типа (синих бус) и k3=6 элементов третьего типа (красных бус). По формуле (6) получаем

Пример 11.2. У мамы было 2 одинаковых яблока, 3 одинаковых груши и 4 одинаковых апельсина. Каждый день она давала ребенку по одному фрукту. Сколькими способами она могла это сделать?

Решение. Данная задача есть задача на отыскание числа перестановок с повторениями:

Пример 11.3. Сколько различных браслетов можно сделать из пять одинаковых изумрудов, шести одинаковых рубинов и семи одинаковых сапфиров (в браслет входят все 18 камней)?

Решение. Камни можно переставлять P(5, 6, 7) способами. При циклических перестановках и при зеркальном отражении браслет остается неизменным. В результате получаем

11.1. Сколькими способами можно расположить в ряд две зелёные и четыре красные лампочки?

Ответ: .

11.2. Десять человек надо разбить на три группы соответственно по 2, 3, 5 человек в группе. Сколькими способами можно это сделать?

Ответ: .

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

Ответ: .

11.4. Группу командировочных из восьми человек требуется расселить в три комнаты, из которых две трёхместные и одна двухместная. Сколько вариантов расселения возможно?

Ответ: .

11.5. Сколько различных слов можно получить, переставляя буквы в следующих исходных словах: а) академия, б) электротехника, в) молокопродукт?

Ответ: .

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

Ответ: .

11.7. Для премий на математической олимпиаде выделено 3 экземпляра одной книги, 4 экземпляра другой и 8 экземпляров третьей. Сколькими способами могут быть распределены эти премии между 30 участниками олимпиады, если каждому вручается не более одной книги?

Ответ: .

Ответ: Гласные можно переставлять P(2,1,1)=12 способами, Аналогично, P(2,1,1)=12 способами можно расставить согласные буквы. Если согласные уже расставлены, то для гласных останется 5 мест. Поэтому места для них можно выбрать способами. Всего способов.

19. Размещения, перестановки, сочетания с повторениями. Формула включения – исключения

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

$\< a_1,a_2,\ldots,a_n\> Определение. Отображение множества первых натуральных чисел в данное множество$
, называется размещением с повторениями, составленным из данных элементов по .

Размещения с повторениями называются также конечными последовательностями.

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

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

Пример. Всевозможные размещения с повторениями из трех элементов по 2:

$aa,ab,ac,ba,bb,bc,ca,cb,cc.$

Теорема. Число всевозможных размещений с повторениями из элементов по равно

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

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

$a_<i_<1> >,a_>,\dots,a_>,a_>$

первые элементов

$a_<i_<1> >,a_>,\dots,a_>$

образуют некоторое размещение с повторениями из по элементов. В качестве последнего -го элемента >" width="35" height="15" />
может быть взят любой из элементов. При различных выборах >" width="35" height="15" />
получаются различные размещения. Кроме того, два различные размещения -го порядка дают два различные размещения -го порядка.

Таким образом, число всех размещений -го порядка равно

$n^kn=n^<k+1> .$

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

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

Всякое размещение с повторениями, в котором элемент повторяется раз, элемент повторяется раз и т.д. элемент повторяется раз, где , , , — данные числа, называется перестановкой с повторениями порядка

в которой данные элементы повторяются соответственно , , раз.

$\< a_1,a_2,\ldots,a_n\> Теорема. Число различных перестановок с повторениями из элементов$
, в которых элементы повторяются соответственно раз, равно

$<(k_1+k_2+\dots+k_n)!\over k_1!k_2!\dots k_n!> .$

Доказательство. Если мы будем считать все элементов перестановки с повторениями различными, то всего различных вариантов перестановок элементов — . Однако среди этих перестановок не все различны. В самом деле, все элементы мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы , , , . Таким образом, всякая перестановка может быть записана способами. Следовательно, число различных перестановок с повторениями равно

$<(k_1+k_2+\dots+k_n)!\over k_1!k_2!\dots k_n!> .$

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

Ответ.

$\left(<(p+q+r)!\over p!q!r!> \right).$

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

Определение. Если каждому элементу некоторого конечного множества поставлено в соответствие целое неотрицательное число — кратность данного элемента, то говорят, что задано сочетание с повторениями. Сумма кратностей всех элементов называется порядком сочетания.

Всякое сочетание с повторениями -го порядка, составленное из множества, содержащего элементов, называется также сочетанием с повторением из элементов по .

Если — кратности элементов , то по определению есть порядок сочетания

Теорема. Число сочетаний с повторениями из элементов по выражается формулой

$\tilde _n^k=<(n+k-1)!\over k!(n-1)!>=_^k.$

Пример. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и картошка. Сколькими способами можно купить 7 пирожных?

Решение. Положим пирожные в коробку, а чтобы они не перепутались, разделим их картонными разделителями. Нужно 3 разделителя. Обозначения: 0 (картонки-разделители) и 1 — пирожные. Примерная покупка: 1110101101 — три наполеона, 1 эклер, 2 песочных и 1 картошка.

Итак два класса объектов 1 (7 штук) и 0 (3 штуки) — покупка — 10 объектов.

Два способа рассуждения:

(1) задача сводится к выбору мест для 7 пирожных (или для 3 разделителей) среди 10 объектов.

(2) другой способ рассуждения (эквивалентный). Надо разбить 10 мест на две группы: для 7 пирожных и 3 разделителей.

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

$\tilde<\sf C> Пусть заданы два числа: — число выбираемых элементов, и — число типов элементов, из которых производится выбор. Число _n^k$
сочетаний с повторениями порядка из элементов типов равно числу способов выбора мест для собственно выбираемых элементов различных классов, или, что то же: для разделителей между ними.

Итак, основная формула:

$\tilde _n^k=_^=_^.$

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

Сочетания с повторениями с дополнительными условиями

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

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

В частности, пусть число типов — числа выбранных элементов. Сколько существует сочетаний с повторениями, так что представлены хотя бы по одному все типы элементов?

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

Решение. Пусть нолики — шарики, а единички — стенки ящиков (потребуется единичек). Две единички сразу кладем по краям.

$<\sf C> Теперь положим между ними шарики-нолики, а далее нужно заполнить некоторые промежутки между ними так, чтобы между любыми двумя ноликами находилась не более одной единички. Значит, из промежутков между шариками нужно выбрать места для единичек. Всего таких способов _^$
.

Метод координат. Подсчет числа путей

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

$<\sf C> Поскольку на перекресток на уровне (считая сверху и принимая верхний уровень за нулевой) ведет _n^k$
путей (число способов выбрать движений направо вниз из общего числа движений вниз), то свойство суммирования путей на перекрестке можно записать как

$ _n^k=_^+_^k.$

Формула включения — исключения

Определение. Число элементов множества называется мощностью множества и обозначается .

Теорема. Пусть даны множества . Тогда количество элементов в объединении этих множеств можно найти по формуле:

$\begin |A_1\cup A_2\cup\ldots\cup A_n|=|A_1|+\ldots+|A_n|-\\ -|A_1\cap A_2|-|A_1\cap A_3|-\ldots-|A_\cap A_n|+\\ +|A_1\cap A_2\cap A_3|+\ldots+|A_\cap A_\cap A_n|+(-1)^ |A_1\cap A_2\ldots\cap A_n| \end$

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

$|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|.$

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

Предположим, что формула включения — исключения справедлива для множеств.
Докажем ее для множеств. Множество можно представить в виде

$A_1\cup A_2\cup\ldots\cup A_n=(A_1\cup\ldots\cup A_<n-1> )\cup A_n.$

Тогда получаем (первое равенство по формуле включения — исключения для двух множеств):

$\begin |A_1\cup A_2\cup\ldots\cup A_n|=|A_1\cup\ldots\cup A_|+|A_n|-|(A_1\cup\ldots\cup A_)\cap A_n|=\\ =|A_1|+\ldots+|A_|-|A_1\cap A_2|-|A_1\cap A_3|-\ldots-|A_\cap A_|+\\ +|A_1\cap A_2\cap A_3|+\ldots+|A_\cap A_\cap A_|+(-1)^ |A_1\cap A_2\ldots\cap A_|+\\ +|A_n|-|(A_1\cup\ldots\cup A_)\cap A_n|. \end$

$(A_1\cup A_2\cup\ldots\cup A_ )\cap A_n=(A_1\cap A_n)\cup(A_2\cap A_n)\cup \ldots\cup(A_\cap A_n),$

и формулу включения — исключения для множеств, получаем

В эту формулу подставляем выражение, полученное ранее, и теорема доказана.

Задачи.

1. Есть три билета в различные театры. Сколькими способами они могут быть распределены между 25 школьниками, если каждый школьник может получить только один билет?
2. Есть три билета на КВН 1 апреля. Сколькими способами они могут быть распределены между 25 школьниками (более одного билета в руки не давать. )?
3. Телефонный номер состоит из 7 цифр. Насколько легче угадать правильный номер, если знать, что все его цифры различны?

4. В буфете продаются 5 сортов пирожков: с яблоками, с капустой, картошкой, мясом и грибами (цена всех пирожков одинакова). Скольким числом способов можно сделать покупку из 10 пирожков?

5. (Продолжение). Скольким числом способов можно сделать покупку так, чтобы попробовать пирожков всех видов?

6. (Продолжение). Скольким числом способов можно сделать покупку так, чтобы в нее вошло не менее двух пирожков с мясом и хотя бы один пирожок с яблоками?

7. Скольким числом способов можно вывести на арену цирка 5 львов и 4 тигра так, чтобы никакие два тигра не шли друг за другом (оказавшись рядом, они начинают драться)?

8. За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует со своими соседями. Для участия в спецоперации по освобождению заколдованной принцессы нужно выбрать 5 рыцарей, но при этом нельзя посылать вместе рыцарей, враждующих друг с другом. Скольким числом способов это можно сделать?

9. Докажите формулу

$\sum_<i=0> ^p(_p^i)^2=_^p.$

10. Докажите, что число различных решений уравнения

$<\sf C> в неотрицательных целых числах равно _^$
.

11. Докажите, что число различных решений уравнения

$<\sf C> в натуральных числах равно _^$
.

12. Сколькими способами можно разложить 15 одинаковых шаров по 5 различным ящикам так, чтобы оказалось не более двух пустых ящиков?

13. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным ящикам так, чтобы в каждом ящике оказалось не менее двух шаров?

14. Сколькими способами можно разложить 20 одинаковых шаров по 6 различным ящикам так, чтобы в каждом ящике оказалось не более 5 шаров?

15. Докажите, что число таких перестановок чисел , которые удовлетворяют условию при всех , равно

$n!\sum_<k=0> ^n\frac.$

Комментариев: 11

1 Число ``счастливых’’ билетов | Математика, которая мне нравится:

[. ] Далее нам понадобится число способов представления целого неотрицательного числа в виде суммы трех целых неотрицательных слагаемых. Это можно сделать способами. Действительно, число способов равно числу сочетаний с повторениями из по (или иначе, разбиваем единиц на три группы — три слагаемых, в качестве разделителей используем нули, всего элемента, из которых нужно выбрать нуля, см. сочетания с повторениями). [. ]

2 лариса:

спасибо за понятное объяснение вывода формулы сочетания с повторениями, разделители для пирожных – это здорово.

3 Елизавета Александровна Калинина:

Это спасибо не мне, а Н.Я. Виленкину, А.Н. Виленкину, П.А. Виленкину и книге “Комбинаторика” (объяснение оттуда).

4 Число перестановок | Математика, которая мне нравится:

[. ] формуле включения — исключения [. ]

5 SPSS:

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

6 Артист:

Помогите пожалуста решить задачу:
Имеется 5 видов книг, в скольких-то экземплярах(по сути это не важно).
На полке умещается всего 5 книг.
На полке не может стоять больше 2х одинаковых видов книг.
Сколько всего вариантов размещения книг на полке?

Правильный ответ: 2220 вариантов.

Никак не могу найти решение.

5^5=5*5*5*5*5=3125 вариантов расстановки всего, на полке одновременно может быть 5 одинаковых видов книг.
5!=5*4*3*2*1=120 вариантов перестановок, на полке одновременно только разные книги.

Если брать возведение в степень:
1й множитель – общее количество видов книг.
2й множитель – общее количество видов книг, т. к. не нарушает условие.
3й множитель – общее количество видов книг – 1, т. к. 1 книга уже в 2х экземплярах.
4й множитель – общее количество видов книг – 1, т. к. 1 книга уже в 2х экземплярах.
5й множитель – общее количество видов книг – 2, т. к. 2 книги уже в 2х экземплярах.

Но это неверный счёт, т.к. в “рядах” на полке последовательности нет.
В любом ряду может быть как все экземпляры, так и только некоторые…

Вы уверены, что ответ правильный? И еще: важен порядок расстановки книг на полке?

Артист Reply:
Июль 10th, 2017 at 11:09

Правильный ответ верный, я считал программой.
Порядок не важен.

7 Светлана:

Задача решится, если использовать формулу числа перестановок с повторениями и правило суммы. Ответ правильный.

8 Акмаль:

Помогите с задачей:: Подсчитать число сочетаний из 6 по 3

9 Danil:

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

Общую задачу сформулируем следующим образом.

Число различных перестановок с повторениями, которые можно составить из данных элементов, равно

, (11.1) где .

Пример 11.1. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение. Данная задача есть задача на отыскание числа перестановок с повторениями:

11.1. Сколькими способами можно расположить в ряд две зелёные и четыре красные лампочки?

Ответ: .

Читайте также: