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




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

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,

Найдем число всевозможных разбиений такого вида. Рассуждений: для выбора подмножества T1 . Из S имеется возможностей; после этого подмножества T2 .. Можно выбирать только из n-r1 элементов (т.к. Т12=Æ), и значит, имеется способов для выбора Т2.

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

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

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

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

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

 

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

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

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

 

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

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

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

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

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

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

 

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

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

Размещение элементов и их порядок Размещение групп и их порядок
К Рэ Пэ, Пэ Рг Пг
Рэ , Рг
 

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

 

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

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

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

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

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

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

1, х2, ……….., хn}

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

n1 n2 nk

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

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

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

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

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

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

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

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

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

2. К Рэ Рг

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

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

Рг

Это можно сделать (n1+1)(n2+1)…(nk+1) способами.

Рг

$ n1 aaaaa bbb..b … xxx…x

n1
n2
nk

 

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

ни одного один два три …. n1

n

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

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

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

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

Например

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

Если в N1 сомножители pj войдет mj раз., j=1,…,k, то различные имеют вид

       
 
N1
 
N2

 


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

Значит, число делителей у натурального числа равно (n1+1)(n2+1)…(nk+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 способами. Поэтому число способов разбиения – kn.

n

 

К

 

 

1 2 k-1 k

k

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

 

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

 

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

 

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

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

Þ

 

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

 

9.

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

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

Или, что тоже самое, целое число n>0 разложиться в сумму целых ненулевых слагаемых n=n1+n2+m+nk.

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

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

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

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

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

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

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

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

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

Рk(n)=Pk(n-k)

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

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

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

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

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

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

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

Р2(3)=Р1(1)+Р2(1)

1 0

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

=1 =Р1(2)+Р2(2)

1 + 1

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

 

 

 

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

 

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

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

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

 

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

 

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

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

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

, где

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

Перестановка из примера (см. выше) имеет спецификацию 112131405060708090.

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

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

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

Зададим спецификацию перестановки: 132031405060

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

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

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

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

 

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

 
 
n!

 


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

k1 k2 kn

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

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

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

 

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

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

Пример. Имеем 10 шаров (n=10)? 4 цвета, m=4. Множество шаров имеет спецификацию k1+k2+k3+k4=10

Множество ячеек мощности r имеет спецификацию (n1,n2,…,nr), если в i-й ячейке помещается ni элементов (i=1,…,r).

 

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

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

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

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

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

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

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

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

P(k,n-1)= .

Значит,

При а=1

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

 

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

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

 

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

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

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

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

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

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

Чтобы подсчитать количество объектов длины k, нужно вычислить коэффициент ak, положив x1=x2=x3=…=xn=1.

 

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

 

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

 

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

 

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

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

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

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

Применив сказанное ко всем элементам x1,x2,…,xn, по правилу произведения получаем производящую функцию

F(t)=(1+x1t)(1+x2t)…(1+xnt)=

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

= .

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

Положив x1,x2,…,xn=1, получим такую производящую функцию:

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

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

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

F(t)=(1+x1t)(1+x2t)(1+x3t)=

[выписываем коэффициент при степенях 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)14=

 

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

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

=214 =1

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

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

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

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

Чтобы подсчитать количество объектов длин k, нужно вычислить коэффициент ak, положив x1=x2=x3=…=xn=1 соответствующий полином:

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

 

хi отсутствует в сочетании хi присутствует 1 раз присутствует 2 раза   присутствует mi раз

 

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

Положив x1=x2=x3=…=xn=1, получим производящую функцию для числа сочетаний из n по k с ограниченным числом повторений элементов

n=3 m1=2, m2=2, m3=3
Задача. Дано х1, х1, х2, х2, х3

 

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

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

F(t)=(1+x1t+x12t2)(1+x2t+x22t2)(1+x3t)=[выпишем коэффициент при t3, т.к. к=3]+1*t0+(…)t2+(x1x2x3+ x22x14+x12x3+x12x3+x22x3)t3+(…)t4+(…)t5=

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

 

Коэффициент при t3 a3=x1x2x3+x1x1x2+x1x1x3+x2x2x1+x2x2x3..

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

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

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

Имеем элементы n видов – вида x1, вида x2,…, вида xn.

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

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

F*(t)=(1+t+t2+…)(1+t+t2+…)…(1+t+t2+…)=(1+t+t2+…)n=()n=(1+(-t))-n=

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

= = = == = =

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

 

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

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

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

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

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

Задача. Найти число перестановок длины 2 и длины 3 из элементов x1,x2,x3,x4.

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

действительно имеет 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! способами, каждый раз получая при этом новую перестановку.

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

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

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

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



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: