Число элементов Число вертикальных

Длина такой перестановки элементов с учётом вертикальных линий составляет

r+(n-1)

 

 

Число элементов Число вертикальных

r-сочетаний линий

 

Любое такое r-сочетание можно задать выбором из n-r+1 места, n-1 места для положения вертикальных линий. Это можно сделать способами.

Промежуточные места между линиями заполняются соответствующими видами элементов.

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

Решение. Имеем 4 вида пирожных. Число способов, которыми можно выбрать из них 7 пирожных равно:

n=4, r=7.

 

Разбиение множества на подмножества.

Пусть S — множество мощности n.

r – сочетание из множества является его подмножеством мощности r.

В связи с этим рассмотрим задачу о числе разбиений множества S на подмножества такого вида:

Æ при i¹j, ij=1, …, k,

Найдем число всевозможных разбиений такого вида. Рассуждений: для выбора подмножества T_{1 .} Из S имеется возможностей; после этого подмножества T_{2 .}. Можно выбирать только из n-r₁ элементов (т.к. Т₁IТ₂=Æ), и значит, имеется способов для выбора Т₂.

Подмножество Т_к можно выбирать только после того, как выбраны множества Т_i, i=1,2,…, r - 1, следовательно из элементов. Значит, Т_к можно выбрать способами.

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

- число разбиений множества на k непересекающихся подмножеств.

n – мощность множества

r_i – мощность подмножеств

 

Комбинаторика разбиений.

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

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

 

При этом могут встретиться различные случаи:

· количество элементов в каждой группе задано (К) – не задано ().

· данные элементы различны между собой (Р_э) – одинаковы () – частично различны, то есть имеются предметы разных видов, в пределах каждого вида предмета неразличима (Р_э).

· порядок расположения элементов в группе важен (П_э) – не важен ()

· группы различны (Р_г) – не различны ()

· порядок самих групп важен (П_г) – не важен ().

 

В связи с этим возникает целый ряд комбинаторных задач на разбиение. Подсчитаем количество возможных вариантов таких задач.

Итого:$ 2´5´3=30 видов задач на разбиение Количество элементов в группе	Размещение элементов и их порядок	Размещение групп и их порядок
К	Рэ Пэ, Пэ	Рг Пг
	Рэ ,	Рг

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

 

Рассмотрим только некоторые вилы таких задач.

1 Постановка задачи К Р_э Р_г П_г

Даны n различных предметов и к различных ящиков, Надо положить в первый ящик n₁ предметов, во второй – n₂, в который n_k предметов, где n₁ + n₂ +…+ n_k=n. Сколькими способами можно сделать такое распределение?

К этому типу задач относиться задача о разбиение множества на подмножества.

Пусть S – множество мощности n и множеств Т₁ Т₂ …, Т_к образуют его разбиение.

то есть Æ при i¹j, ij=1, …, k,

{х₁, х₂, ……….., х_n}

{…..}U{…..}U…U{…..}

n₁ n₂ n_k

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

Решив задачу о разбиении множества на подмножества, получим форму для исходной задачи.

Рассуждение. Подмножество мощности n_i является сочетанием длин n_i. Значит, для выбора подмножества Т₁. После сделанного выбора подмножеств Т₂ мощности n₂ можно выбирать только из оставшихся n-n₁ элементов, значит имеется способов для выбора Т₂ ….

Подмножество Т_к мощности n_k можно выбирать только после того, как выбраны подмножества Т_i, i=1,2,.., k-1, следовательно из элементов. Значит, Т_к можно выбрать способами, Применяя теперь обобщенное правило произведения получим, что искомый число разбиений множества S мощности n на к непересекающихся подмножеств равно

К этому же типу задач относиться задача о перестановках с повторениями.

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

Другой способ:

Игроку не важен порядок, в котором он получит кости, а а важно лишь окончательный итог.

При игре в домино игроки сидят в определенном порядке, и важно не только то, как разделились кости, но и то, кому какие кости достались.

2. К Р_э Р_г

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

3. Постановка: если имеется n₁ предметов одного вида,n₂ предметов другого вида, …, n_k предметов качественного вида. Сколькими способами можно разделить их на 2 группы?

`К Р_г

Это можно сделать (n₁+1)(n₂+1)…(n_k+1) способами.

Р_г

$ n₁ aaaaa bbb..b … xxx…x

n1

n2

nk

 

1 + 1 + 1 + 1+……+1=1+n₁ способов взять предмет 1-го вида и т.д.

ни одного один два три …. n₁

n

Сеть обслуживают 2 сервера. В сети работают 15 студентов, 10 преподавателей и 9 аспирантов. Сколькими способами мы можем разделить обслуживание между серверами?

Пример. Двое собрали 10 предметов первой необходимости, 15 предметов второй необходимости и 14 предметов третей. Сколькими способами они могут все это разделить? (15+1)(10+1)

К данному типу задач относиться такая задача.

Найти, сколько делителей есть натурального числа N. Для этого разложим N на простые множители: , где р₁, р₂ ,…, р_n- различные простые числа.

Например

При разложении числа N на 2 сомножителя N=N₁+N₂ простые сомножители распределяться между N₁ и N₂.

Если в N₁ сомножители p_j войдет m_j раз., j=1,…,k, то различные имеют вид

	N1		N2

 

То есть разложение N на 2 сомножителя сводиться к разделу n₁ первого вида, n₂ элементов второго вида, …, n_k элементов k-го вида на 2 части.

Значит, число делителей у натурального числа равно (n₁+1)(n₂+1)…(n_k+1)

4. Постановка. Сколькими способами можно разделить n одинаковых предметов на k групп?

Берем n предметов и расставляем их в ряд (не важно, в каком порядке). Чтобы разбить их на k групп, нужно вставить между ними k-1 разделитель.

 

OOO…O|O…O|…|…|OOO…

Число способов разбиения n предметов на k групп равно числу способов поместить k-1 перегородку на n+k-1 место. Это

4 способа

 

Пример. Трое лиц делят 40 яблок. Сколькими способами это можно сделать. Яблоки одинаковы.

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

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

Пример. Трое грибников собрали 45 белых, 15 подосиновиков и 100 лисичек.

Сколькими способами они могут разделить их между собой?

 

6. Постановка. Сколько существует способов разделить n различных предметов на k различных групп?

Каждый предмет можно поместить в группу k способами. Поэтому число способов разбиения – kⁿ.

n

 

К

 

 

1 2 k-1 k

k

Пример. 8 различных пирожных можно разделить между 5 людьми 5⁸ способами.

 

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

 

8. Постановка. Имеется 4 различных предметов, k различных ящиков. Сколько $ способов эти предметы по k ящикам с учетом порядка их расположения в ящике.

 

Если бы предметы были неразличимы и не учитывался их порядок, то число способов =

Т.к. все предметы различны, то имеем n! различных перестановок. Для каждой перестановки $ способов разместить их по ящикам.

Þ

 

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

 

9.

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

Пусть множество n разбивается на k непустых подмножеств мощности n₁,n_2,…,n_k соответственно, причем .

Или, что тоже самое, целое число n>0 разложиться в сумму целых ненулевых слагаемых n=n₁+n₂+_m+n_k.

Обозначим через P_k(n) число таких разбиений.

Можно сразу сказать, что

P₁(n)=1 — есть 1 способ представить число n одним слагаемым.

P_k(k)=1 — есть 1 способ представить число k k слагаемыми (то есть всеми единицами).

P_k(n)=0 при n<k – не $ способа представить число n, меньше k, k слагаемыми.

Предположим, что

, т.е. если число n представлено в виде суммы слагаемых a₁,…,a_k, то число n-k представлено в виде суммы слагаемых а₁-1, …, а_к-1 и наоборот.

Между {n₁, …, n_k} и {n₁-1, …, n_k-1} $ взаимно-однозначное соответствие.

Значит, количество разбиений числа n на слагаемые n₁,…,n_k равно количеству разбиений числа n-k на слагаемые n₁-1,…,n_k-1

Р_k(n)=P_k(n-k)

Подставляем это количество

Множество {n₁-1,…,n_k-1} содержит столько нулевых слагаемых, сколько единиц среди чисел n₁,…,n_k. Единиц среди этих чисел есть может быть 0,1,2,…,k.

В число разбиений P_k(n-k) входят разбиения, содержащие 0,1,2,…,k единиц.

По правилу суммы

0 единиц содержащее одну единицу

количество способов разбить на слагаемые не содержащие единицу

Р₁(n)=1, Р_k(k)=1, Р_k(n)=0, n<k

Р₂(3)=Р₁(1)+Р₂(1)

1 0

Р₂(6)=Р₁(4)+Р₂(4)=1+2=3

=1 =Р₁(2)+Р₂(2)

1 + 1

Эта рекуррентная формула позволяет получать последовательно значения для Р_k(n).

 

 

 

Циклы. Спецификации.

 

1. Разложение перестановки на циклы.

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

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

 

Любая перестановка может быть разложена на циклы. Если циклические перестановки внутри циклов считать тождественными, то есть считать, что (145)=(451)=(514), то разложение будет единственным.

 

2. Спецификация перестановки.

Пусть некоторая перестановка длин n содержит k₁ циклов состоящих из 1 элемента, k₂ циклов, состоящих из двух элементов, …, k_n циклов, состоящих из n элементов.

Тогда символически она может быть записана в виде

, где

запись — это спецификация перестановки.

Перестановка из примера (см. выше) имеет спецификацию 1¹2¹3¹4⁰5⁰6⁰7⁰8⁰9⁰.

Найдем, чему равно число перестановок такой спецификации, то есть найдем, сколько существует перестановок на множестве мощности n, которые имеют заданное размещение на циклы.

Что имеется ввиду?

Например, пусть n=6. На множестве такой мощности E6! перестановок.

Зададим спецификацию перестановки: 1³2⁰3¹4⁰5⁰6⁰

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

Перестановка - удовлетворяет спецификации

- удовлетворяет спецификации

(12)(3)(456) – не удовлетворяет спецификации

 

1, 2, 3, ………., n

	n!

 

(..)(..)..(..)(..)..(..)…(……)

k₁ k₂ k_n

Всего $ n! перестановок всех элементов множества.

Но при разложении перестановки спецификации на циклы можно k₁! способами переставлять циклы длины 1, k₂! способами переставлять циклы длины 2, …, k_n! способами переставлять циклы длины n, и результат от этого не изменится.

Коме того, внутри цикла длины 2 существует i способов циклически перестановить элементы, и на результат от этого не изменится. А так как циклов длины i – k_i штук, то общее число перестановок заданной спецификации равно:

 

3. Существует такие понятия спецификации множества и спецификации групп (ячеек).

Множество мощности n имеет спецификацию, если оно имеет k₁ элементов первого вида, k₂ элементов второго вида,…,k_m элементов m-го вида, причем k₁+k₂…+k_m=n,

Пример. Имеем 10 шаров (n=10)? 4 цвета, m=4. Множество шаров имеет спецификацию k₁+k₂+k₃+k₄=10

Множество ячеек мощности r имеет спецификацию (n₁,n₂,…,n_r), если в i-й ячейке помещается n_i элементов (i=1,…,r).

 

Производящие функции.

Пример. Рассмотрим многочлены

(a+x)²=aa+ax+xa+xx (1)

(a+x)³=aaa+aax+axa+xaa+xxa+xax+axx+xxx. (2)

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

При разложении на слагаемые многочлена (а+х)ⁿ получим всевозможные размещения с повторениями из 2-х элементов по n.

Приведём подобные слагаемые. Подобными будут слагаемые, содержащие одинаковое количество букв х, а следовательно и одинаковое количество букв а.

Слагаемые, содержащие k букв х и n-k букв а- это перестановки с повторениями. Их число равно:

P(k,n-1)= .

Значит,

При а=1

Т.е. функция f(x)=(1+x)ⁿ взаимно однозначно связана с последовательностью , и эту функцию называют производящей функцией чисел , k=0,…, n.

 

Определение: Пусть рассматривается последовательность целых чисел

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

 

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

На переменную t ограничения почти никогда не накладываются. Производящие функции позволяют перейти от рассмотрения отделяющих величин (например, сочетаний из n по k для частного k) к рассмотрению их последовательностей.

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

Некоторые производящие функции позволяют только подсчитывать количество объектов.

Очень часто производящая функция строится так, что в ее представлении присутствуют формальные обозначения элементов, образующих комбинаторные объекты, -x₁, x₂, …,x_n.

Чтобы получить интересующие нас объекты, состоящие из k элементов, нужно выписать коэффициент ряда при t_k, т.е. a_k. По слагаемым, присутствующим в a_k, определяются нужные объекты. Сколько имеется слагаемых, содержащих x_i-ые в коэффициенте a_k, столько и объектов.

Чтобы подсчитать количество объектов длины k, нужно вычислить коэффициент a_k, положив x₁=x₂=x₃=…=x_n=1.

 

Метод производящих функций - один из самых теоретически развитых методов комбинаторного анализа.

 

Основы метода производящих функций рассмотрим на примерах:

 

1. Производящая функция для сочетания из n элементов по k, все элементы различны.

 

Имеем n различных элементов x₁,x₂,…,x_n. Из них выбираем сочетания. Для каждого элемента имеем 2 возможности:

элемент x_i либо не появляется в сочетании, либо появляется только 1 раз.

Одному появлению элемента x_i в сочетании соответствует одночлен ; отсутствию x_i в сочетании соответствует .

По правилу суммы, появлению элемента x_i либо 0, либо 1 раз соответствует полином: + =1+x_it.

Применив сказанное ко всем элементам x₁,x₂,…,x_n, по правилу произведения получаем производящую функцию

F(t)=(1+x₁t)(1+x₂t)…(1+x_nt)=

Это произведение можно представить в виде суммы:

= .

По функции, полученной в таком виде, определяют сами сочетания.

Положив x₁,x₂,…,x_n=1, получим такую производящую функцию:

с помощью такой функции

определяем числа сочетаний.

Задача. Дано множество элементов {x₁,x₂,x₃}. Получить все сочетания из трех элементов по k, где k= 0, 1, 2, 3 и подсчитать их число для каждого k.

F(t)=(1+x₁t)(1+x₂t)(1+x₃t)=

[выписываем коэффициент при степенях t] = =

 

По полученной записи определяем:

K	Коэффициент ak	сочетания из 3 по k (слагаемые ak, содержащие xi)	Число сочетаний из 3 по k (ak, вычисленные при x1=x2=x3=1)
	x1+x2+x3 x1x2+x1x3+x2x3 x1x2x3	0 (объект отсутствует)   x1, x2, x3 x1x2, x1x3, x2x3 x1x2x3	1-существует одна возможность не выбирать ни одного элемента из сочетания

 

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

по правилу суммы это число равно:

Воспользуемся функцией

При t = 1 получим: (1+1)¹⁴=

 

В нашем случае в группу не может входить 0 человек, поэтому:

-искомое число способов.

=2¹⁴ =1

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

Чтобы получить интересующие нас объекты, состоящие из k элементов, нужно выписать коэффициент ряда при t^k. По слагаемым, присутствующим в a_k, определяются нужные объекты.

Очень часто производящая функция строится так, что в ее представлении присутствуют формами обозначения элементов, образующих комбинаторы объекты x₁,x₂,…,x_n.

Сколько слагаемых в коэффициенте, столько и объектов.

Чтобы подсчитать количество объектов длин k, нужно вычислить коэффициент a_k, положив x₁=x₂=x₃=…=x_n=1 соответствующий полином:

mi

Действительно,

 

хi отсутствует в сочетании

хi присутствует 1 раз

присутствует 2 раза

присутствует mi раз

 

С учетом сказанного, для всех n видов элементов производящая функции имеет вид:

Положив x₁=x₂=x₃=…=x_n=1, получим производящую функцию для числа сочетаний из n по k с ограниченным числом повторений элементов

n=3 m1=2, m2=2, m3=3

Задача. Дано х₁, х₁, х₂, х₂, х₃

 

2 элемента вида х1

2 элемента вида х2

1 элемент вида х3

Требуется получить сочетание из данных элементов по 3 и рассчитать их количество.

F(t)=(1+x₁t+x₁²t²)(1+x₂t+x₂²t²)(1+x₃t)=[выпишем коэффициент при t³, т.к. к=3]+1*t⁰+(…)t²+(x₁x₂x₃+ x₂²x₁⁴+x₁²x₃+x₁²x₃+x₂²x₃)t³+(…)t⁴+(…)t⁵=

x1 - 1раз x2 - 1раз x3 - 1раз

x1 - 2раз x2 - 1раз x3 - 0раз

 

Коэффициент при t³ a³=x₁x₂x₃+x₁x₁x₂+x₁x₁x₃+x₂x₂x₁+x₂x₂x₃..

Слагаемое - это все возможные сочетания из имеющихся элементов по 3.

Число таких сочетаний вычисляем, положив a₃=1+1+1+1+1=5.

3. Производящая функция для числа сочетаний из n элементов по k с неограниченным числом повторений элементов.

Имеем элементы n видов – вида x₁, вида x₂,…, вида x_n.

Из этих элементов набираем сочетания, элемент х₂ может появляться в сочетании любое количество раз.

По аналогии с предыдущей задачей построим функцию:

F*(t)=(1+t+t²+…)(1+t+t²+…)…(1+t+t²+…)=(1+t+t²+…)ⁿ=()ⁿ=(1+(-t))^-n=

этот ряд сходится к функции

= = = == = =

этот результат был получен ранее

 

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

4. Производящая функция для числа перестановок длины k из n различных элементов.

Из элементов x₁,x₂,…,x_n строим перестановки длины k. Заметим, что каждому сочетанию из k различных элементов соответствует k! перестановок из этих элементов.

У нас есть производящая функция для числа сочетаний из n по k различных элементов: .

Значит, функция является производящей для перестановок длины k из n различных элементов.

Задача. Найти число перестановок длины 2 и длины 3 из элементов x₁,x₂,x₃,x₄.

Запишем производящую функцию и найдем коэффициент при t² и t³:

действительно имеет 6 х1х2 х1х3 х1х4 х2х3 х2х4 х3х4 состояний и 12 перестановок х2х1 х3х1 х4х1 х1х2 х4х2 х4х3

5. Производящая функция для числа перестановок длины k из n видов элементов. Элементы могут повторяться, число повторений ограничено.

Воспользуемся соответствующей производящей функцией для сочетаний с повторениями элементов:

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

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

Подсчитаем во сколько раз.

x_i элемент может встретиться в сочетании либо m_i раз, тогда мы можем переставить его m_i! способами, и перестановка не измениться,

либо m_i-1 раз - перестановка его (m_i-1)! способами не изменит объект и так далее.