Перестановки и сочетания

Размещено на http://www.allbest.ru/

ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра высшей математики

Перестановки и сочетания

Выполнил: студент первого курса

(гр. 813) физического факультета

Елисеев Дмитрий

Научный руководитель-

ст. преподаватель Алябьева В.Г.

Пермь, 2009

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

При составлении размещений без повторений из n элементов по k мы получим расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называются перестановками из n элементов, или, короче, n-перестановками.

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

Например, из 3 элементов (a,b,c) можно образовать следующие перестановки:

abc, bac, cab, acb, bca, cba.

Число всех возможных перестановок, которые можно образовать из n элементов, обозначается символом

Таким образом, чтобы узнать, сколько перестановок можно составить из n элементов, надо перемножить все натуральные числа от 1 до n.

(Произведение n первых целых чисел обозначается n! (n факториал))

Пример:

Сочетания

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

Например, из 3 элементов (a,b,c) по 2 можно образовать следующие сочетания:

ab, ac, bc.

Число всех возможных сочетаний, которые можно образовать из n элементов по k, обозначается символом :

(В числителе и знаменателе по k множителей).

Пример:

Полезные формулы:

Например:

Формулы

Число сочетаний из n по k равно биномиальному коэффициенту

При фиксированном n производящей функцией последовательности чисел сочетаний ,

, , … является:

Двумерной производящей функцией чисел сочетаний является

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

Если X-множество, состоящие из n элементов, m?n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.

Количество всех размещений из n элементов по m обозначают

n! - n-факториал произведение чисел натурального ряда от 1 до какого либо числа n

n!=1*2*3*...*n0!=1

(Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны)

Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

Значит, ответ на выше поставленную задачу будет

Задача

Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?

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

Возможно 360 вариантов.

Сочетания с повторениями

Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?

Решение:

Найдем количество всех перестановок из этих цифр: P6=6!=720

0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P5=5!=120.

P6-P5=720-120=600

Сочетания без повторений

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

Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m.

Таким образом, количество вариантов при сочетании будет меньше количества размещений.

Число сочетаний из n элементов по m обозначается .

.

Примеры задач

перестановка сочетание задача

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

Решение:

Так как кнопки нажимаются одновременно, то выбор этих трех кнопок - ние. Отсюда возможно вариантов.

2)У одного человека 7 книг по математике, а у второго - 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Решение:

Так как надо порядок следования книг не имеет значения, то выбор 2ух книг - сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги . Значит всего по правилу произведения возможно 21*36=756 вариантов.

При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Первый игрок делает выбор из 28 костей. Второй из 28-7=21 костей, третий 14, а четвертый игрок забирает оставшиеся кости. Следовательно, возможно .

Размещения и сочетания с повторениями

Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Например: в задачах на числа - цифры. Для таких задач при размещениях используется формула , а для сочетаний .

Примеры задач

Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?

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

В кондитерском магазине продавались 4 сорта пироженных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пироженных.

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

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

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

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

Приведем несколько примеров использования этой формулы.

Р5 = 5! = 1· 2 ·3 · 4 ·5 = 120; Р2 = 2! = 1· 2 = 2; Р1 = 1! = 1.

Пример Составить все размещения из трех букв А, В, С.
Решение. АВС, АСВ, ВАС, ВСА, СВА, САВ. Проверим по формуле:

Р3 = 1·2·3 = 6.

Список использованной литературы

1. Виленкин Н.Я. Комбинаторика. М.: Наука, 1969, гл. 2.

2. Виленкин Н.Я. Популярная комбинаторика. М.: Наука.

Размещено на Allbest.ru