Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Правила суммы и произведения

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

Пусть Хх, Х2, ..., Хк попарно не пересекающиеся множества, т.е. X, П X• = 0 при / Ф у. Тогда выполняется равенство

Такой выбор объектов называется несовместными событиями.

Теорема 1.9. Правило суммы

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

Если объект* из М может быть выбран п способами, а объекту может быть выбран т способами, то упорядоченная пара <*, у> (когда выбирается как объект*, так и объекту) может быть выбрана пт способами.

Обобщая на к объектов, получаем, что выбор упорядоченной последовательности < Хх, ..., Хк > может быть осуществлен пхп2---пк способами.

Теорема 1.10. Правило произведения

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

Рассмотрим несколько задач. Во всех случаях мы выбираем и объект*, и объекту, т.е. и то, и другое.

Задача 1.21

Сколькими способами можно задать число палиндром длиной 5?

Решение.

Число палиндром можно читать как слева направо, так и справа налево. Число от этого не изменяется. Например, 70507 или 93639.

Тогда первый разряд может быть от 1 до 9, второй и третий разряды могут быть от 0 до 9. Причем у палиндрома 1-й и 5-й разряды между собой совпадают, 2-й и 4-й также совпадают. Цифры могут повторяться, например число 00000 и 11111 также палиндромы. Тогда по правилу произведения получаем

Л-9 ? 10 • 10 = 900.

Задача 1.22

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

Решение.

В данном случае мы выбираем пару <*, у> без повторений. Старосту можно выбрать 20 способами, а его заместителя 20 - 1 = 19 способами. По правилу произведения 20 • 19 = 380.

Задача 1.23

В урне находится 12 шаров. Три из них красные, пять белые, остальные — синие. Мы выбираем из урны два разноцветных шара. Сколькими способами это можно сделать ?

Решение.

В данном случае мы выбираем пару <х, у> без повторений.

Если пара <красный, синий>, то по правилу произведения таких способов 3-4=12.

Если пара <красный, белый>, то по правилу произведения таких способов 3-5=15.

Если пара <белый, синий>, то по правилу произведения таких способов 5 • 4 = 20.

У нас получается три вида несовместных событий: либо пара скрасный, синий>, либо скрасный, белый>, либо <белый, синий>. По правилу суммы получаем 12 + 15 + 20 = 47 различных способов выбора.

Задача 1.24

Сколько существует четырехзначных чисел, которые делятся на 5?

Решение.

В данном случае мы выбирает четверку «ос, у, і, и>> с повторениями, причем последний элемент н> — либо 0, либо 5 по правилу делимости, а первый х — не может быть 0, иначе число не четырехзначное.

По правилу произведения получаем 9 • 10 • 10 • 2 = 1800.

Задача 1.25

В слове НИЯУ МИФИ выбирают по две буквы (все буквы не обязательно различны) и составляют из них слова. Сколькими способами это можно сделать?

Решение.

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

N=N^ + N2,

где — количество слов из разных букв, а УУ2 — количество слов из одинаковых букв.

Количество различных букв равно 6, п = 6, из них и осуществляется выбор пары.

Результат выбора пары букв ос, у> определяется по формуле для числа сочетаний:

0 2!(6 - 2)!

После того как выбор произведен, из пары букв «ос, у> составляют слова. Количество таких слов вычисляем по формуле для перестановок:

Р2 = 2! = 2.

Мы совершаем два события последовательно: выбираем буквы и составляем слова, следовательно, по правилу произведения получаем решение

= С62Р2 =15-2 = 30.

В случае выбора одинаковых букв слов столько, сколько различных букв, т.е. п:

И2 = п = 6.

Таким образом, общее количество слов

N=N1 + N2 = 30 +6 = 36.

Задача 1.26

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

Решение.

Первый разряд числа может быть только 1, остальные — содержать любую из 10 цифр. Получаем, используя правило произведения:

А = 1 • 10- 10- 10= 1000.

Задача 1.27

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

Решение.

Первые два символа пароля могут быть в виде любой из 26 букв латинского алфавита, т.е. 26 - 26 = 676 возможностей.

С третьего по шестой разряды могут быть сформированы из 36 символов, в которые входят 26 букв и 10 цифр (правило суммы).

Тогда по правилу произведения получаем решение

Л = 676 • 36 • 36 • 36 • 36 = 1 135429416.

 
<<   СОДЕРЖАНИЕ   >>