Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

 

ПРИМЕР: Множества (a, b, c) и (a, c, b) есть различные упорядо­чен­ные множества, состоящие из одних и тех же трех элементов.

 

Сформулируем основные правила комбинаторики.

1. Правило суммы. Пусть из множества А элемент а1 можно выбрать n1 способами, элемент а2 – другими n2 способами, а элемент а3n3 способами, отличными от предыдущих. Тогда выбор одного из элементов а1, или а2, или а3 можно осуществить (n1 + n2 + n3) способа­ми.

ПРИМЕР: Пусть в корзине содержится 7 апельсинов, 5 бананов и 10 яблок. Тогда выбор одного из фруктов (или апельсина, или банана, или яблока) можно сделать 22 способами (7 + 5 + 10 = 22).

 

2. Правило произведения. Пусть из множества А элемент а1 можно выбрать n1 способами, а после этого выбор элемента а2 можно осуществить n2 способами, а после этого выбор элемента а3 можно осуществить n3 способами. Тогда все три элемента в указанном порядке могут быть выбраны способами.

 

ПРИМЕР: Пусть в спортивном велосипеде имеются 3 ведущие звездочки и 4 ведомые. Сколько всего передач имеется в велосипеде?

Очевидно, что каждая передача определяется выбором одной ведущей и одной ведомой звездочки. Следовательно, число всех передач совпадает с числом выборов одного элемента из трех и другого элемента из четырех и равно: 3 ∙ 4 = 12.

 

Пусть некоторое множество А содержит n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов. Число всех таких размещений обозначается (читается: «А из эн по ка») и определя­ется по формуле: .

 

ПРИМЕР: Сколько сигналов можно составить из 6 флажков различного цвета, взятых по два?

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

 

Размещение из n элементов по n элементов называется пере­становками из n элементов. Число всех таких перестановок обозначается и определяется по формуле: .

ПРИМЕР: Сколько трехзначных чисел можно образовать из цифр 1, 2 и 3, если каждая из них может входить в изображение числа только один раз?

Очевидно, что искомое число есть число перестановок из 3 элементов, равное: .

 

Пусть некоторое множество А содержит n элементов. Каждое его неупорядоченное подмножество, состоящее из k элементов, называется сочетанием из n элементов по k элементов. Число всех таких сочетаний обозначается (читается: «цэ из эн по ка») и определяется по формуле: .

ПРИМЕР: Сколькими способами можно выбрать два шара из ящика, содержащего 8 шаров?

Очевидно, что искомое число способов будет равно числу сочетаний из 8 элементов по 2 элемента, т.е.

 

Достаточно несложно (убедитесь в этом сами) показать справедливость еще одной полезной формулы комбинаторики:

 

.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.