Определения сочетаний, размещений и перестановок

Комбинаторный принцип умножения.

Представьте для себя, что человек, которому не чем больше заняться, подбрасывает монету и кость (в виде игрального кубика). На монете может выпасть "орел" (О) и "решка" (Р). При падении кости вероятные финалы представляют собой 1,2,3,4,5 и 6. Вероятными финалами обоих событий являются (О,1), (О,2), (О,3), (О,4), (О,5), (О,6), (Р Определения сочетаний, размещений и перестановок, 1), (Р, 2), (Р, 3), (Р, 4), (Р,5) и (Р,6). Один из вероятных методов представить эти действия—выстроить дерево подсчета, изображенное на рисунке:

Разумеется, что таким макаром представлены все финалы событий, и каждое из обведенных чисел изображает единственный финал. Если на монете выпал О, то есть 6 вероятных исходов для кубика; и те же 6 вероятных Определения сочетаний, размещений и перестановок исходов, если выпала "решка" Р. Таким макаром, можно отыскать полное количество исходов, умножая 2x6, т.е. умножая число вероятных исходов для подкидывания монеты на число вероятных исходов для подкидывания игральной кости. Следует направить внимание, что финал подкидывания монеты не оказывает влияние на вероятный финал подкидывания кости.

Пример Определения сочетаний, размещений и перестановок 1. Сколько существует разных инъективных отображений из огромного количества A в огромное количество B, если |A| = n, а |B| = m?

Решение.

Инъективное отображение предполагает, что каждый элемент из области значения имеет единственный прототип. Отметим сходу, что если a>b, такового отображения не существует.

Найдем число отображений по принципу умножения. Положим, что элементы Определения сочетаний, размещений и перестановок огромного количества A обозначены как . Образ для первого элемента a1 можно избрать m методами. Образ для элемента a2 следует выбирать из огромного количества , где f — отображение (а f(a1) — образ элемента a1), так как нельзя использовать образ первого элемента. Таким макаром, есть m-1 методов выбора вида элемента a Определения сочетаний, размещений и перестановок2. Рассуждая таким макаром далее, получаем, что образ элемента a3 можно избрать m-2 методами и т.д. В конечном итоге число отображений по правилу умножения выходит равным:

Представим, что на собрании находятся 10 парней и 15 дам, и кого-либо 1-го необходимо избрать председателем. Существует 10+15=25 методов выбора председателя. Представим, что человек направляется Определения сочетаний, размещений и перестановок в ресторан, в каком предлагаются 15 блюд из говядины, 8 блюд из свинины и 12 блюд из морских товаров. Гостю ресторана предложен выбор из 15+8+12=35 разных блюд. Заметим, что в каждом случае огромного количества, из частей которых делается выбор, не пересекаются.

Комбинаторный принцип сложения. Пусть - попарно непересекающиеся огромного количества, и пусть для каждого i Определения сочетаний, размещений и перестановок огромное количество Si содержит ni частей. Количество вариантов выбора из S1 либо S2 либо … либо Sm равно На языке теории множеств утверждение аксиомы имеет вид:

Пример 2

Сколько нечетных целых чисел находятся меж числами 100 и 1000?

Решение

Пусть S — огромное количество нечетных целых чисел меж 100 и 1000. Для пусть - подмножество огромного количества S Определения сочетаний, размещений и перестановок такое, что i является последней цифрой его частей. Для каждого i есть 9 вариантов выбора первой числа и 10 вариантов выбора 2-ой числа, так что каждое огромное количество Si содержит 90 частей. . потому меж 100 и 1000 есть 450 нечетных чисел.

Разглядим сейчас применение принципа сложения в этом случае, когда огромного количества могут пересекаться.

Пример 3. Чему равно Определения сочетаний, размещений и перестановок , если огромного количества S и T могут пересекаться?

Решение: (отлично иллюстрировать на кругах Эйлера)

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

Отсюда:

Для 3-х множествформула будет таковой:

Пример 4. Представим Определения сочетаний, размещений и перестановок, что, согласно исследованию, из 200 людей, смотрящих телек, 110 человек глядят спортивную передачу, 120—комедии, 85 предпочитают драмы, 50 глядят драмы и спорт, 70 — комедии и спорт, 55 глядят комедии и драмы и 30 человек глядят все три вида передач.

1. Сколько человек глядят спорт, комедии либо драмы?

2. Сколько человек не глядят ничего из перечисленного выше?

Пусть U Определения сочетаний, размещений и перестановок —огромное количество 200 людей, посреди которых проводился опрос. Пусть S — огромное количество людей, которые глядят спорт; D —огромное количество людей, которые глядят драмы, и С — огромное количество людей, предпочитающих комедии.

По приведенной выше формуле получаем, что

1.

2.

На диаграммах Эйлера эту задачку можно проиллюстрировать так. Понятно, что 30 человек глядят по телевидению спорт Определения сочетаний, размещений и перестановок, комедии и драмы. Так как 50 человек глядят спорт и драмы, то 20 человек должны глядеть спорт и драмы, но не глядеть комедии. Аналогично, 55 глядят комедии и драмы, потому 25 человек должны глядеть комедии и драмы, но не глядеть спорт. К тому же 70 человек глядят спорт и комедии, потому 40 из их глядят спорт и Определения сочетаний, размещений и перестановок комедии, но не глядят драмы. Таким макаром, получаем последующие диаграммы Эйлера (рис 8.6):

Понятно, что 85 человек предпочитают глядеть драмы. Так как 75 из их уже перечислены, другие 10 должны глядеть только драмы. Рассуждая аналогичным образом, получаем, что из 110 тех, кто глядит спорт, уже перечислены 90 человек, потому оставшиеся 20 должны глядеть только Определения сочетаний, размещений и перестановок спорт. И в конце концов, замечаем, что из 120 тех, кто глядит комедии, 95 уже учтены. Таким макаром, 25 человек глядит только комедии. Если подсчитать количество людей в непересекающихся подмножествах, то получим число 170. Потому 30 человек не глядят ни спорт, ни комедии, ни драмы (рис.8.7).

Задачки

1. Если компьютерный пароль содержит семь знаков, которые могут Определения сочетаний, размещений и перестановок быть цифрой либо буковкой британского алфавита, то сколько существует паролей, начинающихся с буковкы?

В британском алфавите 26 букв. Считая строчные и строчные буковкы различными, получаем 52 знака. 1-ый знак пароля может быть избран 52 методами, другие 6 — 62 методами (т.к. можно использовать числа). Общее число композиций равно

2. Сколько существует методов избрания президента Определения сочетаний, размещений и перестановок, вице-президента, секретаря и казначея посреди членов клуба, включающего 8 студентов последнего курса, 10 студентов предпоследнего курса, 15 второкурсников и 20 первокурсников, если:

1. отсутствуют какие-либо ограничения?

2. президентом должен быть студент последнего курса?

3. студент последнего курса не может быть вице-президентом?

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

Всего имеем 8+10+15+20=53 члена клуба. В первом Определения сочетаний, размещений и перестановок случае президента можно избрать 53 методами, вице-президента — 52, секретаря — 51 и казначея — 50. В конечном итоге методов.

Во 2-м случае есть 8 методов выбора президента. Тогда число композиций равно:

В 3-ем случае начнем выбор с вице-президента. Его можно избрать 45 методами. В конечном итоге число композиций рано

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

• Секретарем выбирают первокурсника. Тогда секретаря можно избрать 20 методами, президента — 33, вице-президента — 32, казначея — 31. Итого

• Секретарем выбирают не первокурсника. Тогда первокурсники вообщем в выборах не выбираются. Секретаря можно избрать 33 методами, президента — 32, вице-президента — 31, казначея — 30, общее число методов равно 982090

Для получения общего числа методов для 4-ого варианта сложим приобретенные Определения сочетаний, размещений и перестановок количества. В конечном итоге число композиций равно 1636800.

1. Сколько существует случайных отображений из огромного количества A в огромное количество B, если |A| = n, а |B| = m? Сколько биективных отображений?

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

Биективное отображение можно выстроить исключительно в том случае, когда m=n. В данном случае, используя решение из примера 1, получаем

2. Решить пример 2, пользуясь только принципом умножения.

3. Сколько существует разных четырехзначных Определения сочетаний, размещений и перестановок положительных чисел, если, по последней мере, две числа в числе совпадают? Числа, начинающиеся с нуля (к примеру, 0001) не считаем четырехзначными.

Всего четырехзначных целых чисел существует 9000. Определим, сколько существует четырехзначных чисел с разными цифрами. Разумеется, первую цифру можно избрать 9 методами. Вторую цифру — также 9 методами (т.к. возникает возможность избрать 0), третью Определения сочетаний, размещений и перестановок — 8 методами, четвертую — 7 методами. Если отнять число четырехзначных чисел с различными цифрами из общего числа четырехзначных чисел, получим разыскиваемое число:

4. Представим, что из 100 опрошенных студентов 50 изучают химию, 53 — арифметику, 42 — физику, 15 — химию и физику, 20 занимаются физикой и арифметикой, 25—арифметикой и химией и 5 студентов изучают все три предмета.

1. Сколько студентов изучают хотя бы один Определения сочетаний, размещений и перестановок из 3-х перечисленных предметов?

2. Сколько студентов не изучают ни один из 3-х перечисленных предметов?

3. Сколько студентов изучают только арифметику?

4. Сколько студентов изучают физику либо химию, но неизучают арифметику?

5. Сколько студентов не изучают ни арифметику, ни химию?

Определения сочетаний, размещений и перестановок

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

Переставляя объекты некого набора, мы обычно располагаем их в различном порядке Определения сочетаний, размещений и перестановок. В этом смысле перестановка — это переупорядочение набора объектов. Для подсчета перестановок довольно пользоваться правилом умножения. Разглядим количество вероятных методов формирования числа, переставляя числа 1, 2, 3, 4 и 5. Варианты вероятных перестановок — это, к примеру, числа 12345, 15342, 32415 и 32415. Для нахождения количества вероятных размещений либо перестановок заметим, что первую цифру можно избрать пятью методами Определения сочетаний, размещений и перестановок, вторую — 4-мя методами, третью — 3-мя методами, четвертую — 2-мя, и только один вариант остается для выбора пятой числа. Потому существует 5! вероятных перестановок. Точно так же, если нужно переупорядочить n объектов, то для этого существует n! методов. В перестановках важен порядок. Числа 51342 и 32415, образованные перестановкой цифр 1, 2, 3, 4 и 5, не совпадают. Не считая того Определения сочетаний, размещений и перестановок, так как перестановки рассматриваются как переупорядочения, то каждый объект можно использовать только один раз.

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

Итак, перестановка — это переупорядочение набора объектов, число Определения сочетаний, размещений и перестановок перестановок n частей рассчитывается как n!.

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

Время от времени случается так, что объектов больше, чем мест их расположения. Представим, к примеру, что в организации — 20 человек и из их требуется избрать президента, вице-президента, секретаря и казначея. Имеются 20 вариантов выбора президента, 19 вариантов выбора вице-президента, 18 методов Определения сочетаний, размещений и перестановок выбора секретаря и 17 — казначея. Таким макаром, получаем

методов выбора должностных лиц. Заметьте, что порядок все еще остается значимым. Есть разница, является ли Иванов президентом, вице-президентом, секретарем либо казначеем. Каждое из размещений на должностях 4 избранных лиц представляет собой различную компанию управления, и хоть какого человека можно выбрать только один раз Определения сочетаний, размещений и перестановок.


opredeleniya-struktura-sbornika-informaciya-i-primeri-voprosi-dlya-samokontrolya-i-uprazhneniya-mnozhestvennij-vibor.html
opredeleniya-termina-usluga.html
opredeleniya-urovnya-dolgovremennoj-adaptacii.html