Формула размещения с повторениями – Перестановки, размещения и сочетания. Формулы.

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

Ank — количество размещений с повторениями

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

	Ank	— количество размещений без повторений
	Ak	n(n1)(n		2)…(n k 1)
	n
	Введём такое понятие:
	0! 1
	n! (n 1)!n
	( n! — «эн факториал»)
	Тогда Ank		n!			(27)
			(n k)!

Пример.

Сколькими способами в группе из 24 студентов можно выбрать 1 старосту, 1 финорга и 1 профорга? (3 человека)

A243 2421!! 24 23 22 12144

Перестановки без повторений

Рассмотрим частный случай. Если речь идёт о размещении без повторений и k n, то говорят оперестановках n элементов и обозначают черезPn P(n)

	P(n)	n!		n!	n!	(28)
		(n n)!
				0!

Пример.

Сколько различных слов можно получить перестановкой букв слова «граф»?

P(4) 4! 24

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

Сколько различных слов можно получить перестановкой букв слова «математика»?

10! 10! 151200 2!3!2! 24

Пусть у нас имеется:

n1 — количество предметов первого типа,n2 — количество предметов второго типа,

…

nk — количество предметов типаk.

P(n1 ,n2 ,…,nk ) — количество перестановок с повторениями.

	P(n1 , n2	,…, nk )	(n1 n2 …nk )!		(29)
			n1!n2 !…nk !

Числа P(n1 ,n2 ,…,nk ) называются полиномиальными коэффициентами.nk ! — число способов перестановок предметовk-тоготипа.

Пример.

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

	P(2,2,2,1,1)	8!		8!	7! 5040
		2! 2! 2! 1!1!
				8

			Сочетания с повторениями
C k	n
			— число сочетаний с повторениями.
n	или
	k

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

	Cnk	n!			(30)
		k!(n	k)!

Числа Cnk называются биномиальными коэффициентами.

Пример.

Подсчитать вероятность угадывания ровно 4 номеров в спортлото «5 из 36».

		C 4	C1	9,55 10 5
	P	5	31
		C365

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

Cnk — число сочетаний с повторениями

Введём такую систему: k элементов обозначим точками, нарисуем их в одну линию и разделим ихn-1неразличимыми перегородками, причём количество неразделённых элементов будет означать, сколько раз элемент повторяется (если две перегородки стоят подряд, то это означает, чтокакой-тоэлемент ни разу не используется в данном сочетании).

Тогда каждому сочетанию с повторениями из n поk можно однозначно поставить в соответствие перестановку с повторениями:

P(k,n 1)		(k n 1)!	Cnk k1
		k!(n 1)!
Cnk Cnk k1		(31)

Пример.

Сколькими способами может быть осуществлена покупка 15 открыток, если есть только 3 типа открыток?

C15C1517! 136

3 17 15! 2!

Формула бинома Ньютона

(a x)2	(a x)(a x) aa ax xa xx a2 2ax x2
(a x)3	aaa aax axa xaa xxa xax axx xxx a3 3a2 x3ax2 x3
(a x)n	anCn1an1 x … Cnkan kxk… xn(32)
	n
(a x)n	Cnkxkan k	(33)
	k 0

(x y)6x66x5y 15x4y 220x3y315x2y 46xy5y6

Свойства

1)Cn0Cnn 1, Cn1Cnn 1n

2)CnkCnn k

	Cnn k	n!			n!		Cnk
		(n k)!(n n k)!			(n k)!k!

3)следствие из бинома Ньютона Cn0 Cn1 Cn2 … ( 1)n Cnn 0

4)Cn0Cn1Cn2… Cnn 2n

5)свойство арифметического треугольника

Cnk1 CnkCnk1

Доказательство.

CnkCnk1

n!

n!

n!(n k1)

n!k

k!(n

k)!

(k 1)!(n k 1)!

k!(n k)!(n k

1)

(k 1)!(n k 1)!k

n!(n k1)

n!k

n!n n!k n! n!k

n!(n 1)

(n 1)!

Cnk1

k!(n k1)!

k!(n k1)!

k!(n k1)!

k!(n 1k)!

k!(n k1)!

Полиномиальная формула

(x1 x2 …xm )n (x1 x2 …xm )(x1 x2 …xm )…(x1 x2 …xm )

x1n …x1k1 x2k 2 …xmkm …

После приведения подобных слагаемых коэффициенты при x1k1 x2k 2 …xmkm получатся равнымиP(k1, k2 ,…, km ).Тогда справедлива полиномиальная формула:

(x1 x2 …xm )n	P(k1 ,k2 ,…,km )x1k1 x2k2 …xmkm
ki N0		(34)
k1k2	… kn	n

Пример.

(x y z)4

P(0,0,4) 1

P(0,1,3) 4

P(0,2,2) 6

P(1,1,2) 12

(x y z)4 (x4 y4 z4 ) 4(xy3 x3 y xz3 x3 z yz3 y3 z)6(x2 y2 x2 z2 y2 z2 ) 12(x2 yz xy2 z xyz2 )

Формула включений и исключений

На предприятии работают 35 человек. 11 человек владеют французским языком, 21 человек владеют английским языком, 13 человек владеют немецким языком. И английским, и немецким языками владеют 6 человек. Английским и французским языками владеют 7 человек. Немецким и французским языками владеют 3 человека. Всеми тремя языками владеют 2 человека. Сколько людей не владеют ни одним из этих языков?

Итого 31 человек владеют иностранными языками.

35 31 4

или

35 11 21 13 6 7 3 2 4

Ответ: 4 человека не владеют ни одним из языков.

Пусть дано N — количество предметов иn свойств, которыми эти предметы могут обладать, а могут и не обладать. Обозначим их через1 ,2 ,…,n . Если предмет не

обладает свойством i , то будем обозначать так:

i .

N(

,

,…,

) N N (1 )N (2 ) …N (n )N(1 ,2 ) …N(n 1

, n )

1

2

n

(35)

N(1 ,2 ,3 ) … ( 1)n N (1 ,2 ,…,n )

Формула (35) называется формулой включений и исключений.

Доказательство.

Метод математической индукции.

1) Проверка при n 1.

N(

1

) N N(1 ) — верно.

2) Допустим, что

N(

,

,…,

) N N (1 )N (2 ) … ( 1)k N(1 ,2 ,…,k )

1

2

k

3) Докажем это и при n k 1.

N(

,

,…,

, k 1 )N (k 1 )N (1 ,k 1 )N (2 ,k 1 ) … ( 1)k N(1 ,2 ,…,k 1 )

1

2

k

N(

,

,…,

,

) N (

,

,…,

) N (

,

,…,

, k 1 )N N (1 )N (2 )

1

2

k

k 1

1

2

k

1

2

k

… N (k )N (k 1 )N (1 ,2 ) …N (1 ,k 1 ) … ( 1)k 1 N(1 ,2 ,…,k 1 ) Вывод: на основании метода математической индукции утверждаем, что формула

(35) справедлива для любых натуральных чисел n.

studfiles.net

17) Размещения и сочетания с повторениями – определение, формулы для расчета числа вариантов.

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

8. Пусть дано множество M={1,2,3,4,5}. Тогда размещениями с повторениями из 5 элементов по 2 будут (1,1), (1,2), (2,1), (2,2), …,(5,1) и т.п. – любые упорядоченные пары из 2 элементов множества М.

Количество всех размещений с повторениями обозначим =Â(n,k). Поскольку в таком наборе из k элементов на каждом из k мест может стоять любой из n элементов исходного множества, число размещений с повторениями равно nn…n = n^k.  .

В отличие от выборок без повторений, количество выбираемых объектов может быть больше, чем количество типов, т.е. может быть k  n. Если вернуться к примеру 2.12 (а), то можно рассматривать и 10-разрядные числа.

1. (о мощности множества P(M) )

Для конечного множества M |2^M| = 2^|M|.

Доказательство:

Пусть конечное множество M состоит из n элементов, M = {x₁, …, x_n}. Сопоставим каждому его подмножеству двоичный вектор длины n. Если x_i входит в подмножество, то на i-м месте в этом векторе будет стоять 1, иначе – 0. Поскольку каждая компонента вектора может принимать только значения 0 или 1, а всего таких компонент n, то число различных векторов составит 2

n. 

Следствие:

Можно сгенерировать все подмножества конечного множества M, перечислив некоторым способом все наборы из нулей и единиц длины n.

Можно выполнять такую генерацию различными способами (например, все наборы с одной «1», все с двумя «1», …). Это можно сделать наиболее эффективно, используя т.н. бинарный код Грея. Алгоритм построения бинарного кода Грея позволяет генерировать последовательность всех подмножеств n-элементного множества таким образом, что каждое последующее подмножество получается из предыдущего добавлением или удалением единственного элемента. Подробно этот алгоритм рассматривается при выполнении лабораторной работы.

Определим отношение эквивалентности на множестве размещений с повторениями из n элементов по k: (a₁,a₂,…,

a_k) ~ (b₁,b₂,…,b_k)   cM число элементов a_i = c совпадает с числом элементов b_j = c.

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

9. В примере с множеством M={1,2,3,4,5} сочетания с повторениями из 5 элементов по 2 будут отличаться от размещений тем, что одинаковые по составу наборы будут независимо от порядка элементов в них считаться эквивалентными: (1,1), (1,2)~(2,1), (2,2), (5,2) и т.п.

При рассмотрении выборок с повторениями число n

более наглядно трактуется как количество имеющихся в наличии типов объектов, а k – количество непосредственно выбираемых объектов. Раз объекты выбираются с повторениями, неважно, каково их реальное количество для каждого из типов. Можно считать их неисчерпаемыми.

Число всех сочетаний с повторениями обозначается =Ĉ(n,k) и вычисляется по формуле: Ĉ(n,k)= (2.2)

10. Пусть в кондитерской продается 10 различных видов пирожных. (n=10 – число типов). Сколькими способами можно купить 12 пирожных? (k=12). Ĉ(10,12)=C(10+12–1,12)=C(21,12)=21!/(12! (10–1)!)= 21!/(12! 9!).

18) Биномиальные коэффициенты. Теорема о свойствах биномиальных коэффициентов. Треугольник Паскаля.

Число сочетаний C(n,k)=– число различных k-элементных подмножеств n-элементного множества – встречается в формулах решения многих комбинаторных задач. Например, для определения числа подмножеств n-элементного множества, удовлетворяющих некоторому условию, задача разбивается на составные части: рассматриваются отдельно 1-элементные подмножества, 2-элементные и т.д., затем результаты складываются.

Числа =называютсябиномиальными коэффициентами.

2. Число обладает следующими свойствами:

1. ; 2. ; 3.

Доказательство. 1. ==

2. ===== ===.

3. = ====.

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

В этом равнобедренном треугольнике каждое число (кроме боковых единиц) является суммой двух стоящих над ним чисел. Тогда число сочетаний C(n,k) находится в (n+1) ряду на (k+1) месте. C(5,2)							1							0
						1		1						1
					1		2		1					2
				1		3		3		1				3
			1		4		6		4		1			4
		1		5		10		10		5		1		5
	…		…		…		…		…		…		…

19) Бином Ньютона и следствия.

3. (Бином Ньютона) При любых x, y  R (x+y)ⁿ = .

Доказательство: По индукции.

База: n =1: (x+y)¹ = x+y = 1x¹y⁰+1x⁰y¹=x¹y⁰+ x⁰y¹= .

Индукционный переход: (x+y)ⁿ=(x+y)^n–1(x+y) = x+ y=x¹y^n–1+x²y^n–2+ …+x^n–1y¹+xⁿy⁰+x⁰yⁿ+x¹y^n–1+x²y^n–2 + …+x^n–1y¹= (+)·x¹y^n–1+ (+)·x²y^n–2+…+(+)·x^n–1y¹+ (xⁿy⁰+ )·x⁰yⁿ= |=;=| =x¹y^n–1+x²y^n–2 +…+x^n–1y¹+xⁿy⁰+ x⁰yⁿ= .

Следствие 1. 2ⁿ = . Действительно, 2ⁿ = (1+1)ⁿ = .

Следствие 2. . Действительно, 0= (–1+1)ⁿ = .

1. ; 2.(Тождество Коши).

Доказательство:

1. 0·+1·+2·+…+(n–1)·+n·=(0+n)·+(1+n–1)·+ (2+n–2)·+…=n/2·.

2. – это число способов выбратьk предметов из m+n предметов. Их можно выбирать в два приема: сначала выбрать i предметов из первых n предметов, а затем недостающие k–i предметов – из оставшихся m предметов. Отсюда общее число способов выбрать k предметов составляет .

studfiles.net

Комбинаторная теория

X 1 , X 2 ,…, X n

Комбинаторная теория

Комбинаторика (комбинаторная теория) – один из древнейших разделов математики. В средневековой Европе комбинаторика развивается совместно с теорией вероятностей и выделяется в самостоятельный раздел в 1666 году Лейбницем, который придумал это название и написал книгу «Рассуждения о комбинаторном искусстве». Предметом исследований комбинаторики являются всевозможные комбинации элементовконечных множеств. Рассматриваются комбинации с учётом порядка перечисления элементов или без учёта, комбинации с повторениями и без повторений.

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

Исчисление конечных сумм

…

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

Пусть даны два множества X иY такие, чтоX ∩Y = . ТогдаX Y=X+Y . Другими словами: количество элементов объединения двух не пересекающихся множеств равно сумме количеств элементов этих двух множеств.

А что если X ∩Y ≠ , то есть множестваX иY пересекаются? Тогда, очевидно, что так как у этих двух множеств есть общие элементы, то количество элементов их объединения будет меньше чем сумма количеств элементов по отдельности. Нетрудно догадаться, что эту разницу в количестве дадут общие элементы этих двух множеств, так как простым суммирование количеств эти элементы будут посчитаны дважды, значит из суммы количеств нужно вычесть количество общих элементов:X Y=X+Y−X ∩Y .

Далее, пусть дано n множеств таких, чтоX i∩X j=,i≠j . ТогдаX 1 X 2…X n=X 1+X 2+ …+X n . Другими словами: количество элементов семейства не пересекающихся множеств равно сумме количеств элементов множеств его составляющих. Это правило носит названиеправило сложения.

В случае же, если множества X 1 , X 2 ,…, X n пересекаются, очевидно, столь простым правилом не обойтись, так как один и тот же элемент может принадлежать двум или более множествам. Подробности этого случая обсуждаются в методе включения и исключения.

Правило умножения

Пусть даны два множества X иY. ТогдаX ×Y=X Y . Другими словами: количество всех упорядоченных пар равно произведению количеств элементов исходных множеств.

Далее, пусть дано n множествX 1 , X 2 ,…, X n . ТогдаX 1×X 2×…×X n=X 1 X 2…X n . Другими словами: количество упорядоченных последовательностей равно произведению количеству элементов исходных множеств.

В случае, если X 1=X 2=…=X n , тоX n=X n .

14 Симоненко Е.А. Дискретная математика. Лекции

Метод включения и исключения

Пусть даны n				множеств X 1 , X 2 ,…, X n возможно	попарно пересекающихся. Тогда
X 1 X2 … Xn =( X1 + X2 +…+ Xn )
−( X 1∩X 2 +X 1∩X 3 +…+X n−1∩X n )
+( X 1∩X 2∩X 3 +…+X n−2∩X n−1∩X n )
+(−1)n−1 X	1	∩ X	2	∩…∩X
				n
n
или ∑(−1)k−1 S k (X 1, X 2, …, X n) , гдеS k (X 1, X 2, …, X n)					является суммой	X i1∩…∩X ik по
k =1						X 1 , X2 ,…, Xn .
всем возможным пересечениям ровно k различных множеств из множеств

(Доказательство смотри в [Кузьмин: комбинаторика].)

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

Перестановкой элементов множестваX,X =n , называется последовательность из элементов этого множества длиныn. Различные перестановки одного и того же множества отличаются друг от друга только порядком размещения его элементов. Например, выпишем все перестановки множестваX ={1,2, 3} : (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) .

Выясним, сколько различных перестановок можно получить из множества с n элементами? Для этого будем строить произвольную перестановку по одному элементу по очереди и считать количество различных вариантов выбора элемента множества. Итак, для задания значения для первого элемента произвольной перестановки у нас есть возможность выбора изn элементов. После выбора первого элемента перестановки у нас остаётсяn – 1 элемент и, значит, второй элемент перестановки мы можем выбратьn – 1 способами. Аналогично рассуждаем и для всех остальных элементов перестановки по очереди вплоть до последнего, выбора для которого уже не остаётся (в исходном множестве остаётся только один не выбранный элемент). Таким образом, по правилу умножения мы получаем следующую формулу:

Pn=n (n−1) …1 ,

где Pn обозначает количество всевозможных перестановок множества сn элементами.

Произведение n (n−1) …1 называют факториалом и обозначаютn! . Это число нам ещё встретится. (По определению считают, что0 !=1 .)

Иногда нас интересует только порядок следования элементов, но не то с какого элемента последовательность начинается. Например, для множества X ={1,2, 3} различными будут считаться только такие перестановки: (1,2,3),(1,3,2) . Назовёмциклическим сдвигом влево

последовательности	(x1, x2, … , xn−1 , xn)	последовательность	(x2, … , xn−1 , xn , x1) ,	а
циклическим сдвигом	вправо – последовательность (xn , x1, x2, … , xn−1) . Тогдациклической

перестановкой называется перестановка, получающаяся из некоторой другой циклическим сдвигом вправо или влево. Назовёмосновными перестановки, которые нельзя получить друг из друга посредством циклических сдвигов. Очевидно, что количество циклических перестановок некоторой последовательности равноn, включая её саму. Тогда количество всех основных перестановок равно (n−1)! .

Размещения

Рассмотрим теперь всевозможные перестановки элементов множества X,X =n , произвольной длиныk. Такие перестановки с выборомk элементов изn называют

Комбинаторная теория	15
размещениями. Например, выпишем все размещения по два для множества	X ={1,2, 3} :
(1,2),(1,3),(2,1),(2,3),(3,1),(3,2) .

Выясним, сколько возможно сделать размещений из n элементов поk. Для этого поступим также как и при выяснении количества перестановок элементов множества за той лишь разницей, что у нас будет толькоk элементов: первый элемент множества мы можем выбратьn разными способами, второй –n – 1 разными способами, и так далее, и, наконец последнийn−k+1 разными способами. Таким образом по правилу умножения получаем:

Ank=n (n−1) … (n−k+1)=	n!	.
(n−k)!

Очевидно, что Ann=n! даёт нам число перестановок.

Сочетания

Как уже известно, множество всех возможных комбинаций элементов некоторого множества X называется булеаном множестваX и обозначается2X . (Позже мы выясним, чему равно2X , то есть сколько всего возможно построить подмножеств из некоторого множестваX.) Но часто нас интересуют не все возможные комбинации, а только с определёнными свойствами. В частности, подмножества множестваX,X =n , с определённой мощностьюk называютсочетаниями из n по k. Например, выпишем все сочетания по два для множества

X ={1, 2,3} : {1, 2},{1, 3}, {2,3} .

Возникает вопрос, а сколько возможно сочетаний из n поk? Давайте на время забудем о том, что порядок перечисления элементов множества не важен, тогда количество сочетаний есть

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

должны уменьшить получившиеся число на количество всех возможных порядков размещения, что есть на количество перестановок из k элементов, то есть k ! . Таким образом, получаем следующую формулу:

	Cnk =n (n−1) … (n−k +1)	=	n!	,
			k ! (n−k)!
	k !

где Cnk обозначает количество всех возможных сочетаний изn элементов поk.

Число Cnk также называютбиномиальным коэффициентом. Его свойства мы рассмотрим позже.

Вернёмся к булеану 2X и попытаемся выяснить, чему равно2X . Очевидно, что количество элементов булеана это сумма количеств всех возможных одно элементных подмножеств, всех возможных двух элементных подмножеств и так далее плюс один для пустого множества, то есть:

n

2X =C 0n+C1n+C2n+ …+C nn=∑C kn .

k =0

Очевидно, что C1n =n иCnn=1 . АC0n =1 .

Позже мы найдём более простую формулу для 2X .

Итак, мы рассмотрели различные комбинации без повторений. Ниже будут рассмотрены различные комбинации с повторениями элементов.

16 Симоненко Е.А. Дискретная математика. Лекции

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

Перестановкой элементов мультимножестваX,X =n=n1+n2 + …+nm , называется последовательность из элементов этого множества длиныn. Такие перестановки называют такжеперестановками с повторениями. Например, выпишем все перестановки

мультимножества	X ={1, 2,2} : (1, 2,2),(2,1, 2),(2, 2,1) .
Выясним, сколько	различных перестановок можно	получить из	мультимножества X с
X =n=n1+n2 + …+nm элементами? Как известно,		количество	перестановок n разных

элементов равно n!. Нетрудно понять, что так как некоторые элементы вX могут повторяться, то перестановка одних и тех же элементов между собой новой перестановки не даёт, значит количество перестановок с повторениями меньше количества перестановок без повторений во столько раз, сколько перестановок дают повторяющиеся элементы, а каждый повторяющийся элемент даётni ! ,i [1, m], перестановок. Таким образом получаем:

P (n1, n2,…, nm)=		n!			.
	n ! n	! … n	m	!
1 2

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

Пусть дано множество X,X =n . Тогдаразмещением с повторениями из n по k называется последовательность с повторениями изk элементов множестваX. Например, выпишем все размещения по два для множестваX ={1, 2} : (1,1),(1, 2),(2,1),(2,2) .

Фактически, размещение с повторениями из n поk на множествеX это ничто иное как декартово произведениеX ×X ×…×X =X k . Отсюда сразу следует, что количество всевозможных размещений с повторениями изn поk равно:

Akn=nk.

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

Пусть дано множество X, X =n . Тогда сочетанием с повторениями из n по kназывается мультимножество Yиз kэлементов множества Xтакое, что его элементы могут повторятся от 0до kраз, то есть допускается любое количество повторений. Например, выпишем все сочетания с повторениями по два для множества X =1, 2,3 :

{1, 1},{1, 2}, {1, 3},{2, 2}, {2, 3}, {3,3} .

Выясним, сколько можно получить различных сочетаний с повторениями из n поk? Чтобы выяснить это, сделаем следующее: сгруппируем в произвольном сочетании одинаковые элементы и вставим между группами разных элементовn−1 фиктивный разделительный элемент. Затем перенумеруем элементы полученного мультимножества и получим новое множество сk +n−1 различными элементами. Нетрудно понять, что выбор дляn−1 разделительного элемента номер позиции изk +n−1 различных номеров и даст нам искомое количество сочетаний с повторениями изn поk:

	=	(k +n−1)!	=C kn+−1n−1 =Ckk +n−1 .
Cnk
		k ! (n−1)!

Бином Ньютона и полиномиальная формула

Рассмотрим известные формулы:

Комбинаторная теория

17

(x +y )1=x+y

(x +y )2=x2+2 x y+y2 . (x +y )3=x3+3 x2 y+3 x y2+y3

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

(x+y)1=C 0 x+C1 y
1	1
(x+y)2=C 0 x2	+ C	1 x y+ C2 y2			.
2		2	2
(x+y)3=C 0 x3+C		1 x2y+ C2x y2+ C 3			y3
3		3	3	3

Более того, с помощью метода математической индукции можно доказать следующую формулу:

n

(x+ y)n=C0n xn y0+C1n xn−1 y1+…+Ckn xn−k yk +…+Cnn x0 yn=∑Cnk xn−k yk .

k =0

Эта формула носит название бином Ньютонаили биномиальное разложение натуральной степени бинома. Здесь словом биномназван двучлен x+ y . Отсюда название для Cnk биномиальный коэффициент.

Биномиальный коэффициент обладает двумя интересными свойствами:

Cnk=Cnn−k −правило симметрии ,

Cnk=Ckn−1+ Ckn−−11−правило Паскаля.

Эти два свойства (правила) позволяют построить так называемый треугольник Паскаля: 1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

…

Что также даёт нам рекурсивное правило для вычисления биномиальных коэффициентов.

Вспомним теперь о до конца нерешённой нами проблеме: чему равно 2X ? Как мы уже выяснили при рассмотрении сочетаний (без повторений):

n

2X =C 0n+C1n+C2n+ …+C nn=∑C kn .

k =0

Если мы сравним эту формулу с биномом Ньютона, то увидим, что если положить x=1 иy=1 , то получим:

n

(1+1)n=C 0n+C1n+ …+C kn+ …+C nn=∑Cnk ,

k=0

что даёт нам ответ на наш вопрос:

2X=2 X.

Обобщением бинома Ньютона является полиномиальная формула:

studfiles.net

Комбинаторная теория

X 1 , X 2 ,… , X n

Комбинаторная теория

Комбинаторика (комбинаторная теория) – один из древнейших разделов математики. В средневековой Европе комбинаторика развивается совместно с теорией вероятностей и выделяется в самостоятельный раздел в 1666 году Лейбницем, который придумал это название и написал книгу «Рассуждения о комбинаторном искусстве». Предметом исследований комбинаторики являются всевозможные комбинации элементовконечных множеств. Рассматриваются комбинации с учётом порядка перечисления элементов или без учёта, комбинации с повторениями и без повторений.

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

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

Пусть даны два множества X иY такие, чтоX ∩Y = . ТогдаX Y=X+Y . Другими словами: количество элементов объединения двух не пересекающихся множеств равно сумме количеств элементов этих двух множеств.

А что если X ∩Y ≠ , то есть множестваX иY пересекаются? Тогда, очевидно, что так как у этих двух множеств есть общие элементы, то количество элементов их объединения будет меньше чем сумма количеств элементов по отдельности. Нетрудно догадаться, что эту разницу в количестве дадут общие элементы этих двух множеств, так как простым суммирование количеств эти элементы будут посчитаны дважды, значит из суммы количеств нужно вычесть количество общих элементов:X Y=X+Y−X ∩Y .

Далее, пусть дано n множеств таких, чтоX i∩X j=,i≠j . ТогдаX 1 X 2…X n=X 1+X 2+ …+X n . Другими словами: количество элементов семейства не пересекающихся множеств равно сумме количеств элементов множеств его составляющих. Это правило носит названиеправило сложения.

В случае же, если множества X 1 , X 2 ,…, X n пересекаются, очевидно, столь простым правилом не обойтись, так как один и тот же элемент может принадлежать двум или более множествам. Подробности этого случая обсуждаются в методе включения и исключения.

Правило умножения

Пусть даны два множества X и Y. Тогда X ×Y=X Y . Другими словами: количество всех упорядоченных пар равно произведению количеств элементов исходных множеств.

Далее, пусть дано n множеств X 1 , X 2 ,…, X n . ТогдаX 1×X 2×…×X n =X 1 X 2 …X n . Другими словами: количество упорядоченных последовательностей равно произведению

количеству элементов исходных множеств.

В случае, если X 1=X 2=…=X n , тоX n =X n .

Метод включения и исключения

Пусть даны		n		множеств X 1 , X 2 ,…, X n возможно попарно пересекающихся. Тогда
X 1 X2… Xn=(X1+X2+…+Xn)
−( X 1∩X 2 +X 1∩X 3 +…+X n−1∩X n )
+( X 1∩X 2∩X 3 +…+X n−2∩X n−1∩X n )
+(−1)n−1 X	∩ X		2	∩…∩X
1				n

16	Симоненко Е.А. Дискретная математика. Лекции
n
или ∑(−1)k−1 S k (X 1, X 2,…, X n) , гдеS k (X 1, X 2, …, X n)		является суммой	X i1∩…∩X ik по
k =1			X 1 , X2 ,…, Xn .
всем возможным пересечениям ровно k различных множеств из множеств
(Доказательство смотри в [Кузьмин: комбинаторика].)
Перестановки
Перестановкой элементов множества	X,X =n ,	называется последовательность из

элементов этого множества длины n. Различные перестановки одного и того же множества отличаются друг от друга только порядком размещения его элементов. Например, выпишем все перестановки множестваX ={1,2, 3} : (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) .

Выясним, сколько различных перестановок можно получить из множества с n элементами? Для этого будем строить произвольную перестановку по одному элементу по очереди и считать количество различных вариантов выбора элемента множества. Итак, для задания значения для первого элемента произвольной перестановки у нас есть возможность выбора из n элементов. После выбора первого элемента перестановки у нас остаётсяn – 1 элемент и, значит, второй элемент перестановки мы можем выбратьn – 1 способами. Аналогично рассуждаем и для всех остальных элементов перестановки по очереди вплоть до последнего, выбора для которого уже не остаётся (в исходном множестве остаётся только один не выбранный элемент). Таким образом, по правилу умножения мы получаем следующую формулу:

Pn=n (n−1) …1 ,

где Pn обозначает количество всевозможных перестановок множества сn элементами.

Произведение n (n−1) …1 называют факториалом и обозначаютn! . Это число нам ещё встретится. (По определению считают, что0 !=1 .)

Иногда нас интересует только порядок следования элементов, но не то с какого элемента последовательность начинается. Например, для множества X ={1,2, 3} различными будут считаться только такие перестановки: (1,2,3),(1,3,2) . Назовёмциклическим сдвигом влево последовательности (x1, x2, … , xn −1 , xn) последовательность (x2, … , xn−1 , xn , x1) , а

циклическим сдвигом вправо – последовательность (xn , x1, x2,… , xn−1) . Тогдациклической перестановкой называется перестановка, получающаяся из некоторой другой циклическим сдвигом вправо или влево. Назовёмосновными перестановки, которые нельзя получить друг из друга посредством циклических сдвигов. Очевидно, что количество циклических перестановок некоторой последовательности равноn, включая её саму. Тогда количество всех основных перестановок равно (n−1)! .

Размещения

Рассмотрим теперь всевозможные перестановки элементов множества X,X =n , произвольной длиныk. Такие перестановки с выборомk элементов изn называютразмещениями. Например, выпишем все размещения по два для множестваX ={1,2, 3} :

(1,2),(1,3),(2,1),(2,3),(3,1),(3,2) .

Выясним, сколько возможно сделать размещений из n элементов поk. Для этого поступим также как и при выяснении количества перестановок элементов множества за той лишь разницей, что у нас будет толькоk элементов: первый элемент множества мы можем выбратьn разными способами, второй –n – 1 разными способами, и так далее, и, наконец последнийn−k+1 разными способами. Таким образом по правилу умножения получаем:

Комбинаторная теория		17
Ank=n (n−1) … (n−k+1)=	n !	.
(n−k)!

Очевидно, что Ann=n! даёт нам число перестановок.

Сочетания

Как уже известно, множество всех возможных комбинаций элементов некоторого множества X называется булеаном множестваX и обозначается2X . (Позже мы выясним, чему равно2X , то есть сколько всего возможно построить подмножеств из некоторого множестваX.) Но часто нас интересуют не все возможные комбинации, а только с определёнными свойствами. В частности, подмножества множестваX,X =n , с определённой мощностьюk называютсочетаниями из n по k. Например, выпишем все сочетания по два для множества

X ={1, 2,3} : {1, 2},{1, 3}, {2,3} .

Возникает вопрос, а сколько возможно сочетаний из n поk? Давайте на время забудем о том, что порядок перечисления элементов множества не важен, тогда количество сочетаний есть

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

должны уменьшить получившиеся число на количество всех возможных порядков размещения, что есть на количество перестановок из k элементов, то есть k ! . Таким образом, получаем следующую формулу:

	Cnk=n (n−1) …(n−k + 1)	=	n!	,
			k ! (n−k)!
	k !

где Cnk обозначает количество всех возможных сочетаний изn элементов поk.

Число Cnk также называютбиномиальным коэффициентом. Его свойства мы рассмотрим позже.

Вернёмся к булеану 2X и попытаемся выяснить, чему равно2X . Очевидно, что количество элементов булеана это сумма количеств всех возможных одно элементных подмножеств, всех возможных двух элементных подмножеств и так далее плюс один для пустого множества, то есть:

n

2X =C 0n+C1n+C2n+ …+C nn=∑C kn .

k =0

Очевидно, что C1n =n иCnn=1 . АC0n =1 .

Позже мы найдём более простую формулу для 2X .

Итак, мы рассмотрели различные комбинации без повторений. Ниже будут рассмотрены различные комбинации с повторениями элементов.

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

Перестановкой элементов мультимножестваX,X =n=n1+n2 + …+nm , называется последовательность из элементов этого множества длиныn. Такие перестановки называют такжеперестановками с повторениями. Например, выпишем все перестановки мультимножестваX ={1, 2,2} : (1, 2,2),(2,1, 2),(2, 2,1) .

Выясним, сколько различных перестановок можно	получить из мультимножества X с
X =n=n1+n2+ …+nm элементами? Как известно,	количество перестановок n разных

элементов равно n!. Нетрудно понять, что так как некоторые элементы вX могут повторяться,

18 Симоненко Е.А. Дискретная математика. Лекции

то перестановка одних и тех же элементов между собой новой перестановки не даёт, значит количество перестановок с повторениями меньше количества перестановок без повторений во столько раз, сколько перестановок дают повторяющиеся элементы, а каждый повторяющийся элемент даёт k! перестановок, еслиk – количество повторов. Таким образом получаем:

P (n1, n2, …, nm)=		n!			.
	n ! n	! … n	m	!
1 2

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

Пусть дано множество X,X =n . Тогдаразмещением с повторениями из n по k называется последовательность с повторениями изk элементов мультимножестваX. Например, выпишем все размещения по два для множестваX ={1, 2} : (1,1),(1, 2),(2,1),(2,2) .

Фактически, размещение с повторениями из n поk на множествеX это ничто иное как декартово произведениеX ×X ×…×X =X n . Отсюда сразу следует, что количество всевозможных размещений с повторениями из n по k равно:

Akn=nk.

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

Пусть дано множество X, X =n . Тогда сочетанием с повторениями из n по kназывается мультимножество Yиз kэлементов множества Xтакое, что его элементы могут повторятся от 0до kраз, то есть допускается любое количество повторений. Например, выпишем все сочетания с повторениями по два для множества X =1, 2,3 :

{1, 1},{1, 2}, {1, 3},{2, 2}, {2, 3}, {3,3} .

Выясним, сколько можно получить различных сочетаний с повторениями из n поk? Чтобы выяснить это, сделаем следующее: сгруппируем в произвольном сочетании одинаковые элементы и вставим между группами разных элементовn−1 фиктивный разделительный элемент. Затем перенумеруем элементы полученного мультимножества и получим новое множество сk +n−1 различными элементами. Нетрудно понять, что выбор дляn−1 разделительного элемента номер позиции изk +n−1 различных номеров и даст нам искомое количество сочетаний с повторениями изn поk:

	=	(k +n−1)!	=C kn+−1n−1 =Ckk +n−1 .
Cnk
		k ! (n−1)!

Бином Ньютона и полиномиальная формула

Рассмотрим известные формулы:

(x +y )1=x+y
(x+ y)2=x2+2 x y+ y2	.
(x+ y)3=x3+3 x2 y+3 x y2+ y3

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

(x+y)1=C0 x+C1 y
1	1
(x+y)2=C0 x2	+ C	1 x y+ C2 y2		.
2		2	2
(x+y)3=C0 x3+C		1 x2y+ C 2x y2+ C 3y3
3		3	3	3

studfiles.net

§ 4. Элементы комбинаторики. Соединения без повторений и с повторениями. Правила суммы и произведения.

Комбинаторика – теория соединений – изучает некоторые операции над конечными множествами, как упорядочение множества и разбиение множества, интересуется расположением элементов в множестве, выясняет, сколькими способами можно расположить элементы множества в том или ином порядке. Это приводит к понятиям перестановок, размещений и сочетаний. Основными задачами комбинаторики являются: 1) определение вида соединения; 2) подсчет числа соединений.

П.1 Соединения без повторений

Пусть дано множество М, состоящее из nэлементов.

Опр. 4.1.1Перестановки– всевозможные упорядоченные множества, составленные из всех элементов данного множества. Число всевозможных перестановок изnэлементов обозначают Р_nи находят по формуле

Р_n= n! (1),

где n!= 123n, 0!=1 по определению.

Пример 4.1.1.Сколько перестановок можно составить из трех букв а, в, с?

Решение:Р₃=123=6. Действительно: авс, вас, асв, сав, вса, сва.

Пример 4.1.2. Сколькими способами можно переставить буквы в слове «треугольник»?

Решение:Т.к. все буквы в данном слове разные, т.е. нет повторений, то можно воспользоваться формулой (1): Р₁₁=11!=39916800.

Опр. 4.1.2Размещениями из n по m называются всевозможные упорядоченные подмножества, содержащиеmэлементов из данныхn. Обозначаются и вычисляются по формуле:

(2).

Пример 4.1.3.Сколько можно составить четырехзначных чисел, содержащих различные цифры из 5 цифр.

Решение:Четырехзначное число – это упорядоченная последовательность цифр, т.е. имеем дело с размещениями без повторений: А₅⁴=5432=120.

Пример 4.1.4.В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами может быть составлено расписание на 1 день?

Решение:

Опр. 4.1.3Сочетаниями из n по m называются всевозможные подмножества данныхn элементов, состоящие изm элементов. Для подсчета их числа используются следующие обозначение и формула:

(3).

Пример 4.1.5.Сколькими способами можно из 7 различных открыток выбрать три?

Решение:Совокупность трех открыток является неупорядоченным подмножеством семи открыток, поэтому имеем дело с сочетаниями:

П.2 Соединения с повторениями

Опр: 4.2.1Перестановками с повторениями называются перестановки изnэлементов, в каждую из которых входитn₁элементова,n₂элементовb, …,n_kэлементовl, гдеn=n₁+n₂+…+n_k. Число перестановок с повторениями вычисляется по формуле:

Пример 4.2.1 Сколькими способами можно переставить буквы в слове “математика”.

Решение:В слове “математика” есть повторяющиеся буквы: “м” – 2 раза, “а” – 3 раза, “т” – 2 раза, “е” – 1 раз, “и” – 1 раз, “к” – 1 раз. Порядок расположения элементов имеет значение (это очевидно, так как если переставить местами 2 буквы, то получатся разные слова) и все элементы используются, следовательно, это перестановка с повторениями.

Таким образом, в слове “математика” можно переставить буквы 151200 способами.

Опр 4.2.2Сочетания изnэлементов, в каждое из которых входитmэлементов, причем один и тот же элемент может повторяться в каждом сочетании любое число раз, но не болееm, называются сочетаниями с повторениями. Число сочетаний с повторениями вычисляется по формуле:

Пример 4.2.2на почте продаются открытки 10 сортов. Сколько вариантов существует для покупки 12 открыток.

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

.

Таким образом, из 10 открыток можно выбрать набор из12 штук 293930 способами.

Опр 4.2.3 Размещениями с повторениями изnэлементов поkэлементов называются упорядоченные множества, каждое из которых содержитkнеобязательно различных элементов из данного множестваnэлементов. Число размещений с повторениями вычисляется по формуле:

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

Решение:Так как порядок расположения элементов важен и не все элементы используются в данном соединении, то это размещение. А так как всего 8 гнезд, а флажков 2 вида (голубой и красный), то они будут повторяться, т.е. это размещение с повторением.

Таким образом, существует 256 способов украсить здание с 8 гнездами флажками двух цветов.

studfiles.net

Комбинаторика в MS EXCEL. Примеры и методы

Подсчитаем в MS EXCEL количество Размещений с повторениями из n по k (выборка с возвращением). Также с помощью формул выведем на лист соответствующие варианты Размещений (английский перевод термина: sequence with repetition или permutations with repetition).

Размещение с повторениями (выборка с возвращением) — это Размещение n объектов по k в предположении, что каждый объект может участвовать в размещении несколько раз.

Примечание: О Размещениях без повторений (т.е. без возвращения элементов) можно прочитать в статье Размещения без повторений: Комбинаторика в MS EXCEL

Например, из множества содержащего 3 (n) различных элемента (a, b, c) можно сформировать 9 (=3^2) упорядоченных наборов по 2 (k) элемента (т.е. 9 размещений с повторениями из 3 по 2): аа, ab, ac, ba, bb, bc, ca, cb, сс. В отличие от Размещений без повторений наборы аа, bb и сс  допустимы. В отличие от Сочетаний наборы ac и ca считаются различными (важен порядок).

В отличие от Размещений без повторений, k может быть меньше или больше n. Например, из множества содержащего 2 (n) различных элемента (a, b) можно сформировать 8 (=2^3) упорядоченных наборов по 3 (k) элемента (т.е. 8 размещений с повторениями из 2 по 3): ааa, аab, aba, abb, baa, bab, bba, bbb. В отличие от Размещений без повторений наборы ааa, abb и пр. допустимы. В отличие от Сочетаний наборы abb и bba считаются различными (важен порядок).

В файле примера MS EXCEL приведен подсчет количества Размещений с повторениями и создана универсальная формула для вывода всех размещений для заданных n и k.

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

Задача

Богатый автолюбитель решил сделать подарки своим 3 любимым родственницам: жене, маме и сестре. К сожалению, женщины не смогли однозначно определиться с марками машин, но указали 4 марки, которые им всем троим нравятся в одинаковой степени: Volkswagen Polo, Hyundai Solaris, KIA Rio и Renault Duster. Автолюбитель решает довериться случаю и делает 4 записки, с указанием марок машин. Все записки кладет в мешок. После каждого выбора, автолюбитель кладет выбранную записку обратно в мешок. Определить число различных вариантов распределения марок между родственницами.

Нам нужно определить число размещений с повторениями 4-х марок машин 3-м родственницам. Т.е. n=4, а k=3. Оказывается, что таких вариантов =4^3 равно 64.

Воспользуемся файлом примера, чтобы убедиться, что мы решили задачу правильно.

По аналогии с решением задачи в статье Размещений без повторений сопоставим произвольным образом маркам машин числовые значения и сделаем сокращения названий марок: Hyundai Solaris (HS=1), KIA Rio (KR=2), …

Выставив в ячейках В5 и В6 значения 4 и 3 соответственно, определим все варианты размещений.

Примечание: О перестановках можно прочитать в статье Перестановки без повторений: Комбинаторика в MS EXCEL, а о сочетаниях в статье Сочетания без повторений: Комбинаторика в MS EXCEL.
Примечание: В данной статье рассмотрена выборка элементов из одного массива, в котором содержится n элементов. В статье Комбинации элементов из нескольких множеств составлены все возможные комбинации элементов таким образом, чтобы в комбинации присутствовал один и только один элемент из каждого множества. Если все множества идентичны (состоят из одинаковых элементов), то задача сводится к рассмотренному в этой статье Размещению с повторениями.

excel2.ru

Выборки элементов с повторениями

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

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

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

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

Задача. На световой панели в ряд расположены 4 лампочки, каждая из которых может гореть красным, жёлтым или зелёным цветом. Сколько различных сигналов можно передать с помощью панели (все лампочки должны гореть, порядок цветов имеет значение)?

Решение. Сигналы светового табло можно рассматривать как выборки из 3 по 4. Определим комбинаторную схему: поскольку «порядок цветов имеет значение» — это размещения. Заметим, что каждая из лампочек в один и тот же момент времени может гореть одним цветом. Значит, выборка — размещения с повторениями.

Комбинаторная схема «размещения с повторениями» используется в задаче №10 ЕГЭ по информатике (смотрите комбинаторные задачи в ЕГЭ).

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

Пусть в исходную совокупность входит n₁ элементов первого типа, n₂ — второго типа, …, n_k – k-го типа, при этом n₁ + n₂ + …+ n_k = n. Всевозможные упорядоченные выборки, составленные из всех данных n элементов, называются перестановками с повторениями.

Формула для расчета количества cочетаний с повторениями

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

Решение. Заметим, что все лампочки исходной совокупности должны располагаться на табло (4 + 2 = 6). Так как «все лампочки должны гореть», то сигналы будут отличаться только порядком цветов. Значит, комбинаторная схема – перестановки с повторениями.

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

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

Формула для расчета количества cочетаний с повторениями

Задача. Для составления некоторого кода используются цифры 1, 2, 3. Кодовые слова должны удовлетворять следующим свойствам:

1. Длина кодовых слов равна 3;
2. Кодовые слова могут содержать одинаковые цифры;
3. Кодовые слова, отличающиеся только порядком цифр, считаются одинаковыми.

Сколько вариантов кодовых слов можно составить?

Решение. Поскольку длина кодовых слов равна 3, то выборки из 3 по 3. Определим комбинаторную схему: из пункта 3 следует, что выборка неупорядоченная при этом «Кодовые слова могут содержать одинаковые цифры», значит, выборки – сочетания с повторениями.

Действительно, таких кодовых слов ровно 10:
111
112 113
122 123 133
222 223 233 333

informatics-lesson.ru