Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений




Скачать 72.42 Kb.
НазваниеЛекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений
Дата конвертации01.09.2013
Размер72.42 Kb.
ТипЛекция
Лекция №1.

Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений.

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

В теории вероятностей принято говорить не о комбинациях, а о выборках. Поэтому мы будем придерживаться термина «выборка».

В комбинаторике рассматриваются виды выборок — пере­становки, размещения, сочетания.

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

Допустим, в ящике имеется п разноцветных шариков. Про­извольным образом вынимаем один шарик. Сколькими спосо­бами можно это сделать? Конечно, п способами. Теперь эти п

шариков распределим по двум ящикам: в первом т шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами можно это сделать? Из первого ящика шарик можно вынуть т разными спосо­бами, из второго — k разными способами. Таким образом, один шарик из этих двух ящиков можно вынуть шарик

n = m + k способами. Рассмотрение этого примера позволяет сформулировать правило суммы:

Если, некоторый объект А можно выбрать т способами, а объект В k способами (не такими, как А), то объект «либо А, либо В» можно выбрать m + k способами.

Это правило называется правилом суммы.

Рассмотрим вопрос о том, сколько можно записать двузначных чисел в де­сятичной системе счисления?

Поскольку число двузначное, число десятков может прини­мать одно из девяти значений: 1, 2, 3, 4, 5, 6, 7, 8, 9. Число еди­ниц может принимать те же значения и может, кроме того, быть равным нулю.

Если цифра десятков 1, цифра единиц может быть 0, 1, 2, ..., 9 — всего 10 значений. Если цифра десятков 2, то вновь цифра единиц может быть равна 0, 1, 2, ..., 9. Всего получаем 90 дву­значных чисел.

Обобщим полученный результат. Пусть данное множество из n = m + k элементов разбито на два подмножества, состоящие соответственно из m и k элементов. В нашем случае: m –число цифр, при помощи которых можно записать число десятков, значит m равно 9; k – число цифр, при помощи которых можно записать число единиц, а значит k равно 10. Пусть из подмножества, со­держащего m элементов, выбирается один элемент и независимо из подмножества, содержащего k элементов, выбирается один элемент. Спрашивается: сколько различных пар элементов при этом образуется? Очевидно, что каждому элементу из первого множества можно поставить в пару каждый элемент второго множества, а значит всего можно составить общее число пар N=mk.

Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта A) k способами, то пары объектов А и В можно выбрать mk способами.

Это и есть правило произведений.

Генеральная совокупность без повторений — это набор неко­торого конечного числа различных элементов:

Наглядному представлению такой генеральной совокупнос­ти может послужить набор из п разноцветных шаров, в которой никакие два шара не имеют одинаковой окраски..

Выборкой объема будем называть произвольную группу из т элементов данной генеральной совокупности. На­глядному представлению такой выборки может служить последовательность из т шаров, выбранная из имеющегося множества.

Каким минимальным признаком может отличиться одна выборка объема т от другой выборки такого же объема? Это равносильно вопросу: каким минимальным признаком могут отличаться две линейки из шариков, построенная из их одина­кового количества?

Минимальным признаком, отличающим од­ну выборку объема т от другой выборки такого же объема, может быть:

1) их различие по крайней мере одним элементом

2) их различие порядком расположения элементов.

Назовем такие выборки размещениями без повторений из п элементов по т.

Можно построить такой наглядный граф наших рассуж­дений :




Отсюда следует определение понятия:

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

Характерный пример размещений без повторений — вся со­вокупность четырехзначных номеров, в каждом из которых нет пов­торения цифр.

Число размещений из п элементов по m договоримся обо­значать . Попробуем определить это число.

Пусть имеем п элементов. Первый элемент можно выбрать п способами. Второй приходится выбирать из оставшихся п — 1 элементов, поэтому второй элемент можно выбрать п — 1 спо­собом. Тогда по правилу произведения пары двух элементов можно об­разовать п (п-1) способами. Третий элемент придется отбирать из числа оставшихся п-2 элементов. Это можно сделать п-2 способами. Тогда опять по правилу произведения тройки элементов можно образовать п(п-1) (п-2) способами. Аналогично чет­верки можно образовать п (п- 1) (п- 2) (п- 3) способами, а раз­мещения по m элементов п (п — 1) (п — 2).. . (п-(т- 1)) спосо­бами. Таким образом,



Преобразуем полученную формулу, умножая и деля правую часть на произведение:

. Тогда выведенная формула имеет вид:


.


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

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

Характерный пример перестановок без повторений — вся со­вокупность всех десятизначных номеров, в каждом из которых нет повторения цифр.

Обозначим число перестановок объема п символом Рп. Тогда по определению



Среди размещений без повторений из п элементов по m (m < п) можно выделить такие, которые отличаются одно от другого только первым признаком, а именно по крайней мере одним элементом. Значит:

Сочетаниями без повторений из п элементов по m называют­ся такие размещения без повторений из п элементов по т, ко­торые одно от другого отличаются хотя бы одним элемен­том.

Число таких сочетаний обозначается символом . Разу­меется, при т = п .

Характерный пример сочетаний без повторений — всевоз­можные варианты состава делегации в количестве, например, четырех человек от коллектива, в котором 15 человек.

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

,

откуда

.


В
се нами рассмотренное в этой лекции можно привести к та­кой обобщающей схеме:


Примеры использования полученных формул:

Задача 1. На тренировках зани­маются 12 баскетболистов. Сколько может быть образо­вано тренером разных стар­товых пятерок?

Решение: Так как при составлении стартовой пятерки тренера интересует только состав пя­терки, то достаточно опреде­лить число сочетаний из 12 элементов по 5:

.


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

Решение: Ясно, что в этом случае на каждой горизонтали и каждой вертикали шахматной доски может быть расположено только по одной ладье. Число возможных позиций — число перестано­вок из 8 элементов:

.

3. Для научной экспедиции необходимо укомплектовать следую­щий команду: начальник экспедиции, первый его заместитель, второй заместитель, два сотрудника и один стажер. Начальник и его заместители может быть отобрана из числа 25 кандидатов наук, два сотрудника — из числа 20 специалистов, в совершенстве знающих характер предстоящей работы, и стажер — из числа 8 наиболее подготовленных студентов. Сколькими способами можно укомплектовать команду экспедиции?

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

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

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

Задачи для самостоятельного решения:

  1. В классе 30 учеников. Необходимо избрать старосту, члена ученического комитета и ответственного за дежурство. Сколькими способами можно об­разовать эту тройку, если одно лицо может зани­мать только один пост? (Ответ 24360)

  2. Сколько разных пятизначных чисел можно составить из цифр 1, 2, 3, 4 и 5 при условии, что ни одна цифра не повторяется? (Ответ: 120)

  3. Игрок сначала бросает белую игральную кость, потом черную. Сколько может быть случаев, когда число очков, поя­вившихся на белой кости, больше числа очков, появившихся на черной? (Ответ 15)

  4. Сколько разных стартовых шестерок можно образовать из числа 10 волейболистов? (Ответ 210)

  5. В одной арабской сказке речь идет о такой задаче. Вокруг костра сидят 12 разбойников. Каждый из них смертельно ненавидит двух ближайших соседей. С целью спрятать награбленное необходимо выделить 5 разбойников. Сколькими способами атаман может назначить пятерых так, чтобы между ними не было распрей? (Ответ 36).

Похожие:

Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconУрал—батыр
Ночь, глубокая ночь повсюду. Не видно ни звездочки, ни огонька, лишь только ночь вокруг – без конца и без начала, без верха и низа,...
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconКурс лекций Москва 2002 Лекция 1 о критериях и смысле периода Новое время
Лекция 1 о критериях и смысле периода Новое время «Все части нашего мира так связа­ны и соединены одна с другою, что я полагаю невозможным...
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconМетодика фитнеc-формирующего массажа. Работа с проблемными зонами живота
Скручивания корпусом вперед до максимального напряжения мышц живота. Сильно вперед, медленно возврат в исходное положение. 1 подход...
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconСкучали ли вы без меня?
Безумно! Признаюсь. Тема, которая волнует нас это тема ликвидация бренда Миракс. Или что?
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconКомплексы упражнений для коррекции телосложения у девушек (учитывающие коррекции телосложения)
И. п. – стоя на коленях. Ноги врозь, носки повернуты наружу. Руки на пояс. Сесть на пол, стараясь коснуться пола ягодицами, выполнить...
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconРоссийская федерация федеральный закон
Настоящий Федеральный закон определяет общие принципы, содержание и меры социальной поддержки детей-сирот и детей, оставшихся без...
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений icon«Без многого может обойтись человек, только не без человека»
Я считаю, что высказывание Людвига Берне, немецкого публициста и писателя, о том, что «без многого может обойтись человек, только...
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconВы любите друг друга?
От общей суммы заказа Вы вносите до даты торжества, оставшуюся сумму Вы оплачиваете равными частями в течение года после даты торжества....
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconИнструкция по измерению фигуры ребёнка
Ребенок может быть одет в майку, футболку, без обуви. Все измерения производят достаточно плотно по фигуре, без прибавок. Ребенок...
Лекция №1. Тема. Принципы комбинаторики. Генеральная совокупность без повторений. Выборки без повторений iconБез тайн
В75 Без таємниць про залежності та їхнє лікування. – Пер з пол. – К.: Сфера, 2004. – 270 с
Разместите кнопку на своём сайте:
kaz2.docdat.com


База данных защищена авторским правом ©kaz2.docdat.com 2013
обратиться к администрации
kaz2.docdat.com
Главная страница