Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2



Скачать 88.28 Kb.
Дата30.01.2013
Размер88.28 Kb.
ТипКурс лекций

Математика. Курс лекций для студентов специальности Психология


Часть 1. Элементы теории множеств и математической логики
Лекция 2

Элементы комбинаторики
1. Основные правила комбинаторики

2. Сочетания

3. Размещения

4. Перестановки
1. Основные правила комбинаторики
Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько комбинаций, подчиненных тем или иным условиям, можно составить из заданных множеств. Будущему психологу необходимы определенные умения и навыки решения комбинаторных задач. Ему необходимо:

  • уметь грамотно осуществлять перебор возможных вариантов и при этом быть уверенным, что перебор осуществлен правильно;

  • знать общие правила комбинаторики, виды комбинаций и уметь подсчитывать их число по формулам.

Правило суммы. Рассмотрим два конечных непересекающихся множества: , состоящее из элементов, и множество , состоящее из элементов. Пусть элемент из множества можно выбрать различными способами, а элемент из множества - различными способами. Тогда выбор одного из элементов «либо , либо » можно осуществить способами. В общем случае, для непересекающихся множеств , , … , число выборов одного из элементов « из gif" name="object19" align=absmiddle width=27 height=21> или из , …, или из » равно .


Пример 1. Из пункта А в пункт В можно добраться поездом или автобусом, причем между А и В существует 2 железнодорожных и 3 автобусных маршрута. Сколькими способами можно добраться из пункта А в пункт В?

По условию задачи можно выбрать два железнодорожных маршрута и три автобусных. Так как в задаче идет речь о выборе «либо …, либо …», то его, согласно правилу суммы, можно осуществить 2+3=5 способами. Общее число маршрутов из пункта А в пункт В равно 2+3=5.

Правило произведения. Рассмотрим два множества Х и Y. Пусть выбор некоторого элемента из множества можно осуществить различными способами. После каждого из таких выборов из множества элемент можно выбрать различными способами. Тогда выбор упорядоченной пары , то есть элемента « и », можно осуществить способами:






… … … … … …


Пример 2. Пусть , - два множества. Найти число всех упорядоченных пар и перечислить их.

По правилу произведения число упорядоченных пар равно . Составим пары элементов, в которых первый элемент – из множества , а второй элемент - из множества : , , , , , - их ровно шесть.

При решении данной задачи и ей подобных можно воспользоваться схемой, известной под именем «дерева логических возможностей» (рисунок 1.9). В качестве первого элемента можем выбрать или . После каждого сделанного выбора в качестве второго элемента можем выбрать , или , или . Каждой паре элементов соответствует одна «дорожка» (один путь) на схеме. Таких путей 6.






Рисунок 1.9

Правило произведения справедливо как для пересекающихся, так и для непересекающихся множеств , , , …, , .
2. Сочетания


  • Сочетанием из элементов по элементов () называется любое подмножество, которое содержит различных элементов, выбранных их -элементного множества.

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

Число всех возможных сочетаний из элементов по обозначается и вычисляется по формуле

, (1.1)

где - произведение натуральных чисел от 1 до (читается «эн факториал»);

- произведение натуральных чисел от 1 до ;

- произведение натуральных чисел от 1 до .

После сокращения общих множителей в числителе и знаменателе получим более удобную для подсчета формулу

. (1.2)

Пример 3. В группе 25 студентов. Нужно выбрать трех человек на конференцию. Сколькими способами это можно сделать?

Решение. Так как порядок выбранных трех человек не имеет значения, то имеем неупорядоченные выборки без повторения, то есть сочетания. Число сочетаний из 25 по 3 равно - это число способов выбора трех студентов на конференцию.

Пример 4. Вычислить число двухэлементных подмножеств, составленных из элементов 5-элементного множества . Записать эти подмножества.

Решение. В задаче ; ; тогда . Так как сочетания – неупорядоченные подмножества, то записываем их в фигурных скобках:

, , , , ,, , , , .

Приведем свойства сочетаний.

1. ; 2. ; 3. ;

4. - число всех подмножеств множества объема .

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

Пример 5. Имеются учебники по четырем предметам. Сколькими способами можно составить набор из 8 учебников?

Решение. Так как порядок учебников не играет роли, то каждый набор учебников имеет «объем» , в котором будут повторяться учебники по одному и тому же предмету (например, различных авторов). Число сочетаний с повторениями из 4 элементов по 8 равно

.
3. Размещения

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

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

Пример 6. Дано множество . Составим упорядоченные подмножества из трех элементов ( по два (). Получим: , , , , , - всего 6 упорядоченных подмножеств.

  • Размещением из элементов по элементов () называется упорядоченное подмножество , содержащее различных элементов -элементного множества.

Все размещения отличаются друг от друга или составом элементов (в примере 6 - , , ), или порядком расположения элементов в выборке (например, и ).

Число размещений из элементов по элементов обозначается и вычисляется по формуле

. (1.3)

Пример 7. В соревнованиях участвуют 10 команд. Сколькими способами могут распределиться три первых места?

Решение. Нужно найти число всех подмножеств, которые состоят из трех элементов и отличаются составом (номерами команд) или порядком их размещения. Таким образом, имеем дело с размещениями. Первое место может занять одна из 10 команд, второе место – одна из 9 команд, третье место займет одна из оставшихся 8 команд. По правилу произведения . Действительно число размещений из 10 по 3 равно .

  • Размещениями с повторениями из элементов по элементов – это выборки объема , осуществляемые с возвращением их элементов и с их упорядочиванием.

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

Пример 8. Имеется 5 стульев и 7 рулонов ткани различных цветов. Сколькими способами можно осуществить обивку стульев?

Решение. Так как стулья различны, то можно их перенумеровать. Стул № 1 можно обить семью видами ткани; стул № 2 – также семью, …, стул № 5 – семью видами ткани. Каждый способ обивки пяти стульев есть подмножество объема =5 (видов ткани), составленное (выбранное) из элементов множества, содержащего 7 элементов (видов ткани). По правилу произведения выбор упорядоченного подмножества объема может быть осуществлен способами.
4. Перестановки


  • Перестановкой из элементов называется размещение из элементов по элементов.

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

. (1.4)

Пример 9. Сколькими способами можно расставить 5 книг на одной полке?

Решение. Первую книгу можно расставить на 5 мест пятью способами, вторую книгу – четырьмя способами, третью книгу – тремя способами, четвертую книгу – двумя способами, пятую книгу – одним способом. По правилу умножения общее число способов расстановки книг равно . По формуле перестановок число перестановок из 5 равно тоже 120, т.е. .

  • Если в перестановках из общего числа элементов есть различных элементов, при этом первый элемент повторяется раз, второй элемент - раз, …, -й элемент - раз (), то такие перестановки из элементов, называются перестановками с повторениями.

Число перестановок с повторениями из элементов равно

. (1.5)

Пример 10. Сколько различных «слов» (не обязательно имеющих смысл) можно получить, переставляя буквы слова «математика»?

Решение. По условию задачи, ; ; ; ; ; ; . Тогда число перестановок с повторениями равно «слов».
Основные соединения в комбинаторике


Названия, обозначения

Пояснения

Примеры

Перестановки из элементов



Соединения отличаются только порядком элементов.

Число способов поменять местами 5 детей, стоящих в шеренгу



Размещения из элементов по



Соединения отличаются хотя бы одним элементом или порядком элементов.

Число способов распределить 3 различные обязанности между 5 студентами (по одной обязанности на студента)



Сочетания из элементов по



Соединения отличаются хотя бы одним элементом (порядок элементов не учитывается)

; ;

Число способов выбрать 3 делегата на конференцию из 10 студентов









Похожие:

Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconКурс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 1
Понятия «множество», «элемент множества», «элемент принадлежит множеству» относятся к первичным, неопределяемым понятиям современной...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconКурс лекций для студентов специальности Психология Часть линейная и векторная алгебра Лекция 2
Каждой квадратной матрице поставим в соответствие некоторое число, которое будем называть определителем матрицы, и укажем правило...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconКурс лекций для студентов специальности Психология Часть математическая статистика Лекция 4 Проверка гипотез о законе распределения
Распределением признака называется закономерность встречаемости разных его значений. В данной теме будем рассматривать сравнение...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconКурс лекций для студентов специальности Психология Часть математическая статистика Лекция 2
Следующий шаг – получение числовых характеристик выборки, позволяющих глубже понять особенности объекта наблюдения: среднее значение...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconКурс лекций для студентов специальности Психология Часть основы математического анализа Лекция 2
К основным операциям (+, –,, ), которые применяются в элементарной математике, в высшей математике добавляется еще одна – операция...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconЛогинов А. С. Часть Дифференциальное исчисление
В разделе рассматриваются основные понятия теории множеств, определение множества действительных чисел. Приводится необходимая терминология...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconДискретная математика (конспект лекций)
Фгоу впо сибгути. Раздел 1 Основы теории множеств. Раздел 2 Формулы логики. Раздел 3 Булевы функции. Раздел 4 Предикаты и бинарные...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconКомитет образования и науки администрации санкт-петербурга
«Элементы теории множеств» и «Элементы теории вероятности». Этот курс дополняет базовую программу, не нарушая её целостности. Задания,...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconЭлементы математической логики
Простейшую из формальных логических теорий называют алгеброй высказываний, поэтому начнем знакомство с элементами математической...
Курс лекций для студентов специальности Психология Часть Элементы теории множеств и математической логики Лекция 2 iconКурс лекций по высшей геодезии раздел «теоретическая геодезия»
Курс лекций ведется на кафедре прикладной геодезии и фотограмметрии Полоцкого государственного университета для студентов специальности...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org