Число способов которым можно осуществить

Число способов которым можно осуществить

тБУУНПФТЙН УМЕДХАЭЙЕ ЧПЪНПЦОЩЕ УРПУПВЩ ЧЩВПТБ.

1. чЩВПТ У ЧПЪЧТБЭЕОЙЕН: ЛБЦДЩК ЧЩОХФЩК ЫБТ ЧПЪЧТБЭБЕФУС Ч ХТОХ, ЛБЦДЩК УМЕДХАЭЙК ЫБТ ЧЩВЙТБЕФУС ЙЪ РПМОПК ХТОЩ. ч РПМХЮЕООПН ОБВПТЕ ЙЪ ОПНЕТПЧ ЫБТПЧ НПЗХФ ЧУФТЕЮБФШУС ПДОЙ Й ФЕ ЦЕ ОПНЕТБ. 2. чЩВПТ ВЕЪ ЧПЪЧТБЭЕОЙС: ЧЩОХФЩЕ ЫБТЩ Ч ХТОХ ОЕ ЧПЪЧТБЭБАФУС, Й Ч РПМХЮЕООПН ОБВПТЕ ОЕ НПЗХФ ЧУФТЕЮБФШУС ПДОЙ Й ФЕ ЦЕ ОПНЕТБ.

хУМПЧЙНУС, ЛБЛЙЕ ТЕЪХМШФБФЩ ЧЩВПТБ (ОБВПТЩ ЙЪ ОПНЕТПЧ ЫБТПЧ) НЩ ВХДЕН УЮЙФБФШ ТБЪМЙЮОЩНЙ. еУФШ ТПЧОП ДЧЕ ЧПЪНПЦОПУФЙ.

1. чЩВПТ У ХЮЈФПН РПТСДЛБ : ДЧБ ОБВПТБ ОПНЕТПЧ ЫБТПЧ УЮЙФБАФУС ТБЪМЙЮОЩНЙ, ЕУМЙ ПОЙ ПФМЙЮБАФУС УПУФБЧПН ЙМЙ РПТСДЛПН ОПНЕТПЧ. фБЛ, РТЙ ЧЩВПТЕ ФТЈИ ЫБТПЧ ЙЪ ХТОЩ, УПДЕТЦБЭЕК 5 ЫБТПЧ, ОБВПТЩ (1, 5, 2), (2, 5, 1) Й (4, 4, 5) ТБЪМЙЮОЩ, ЕУМЙ РПТСДПЛ ХЮЙФЩЧБЕФУС. 2. чЩВПТ ВЕЪ ХЮЈФБ РПТСДЛБ : ДЧБ ОБВПТБ ОПНЕТПЧ ЫБТПЧ УЮЙФБАФУС ТБЪМЙЮОЩНЙ, ЕУМЙ ПОЙ ПФМЙЮБАФУС УПУФБЧПН. оБВПТЩ, ПФМЙЮБАЭЙЕУС МЙЫШ РПТСДЛПН УМЕДПЧБОЙС ОПНЕТПЧ, УЮЙФБАФУС ПДЙОБЛПЧЩНЙ.

фБЛ, ОБВПТЩ (1, 5, 2) Й (2, 5, 1) ОЕ ТБЪМЙЮБАФУС Й ПВТБЪХАФ ПДЙО Й ФПФ ЦЕ ТЕЪХМШФБФ ЧЩВПТБ, ЕУМЙ РПТСДПЛ ОЕ ХЮЙФЩЧБЕФУС.

рПДУЮЙФБЕН, УЛПМШЛП ЧПЪНПЦОП ТБЪМЙЮОЩИ ТЕЪХМШФБФПЧ ДМС ЛБЦДПК ЙЪ ЮЕФЩТЈИ УИЕН ЧЩВПТБ (ЧЩВПТ У ЧПЪЧТБЭЕОЙЕН ЙМЙ ВЕЪ, Й Ч ЛБЦДПН ЙЪ ЬФЙИ УМХЮБЕЧ — У ХЮЈФПН РПТСДЛБ ЙМЙ ВЕЪ).

Й ОБЪЩЧБЕФУС ЮЙУМПН ТБЪНЕЭЕОЙК ЙЪ ЬМЕНЕОФПЧ РП ЬМЕНЕОФПЧ.

ТБЧОП . дМС ЛБЦДПК ФБЛПК РБТЩ ЕУФШ УРПУПВБ ЧЩВТБФШ ФТЕФЙК ЫБТ. рП ФЕПТЕНЕ 1, ЮЙУМП ЧПЪНПЦОЩИ ФТПЕЛ

ТБЧОП РТПЙЪЧЕДЕОЙА ЮЙУМБ РБТ Й ЮЙУМБ УРПУПВПЧ ЧЩВПТБ ФТЕФШЕЗП ЫБТБ, Ф.Е. ТБЧОП . рТПДПМЦБС ТБУУХЦДЕОЙС, РПМХЮЙН, ЮФП ПВЭЕЕ ЮЙУМП ЧПЪНПЦОЩИ ОБВПТПЧ ЙЪ ЫБТПЧ ТБЧОП . ч ЬФПН РТПЙЪЧЕДЕОЙЙ УПНОПЦЙФЕМЕК РПУМЕДОЙК НОПЦЙФЕМШ ЕУФШ ЮЙУМП УРПУПВПЧ ЧЩВПТБ -ЗП ЫБТБ, ЛПЗДБ ХЦЕ ЧЩВТБОЩ РТЕДЩДХЭЙЕ.

Й ОБЪЩЧБЕФУС ЮЙУМПН УПЮЕФБОЙК ЙЪ ЬМЕНЕОФПЧ РП ЬМЕНЕОФПЧ.

У ХЮЈФПН РПТСДЛБ	ВЕЪ ХЮЈФБ РПТСДЛБ
(1,1)	(1,1)
(2,2)	(2,2)
(1,2) (2,1)	> (1,2)

чЙДЙН, ЮФП Ч УИЕНЕ «ВЕЪ ХЮЈФБ РПТСДЛБ» РПМХЮЙМПУШ ФТЙ ТБЪМЙЮОЩИ ТЕЪХМШФБФБ, Ч ПФМЙЮЙЕ ПФ ЮЕФЩТЈИ ТЕЪХМШФБФПЧ Ч УИЕНЕ «У ХЮЈФПН РПТСДЛБ». ъБНЕФЙН ФБЛЦЕ, ЮФП ОЙЛБЛЙН ДЕМЕОЙЕН ОБ «ЮЙУМП ЛБЛЙИ-ОЙВХДШ РЕТЕУФБОПЧПЛ», ЛПФПТПЕ РПНПЗМП ЙЪВБЧЙФШУС ПФ ХЮЈФБ РПТСДЛБ РТЙ ЧЩВПТЕ ВЕЪ ЧПЪЧТБЭЕОЙС, ЮЙУМП 3 ЙЪ ЮЙУМБ 4 РПМХЮЙФШ ОЕ ХДБУФУС.

рТЕДУФБЧЙН УЕВЕ ДТХЗПК ЬЛУРЕТЙНЕОФ, ЙНЕАЭЙК ФПЮОП ФБЛЙЕ ЦЕ ТЕЪХМШФБФЩ, Й РПУЮЙФБЕН ЙИ ЛПМЙЮЕУФЧП. еУФШ СЭЙЛПЧ, Ч ЛПФПТЩИ ТБЪНЕЭБАФУС ЫБТПЧ. оБУ ЙОФЕТЕУХЕФ ФПМШЛП ЮЙУМП ЫБТПЧ Ч ЛБЦДПН СЭЙЛЕ. тЕЪХМШФБФПН ЬЛУРЕТЙНЕОФБ УОПЧБ СЧМСЕФУС ОБВПТ ЮЙУЕМ , ЗДЕ ТБЧОП ЮЙУМХ ЫБТПЧ Ч СЭЙЛЕ У ОПНЕТПН , Й . юЙУМБ РТЙОЙНБАФ ОБФХТБМШОЩЕ ЪОБЮЕОЙС ЙМЙ ТБЧОЩ ОХМА.

б ФЕРЕТШ ЙЪПВТБЪЙН ТЕЪХМШФБФ ФБЛПЗП ТБЪНЕЭЕОЙС Ч ЧЙДЕ УИЕНЩ, Ч ЛПФПТПК ЧЕТФЙЛБМШОЩЕ МЙОЙЙ ПВПЪОБЮБАФ РЕТЕЗПТПДЛЙ НЕЦДХ СЭЙЛБНЙ, Б ФПЮЛЙ — ОБИПДСЭЙЕУС Ч СЭЙЛБИ ЫБТЩ:

нЩ ЧЙДЙН ТЕЪХМШФБФ ТБЪНЕЭЕОЙС ДЕЧСФЙ ЫБТПЧ РП УЕНЙ СЭЙЛБН. рЕТЧЩК СЭЙЛ УПДЕТЦЙФ ФТЙ ЫБТБ, ЧФПТПК Й ЫЕУФПК СЭЙЛЙ РХУФЩ, ФТЕФЙК СЭЙЛ УПДЕТЦЙФ ПДЙО ЫБТ, Ч ЮЕФЧЈТФПН Й РСФПН СЭЙЛБИ МЕЦЙФ РП ДЧБ ЫБТБ. рЕТЕМПЦЙН ПДЙО ЫБТ ЙЪ РЕТЧПЗП СЭЙЛБ ЧП ЧФПТПК Й ЙЪПВТБЪЙН ФБЛЙН ЦЕ ПВТБЪПН ЕЭЈ ДЧБ ТЕЪХМШФБФБ ТБЪНЕЭЕОЙС:

чЙДЙН, ЮФП ЧУЕ ТБЪНЕЭЕОЙС НПЦОП РПМХЮЙФШ, НЕОСС НЕЦДХ УПВПК ЫБТЩ Й РЕТЕЗПТПДЛЙ, ЙМЙ ТБУУФБЧМСС ЫБТПЧ ОБ НЕУФБИ. юЙУМП РПМХЮБЕФУС ФБЛ: Х СЭЙЛПЧ ЕУФШ ТПЧОП РЕТЕЗПТПДЛБ, УЮЙФБС ЛТБКОЙЕ, ОП ЙЪ ОЙИ РЕТЕНЕЭБФШ НПЦОП МЙЫШ ЧОХФТЕООАА РЕТЕЗПТПДЛХ. фБЛЙН ПВТБЪПН, ЙНЕЕФУС НЕУФ, ЛПФПТЩЕ НПЦОП ЪБОСФШ ЫБТБНЙ МЙВП ЧОХФТЕООЙНЙ РЕТЕЗПТПДЛБНЙ. рЕТЕВТБЧ ЧУЕ ЧПЪНПЦОЩЕ УРПУПВЩ ТБУУФБЧЙФШ ЫБТПЧ ОБ ЬФЙИ НЕУФБИ (ЪБРПМОСС ПУФБЧЫЙЕУС НЕУФБ РЕТЕЗПТПДЛБНЙ), РЕТЕВЕТЕН ЧУЕ ОХЦОЩЕ ТБЪНЕЭЕОЙС.

пУФБМПУШ ЪБНЕФЙФШ, ЮФП УРПУПВПЧ ТБУУФБЧЙФШ ЫБТПЧ ОБ НЕУФБИ УХЭЕУФЧХЕФ

йНЕООП УФПМШЛП ЕУФШ УРПУПВПЧ ЧЩВТБФШ ЙЪ ОПНЕТПЧ НЕУФ ОПНЕТПЧ НЕУФ ДМС ЫБТПЧ.

Источник

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

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

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

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

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

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

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

.

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

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

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

.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

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

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

.

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

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

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

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

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Источник

10. Элементы комбинаторики

10.1 Пусть есть некоторое конечное множество элементов U = . Рассмотрим набор элементов , где ÎU, j = 1, 2, . r. Этот набор называется Выборкой объема r из n элементов. Любое подмножество U является выборкой, но не всякая выборка является подмножеством U, так как в выборку один и тот же элемент может входить несколько раз (в отличие от подмножества).

Комбинаторные задачи связаны с подсчетом числа выборок объема r из n элементов, где выборки подчиняются определенным условиям, т. е. выбор производится по какому-нибудь принципу. Подсчет числа выборок основывается на двух правилах теории множеств.

10.2 Принцип суммы: если card A = m, card B = n и AÇB = Æ , то card A È B = m+n. На комбинаторном языке это означает: если объект A можно выбрать m способами, объект B другими n способами и их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m+n способами.

10.3 Принцип произведения: если card A = m, card B = n, то card (A´B) = m´n. На комбинаторном языке это означает: если объект A может быть выбран m способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен m×n способами.

10.4 Пример. A = <10 различных шоколадок>, B = <5 различных пачек печенья>. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в это случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.

10.5 Пример. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков?

Пусть m — число возможностей для выпадения четного числа на одной кости, n — число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, равно как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных или двух нечетных чисел будет 18.

Рассмотрим основные способы формирования выборок.

10.6 Определение. Выборка называется Упорядоченной, если в ней задан порядок следования элементов. Если порядок следования элементов несущественен, то выборка называется неупорядоченной.

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

10.7 Перестановки. Упорядоченные выборки объемом n из n элементов, где все элементы различны, называются Перестановками из n элементов. Число перестановок из n элементов обозначается Pn.

10.8 Теорема. P = n!

Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P1 = 1!. Пусть для n = k теорема верна и Pk = k!, покажем, что она тогда верна и для n = k + 1. Рассмотрим (k+1)-ый элемент, будем считать его объектом A, который можно выбрать k+1 способами. Тогда объект B — упорядоченная выборка из оставшихся k элементов по k. B соответствии с индуктивным предположением объект B можно выбрать k! способами. По принципу произведения выбор “A и B” можно осуществить k!´(k + 1) = (k + 1)! способами. А совместный выбор “A и B” есть упорядоченная выборка из k + 1 элементов по k + 1.

10.9 Пример. Сколько существует способов, чтобы расположить на полке 10 различных книг? Ответ: 10 !

Можно рассуждать иначе. Выбираем первый элемент, это можно сделать n способами. Затем выбираем второй элемент, это можно сделать (n — 1) способами. По правилу произведения упорядоченный выбор двух элементов можно осуществить n´(n — 1) способами. Затем выбираем третий элемент, для его выбора останется n — 2 возможности, последний элемент можно выбрать единственным способом. Мы вновь приходим к формуле: n(n — 1)( n — r) . 1.

Источник