Журавлев Ю.И., Флеров Ю.А. Дискретный анализ - файл n1.doc

приобрести
Журавлев Ю.И., Флеров Ю.А. Дискретный анализ
скачать (2348 kb.)
Доступные файлы (1):
n1.doc2348kb.08.07.2012 19:20скачать

n1.doc

  1   2   3   4   5   6   7   8   9   ...   12






Журавлев Ю.И., Флеров Ю.А.

ДИСКРЕТНЫЙ АНАЛИЗ

I

1.Элементы комбинаторики.

1.1.Введение


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

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

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

Основная проблема комбинаторики - подсчет числа элементов в конечном множестве. В этой широкой проблеме можно условно выделить следующие основные направления исследований:

1.2.Два принципа комбинаторики


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

Правило произведения. Если объект A может быть выбран m различными способами и после каждого из таких выборов объект B в свою очередь может быть выбран n различными способами, то выбор двух объектов “A и B” в указанном порядке может быть осуществлен mn способами.

Правило суммы. Если объект A может быть выбран m различными способами, а объект B может быть выбран другими n различными способами при условии, что одновременный выбор A и B невозможен, то выбор “A или B” может быть осуществлен m + n способами.

1.3.Функции и размещения


Классической задачей комбинаторики является задача определения числа способов размещения некоторых объектов в каком-то количестве ящиков так, чтобы были выполнены заданные ограничения. Эту задачу можно сформулировать несколько более формально следующим образом.

Термины “функция”, “отображение”, “преобразование” и “соответствие” будут в дальнейшем использоваться как синонимы. При этом запись
f: XY означает, что f есть функция с областью определения X, область значений которой содержится во множестве Y, то есть для каждого xX функция f определяет единственный элемент y = f(x)  Y.

Пусть даны множества X, Y, причем множество X содержит n элементов (|X| = n), а множество Y содержит m элементов (|Y| = m). В этих терминах задача может быть сформулирована следующим образом: сколько существует функций (отображений) , удовлетворяющих заданным ограничениям. Элементы множества X соответствуют объектам, элементы множества Y- ящикам, а каждая функция f : X Y определяет некоторое размещение, указывая для каждого объекта xX ящик y = f(x)  Y, в котором данный объект находится.

Другую традиционную интерпретацию можно получить, трактуя Y как множество цветов, а f(x) как “цвет объекта x”. Наша задача эквивалентна, таким образом, вопросу, сколькими способами можно покрасить объекты так, чтобы были соблюдены некоторые ограничения.

Наконец, каждому отображению f : XY, X = n, Y=m, можно взаимно однозначно сопоставить слово< f(x1), ... , f (xn)> = 1, y2, ... , yn> =
= y1 y2 ...yn в алфавите из m символов. Получаем третью эквивалентную формулировку задачи: подсчет числа слов в алфавите, удовлетворяющих заданным ограничениям.

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

Утверждение 1.1. Если |X| = n, |Y| = m, то количество всех функций равно mn.

Эквивалентное утверждение 1 .1. Число слов длины n в алфавите из m символов равно mn.

Доказательство. Без потери общности можно всегда считать, что X = {1,..., n}, Y = {1,..., m}. Каждую функцию можно тогда отождествить с последовательностью < f(1),..., f (n)> = < y1 ,...,yn> . Каждый член yi последовательности можно выбрать m способами, что дает mn возможностей выбора последовательности 1 ,...,yn>.

Определения.

Отображение : X  Y сюръективно, если для каждого элемента yY существует хотя бы один элемент xX , такой что (x)=y (в каждом ящике при размещении находится хотя бы один объект, все буквы алфавита используются в слове, все цвета используются при окраске).

Отображение : X инъективно если .

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

Если x - действительное число, положим по определению

[x]n = x (x-1)(x-2)...(x-n+1).

Обозначение [x]n читается как “n факториал от x вниз” или “нижняя n-ая степень x”.

Утверждение 1.2. Число инъективных отображений (инъекций) множества X из n элементов, | X| = n, во множество Y из m элементов, |Y|= m, есть [m]n .

Эквивалентное утверждение 1 .2. Число слов длины n без повторений букв в алфавите из m букв есть [m]n .

Доказательство. Будем определять на этот раз число инъективных, (то есть имеющих все различные члены) последовательностей 1 ,...,yn>. Элемент y1 может быть выбран m способами, элемент y2 можно выбрать m-1 способом из оставшихся элементов. В общем случае, если уже выбраны элементы y1 ,...,yi-1, то в качестве yi может быть выбран любой из m-i +1 элементов множества Y\{y1,...,yi-1}. (Принимаем, что mn, если n>m, то и [m]n и искомое число функций равно 0). Это дает m(m-1)...(m - n+1) возможность выбора инъективных последовательностей 1 ,...,yn>.

Отметим, что



Определение.

Каждое взаимно однозначное отображение f :XX называется перестановкой множества x.

В соответствии с утверждением 1 .2 число перестановок n- элементного множества равно n!.

1.3.1. Числа Стирлинга первого рода


Выражение [x]n является полиномом степени n от переменной x, следовательно его можно представить в виде следующего разложения по степеням x:

[x]n = s(n,0) + s(n,1)x +...+ s(n,n)xn .

По определению, коэффициенты s(n,k) такого разложения называются числами Стирлинга первого рода.

Утверждение 1.3. Числа Стирлинга первого рода удовлетворяют следующим рекуррентным соотношениям:



s(n, 0)= 0;

s(n, n)= 1.

Доказательство. По определению

[x]n+1 = [x]n (x-n).

Представляя полиномы в левой и правой частях равенства в виде разложения по степеням x, получим

s(n+1,n+1)xn+1 +  + s(n+1, k)xk + +s(n+1,0)=

(s(n,n)+  +s(n, k-1)xk-1 + s(n,k)xk +  +s(n,0))(x-n).

Вычисляя и приравнивая коэффициенты при xk слева и справа, получаем первую формулу утверждения. Другие две формулы очевидны.

Утверждение 1 .3 дает эффективный способ рекуррентного вычисления чисел Стирлинга первого рода.

Приведем часть значений таблицы s(n,k) для начальных значений n и k :

s(n,k)

k=0

k=1

k=2

k=3

k=4

k=5

n=1

0

1

0

0

0

0

n=2

0

-1

1

0

0

0

n=3

0

2

-3

1

0

0

n=4

0

-6

11

-6

1

0

n=5

0

24

-50

75

-10

1


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

1.3.2. Циклическая структура перестановок


Перестановки множеств и мультимножеств - один из самых богатых объектов перечислительной комбинаторики. Основная причина этого - большое разнообразие способов комбинаторного представления перестановки. Перестановку можно представлять как слово или как функцию. В частности, функция
: [n]  [n], задаваемая равенством (i) = a i , соответствует слову a1a2 ... an.

Если рассматривать перестановку  конечного множества S как взаимно однозначное отображение : S  S, то естественно для каждого xS рассмотреть последовательность x, (x), 2(x), ... . В конце концов (так как  - взаимно однозначное соответствие, и множество S предполагается конечным) мы вновь получим x. Таким образом, для некоторого единственного наименьшего k  1 имеем, что k(x) = x и элементы x, (x), ... ,  k-1(x) все различны. Назовем последовательность (x, (x), ... ,  k-1(x)) циклом перестановкидлины k. Циклы (x, (x), ... ,  k-1(x)) и ( i(x),  i+1(x), ... ,  k-1(x), x, ... ,
i-1(x)) считаются эквивалентными. Каждый элемент S встречается тогда в единственном цикле перестановки , и мы можем рассматривать  как объединение непересекающихся циклов или, по-другому, как произведение различных циклов C1, ... , Cn. Например, если перестановка : [7]  [7] определена как , то есть (1) = 4, (2) = 2, (3) = 7, (4) = 1, (5) = 3, (6) = 6, (7) = 5, то  = (14)(2)(375)(6). Конечно, возможны различные обозначения такого представления перестановки; например, имеем:  = (753) (14) (6) (2). Можно определить стандартное представление:

  • в каждом цикле пишется первым его наибольший элемент;

  • циклы записываются в порядке возрастания их максимальных элементов.

Пусть c(n, k) - число таких перестановок множества из n элементов, которые имеют k циклов. Будем обозначать множество всех перестановок n - элементного множества символом n .

Утверждение 1.4. Числа c(n,k) удовлетворяют следующему рекуррентному сотношению:

c(n, k) = (n - 1) c(n-1, k) + c(n-1, k-1) , n, k 1,

с начальными условиями c(n, k) = 0 при n  0 или k  0, за исключением
c(0, 0) = 1.

Докажем сфомулированное утверждение.

Возьмем перестановку   n-1 с k циклами. Мы можем вставить символ n после любого из символов 1, 2, ... , n-1 в разложении перестановки  на непересекающиеся циклы n-1 способом, получив таким образом разложение на непересекающиеся циклы перестановки n с k циклами, где n встречается в цикле длины, не меньшей 2. Следовательно, существует (n-1)c(n-1,k) перестановок n c k циклами, для которых (n)n.

С другой стороны, если выбрана перестановка n-1 с k-1 циклом, ее можно достроить до перестановки n с k циклами, удовлетворяющей условию (n) = n. Положим



Следовательно, имеется c(n - 1, k - 1) перестановок n с k циклами, для которых (n) = n, и доказательство закончено.

Числа c(n,k) = ( - 1)n-ks(n,k) известны под названием чисел Стирлинга первого рода без знака.

Укажем на еще одну важную роль чисел c(n, k).

Пусть x - переменная. Фиксируем n  0. Тогда имеет место

Утверждение 1.5.



Доказательство. Положим



Отсюда следует, что

b(n, k) = (n  1)b(n  1, k) + b(n  1, k  1).

Поэтому b(n, k) удовлетворяют тем же рекуррентным соотношениям и начальным условиям, что и c(n, k), а значит, они совпадают.

1.3.3.Упорядоченные размещения.


Пусть x - переменная или действительное число.

Положим, по определению,

[x]n = x(x + 1)(x + 2)  (x + n  1).

Обозначение [x]n читается как “n факториал от x вверх” или “верхняя n-ая степень x”.

Определение.

Пусть X - множество из n объектов 1,2,...,n, которые должны быть размещены по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два размещения совпадают (равны), если в каждом ящике содержится одна и та же последовательность объектов. Размещения такого типа называются упорядоченными размещениями n объектов по m ящикам.

Приведем для примера всевозможные упорядоченные размещения двух объектов 1 и 2 в двух ящиках.

Ящики будем изображать в виде последовательности вертикальных черточек , представляющих разделяющие ящики перегородки. Таким образом 21 представляет размещение, при котором в первом ящике находится элемент 2, а во втором ящике - элемент 1.

Таблица всевозможных размещений двух объектов в двух ящиках имеет следующий вид:

1 2 ; 12 ; 1 2 ;

2 1 ; 21 ; 2 1 .

Утверждение 1.6. Число упорядоченных размещений n объектов по m ящикам равно

[m]n = m(m + 1)... (m + n - 1)

(полагаем [m]o = 1).

Доказательство. Построим сначала таблицу Tn-1 всех упорядоченных размещений объектов 1,2,...,n-1 по m ящикам. Каждое размещение

i1 i2 ...| ik ik+1 ...| ...|...|... in-1

можно представить как последовательность (n-1) + (m-1) символов, являющихся либо буквой i j , либо вертикальной чертой |. Чтобы из этой последовательности получить последовательность, представляющую упорядоченное размещение n объектов в нее достаточно всеми возможными способами добавить символ n. Символ n можно добавить к этой последовательности (n-1) +
(m-1) + 1 способами, помещая его перед самым первым символом, между двумя любыми символами и после последнего символа.

Таким образом

| Tn | =(m+n-1) |Tn-1| = (m+n-1)(m+n-2) ... (m+1) |T1| = [m]n.

Очевидно, что |T1| = 1.

Отметим простые, часто используемые соотношения:

[m]n = (m-n+1) [m]n-1 ; [m]n =(m+n-1) [m]n-1 ;

[m]n = m! / (m-n)! ; [m]n =(m+n-1)! / (m-1)! ;

[m]n = [m+n-1]n ; [m]n = [m]n-1(m+n-1).
Определение.

Пусть A - алфавит (то есть конечное множество символов) со множеством букв a1 , ... ,am , упорядоченных так, что

a1 < a2 < ...< am .

Cлово x1 x2 ... xn длины n - монотонное, если

x1 x2 ... xn .

Пример.

Пусть A={a,b,c,d}, a < b < c < d.

Тогда монотонными будут, например, следующие слова:

aaa, aab , abc, aad, bcd, ddd .

(По несколько устаревшей терминологии, это комбинации с повторениями из m объектов, взятые по n штук).

Утверждение 1.7. Число монотонных слов длины n в алфавите из m букв равно [m] n/n! .

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

Рассмотрим упорядоченное размещение n объектов 1,2 ,..., n по m ящикам a1 , ... , am и пусть ему соответствует монотонное слово следующим образом:
.

В соответствующем слове буква a1 написана столько раз, сколько объектов в ящике a1 , затем буква a2 столько раз, сколько объектов в ящике a2 , ... .

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

[m]n/n! .

Приложение. (Задача Муавра). Найдем число способов представления целого положительного числа m как упорядоченной суммы n неотрицательных целых чисел

m = u 1 + ...+ u n .

Два таких представления

m=u1 + ...+ un

и

m=u1 + ...+ un

будем считать совпадающими тогда и только тогда, когда

u1= u1 , ... , un= un ,

то есть когда совпадают слагаемые и порядок их следования.

Положим значение k равным частичной сумме первых k членов последовательности n1 , ... , nk : k = n1 + n2 + ... + nk . Каждому представлению m в виде суммы n слагаемых взаимно однозначно соответствует слово
12...n-1 , где 0 12 ... n-1 m. Таким образом, количество представлений m в виде упорядоченной суммы неотрицательных целых слагаемых равно количеству монотонных слов 12...n-1 длины n-1 в алфавите из m+1 символа (i  {0, 1, ... , m}, i = 1, ... , n-1).

Число представлений равно:


1.3.4.Сочетания и биномиальные коэффициенты.


Простейшими комбинаторными объектами являются сочетания и биномиальные коэффициенты.

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

Такие подмножества называются сочетаниями из m элементов по k элементов и обозначаются , а их количество обозначается или . Обозначение читается как “число сочетаний из m по k “ или просто “из m по k”.

Утверждение 1.8. Число различных подмножеств из k элементов множества A, |A |= m есть



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

Построим таблицу T всех строго возрастающих (монотонных, без повторений букв) слов длины k в алфавите A из m букв.

Пример.

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

A= {a,b,c,d,c} .

Положим k=3.

Тогда таблица T всех строго возрастающих слов длины 3 в алфавите A имеет следующий вид:

abc acd adc

abd ace

abe

bcd bde

bce

cde

Переставим буквы в каждом слове всеми возможными способами и обозначим получившуюся таблицу T. T - множество слов без повторения букв длины k в алфавите A.

В таблице T нет пропусков: каждое слово длины k появится в таблице T.

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

По утверждению 1 .2:

| T | = [ m ]k .

Поэтому

| T | = [ m ]k / k! .

Таким образом, окончательно получаем



Второе доказательство.

Определим множество (иногда обозначаемое как-нибудь иначе) как множество всех k-элементных подмножеств (или k-подмножеств) множества S и положим по определению (игнорируя прошлое использование символа ). Подсчитаем двумя способами число N(n, k) способов, которыми можно выбрать k-подможество T множества S, а затем линейно упорядочить его элементы. Множество T мы можем выбрать способами, а затем k способами выбрать первый по порядку элемент множества T, k-1 способом - второй элемент T и так далее. Таким образом

.

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

N(n, k) = n(n - 1) ... (n - k + 1).

Итак, мы дали комбинаторное доказательство того, что

,

и, следовательно,

.

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

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


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

Путь задана последовательность а1, а2, ... , аn, ... (неважно, конечная или бесконечная). Производящей функцией последовательности а1, а2, ... , аn, ... называется функция . При этом все рассматриваемые ряды в случае бесконечной последовательности считаются формально сходящимися (если эти ряды сходятся в какой-то области к функции f(x)), поскольку мы интересуемся не областью сходимости соответствующих рядов, а лишь соотношениями между коэффициентами таких рядов.

Например, из формулы



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

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

,

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

Нас будут интересовать производящие функции для последовательностей a0, a1, ... , an, ..., так или иначе связанных с комбинаторными задачами. С помощью производящих функций удается получать и исследовать самые разные свойства этих последовательностей.

Пусть - производящая функция последовательности b1, b2, ... , bn, ... и - производящая функция последовательности c1, c2, ... , cn, ... . Тогда из равенства



имеем



или в общем виде

.

В таком случае говорят, что последовательность коэффициентов cn есть свертка (произведение Коши) последовательностей an и bn.

1.3.4.2. Биномиальные коэффициенты


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

(1.1)

Для доказательства справедливости написанного соотношения ( 1 .1) достаточно заметить, что коэффициент при xk равен числу способов, которыми из m сомножителей (1+x) ... (1+x) можно выбрать k сомножителей.

Отметим некоторые важнейшие соотношения для биномиальных коэффициентов (чисел сочетаний).

1.

(1.2)

Это важнейшее соотношение - прямое следствие того факта, что каждому k-элементному подмножеству YX однозначно соответствует (n-k) - элементное подмножество X\Y множества X.

2.

(1.3)

Зафиксируем некоторый элемент x из n- элементного множества X. Множество T всех k - элементных подмножеств множества X распадается на два непересекающихся класса:

,

класс T1 подмножеств, которые не содержат элемент x, и класс T2 подмножеств, которые его содержат. Мощность первого класса составляет , а второго , то есть столько, сколько имеется (k-1) - элементных подмножеств множества X\{x}.

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

3. Полагая в ( 1 .1) x=1 получим



Эта формула следует и из того, что сумма слева есть число всех подмножеств n-элементного множества.

4.

(1.4)

Дифференцируя ( 1 .1) и полагая x=1, получаем соотношение ( 1 .4) .

5.

(1.5)

Равенство легко следует из следующего равенства для производящих функций:

(1+x)m+n =(1+x)m (1+x)n .

Полагая в ( 1 .5) m = k = n, получим

.

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

6. Полагая в ( 1 .1) x = –1, получаем

.

Отсюда следует, что

,

где через обозначена целая часть числа m/2.

1.3.4.3. Исчисление конечных разностей


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

Пусть дана функция , определенная на множестве действительных (возможно целых) чисел и принимающая действительные значения. Определим новую функцию (x), называемую первой разностью , формулой

.

Оператор  называется разностным оператором первого порядка; кратко и очень упрощенно можно определить исчисление конечных разностей как исследование оператора  . Можно применить оператор  k раз и получить k-ый разностный оператор

.

Число k(x) называется k-ой разностью  в точке x (k(0) называется k-ой разностью  в 0).

Определим другой оператор E, называемый оператором сдвига, формулой

.

Таким образом, =E  I, где I означает единичный оператор:

.

Тогда первая разность функции может быть записана в виде:

.

Разности более высоких порядков определяются рекуррентным соотношением



Откуда получаем выражение для n -ой разности:



В частности,

, (1.6)

что дает явную формулу для k-ой разности в терминах значений (0), (1), ... , (k). Нетрудно обратить формулу ( 1 .6) и выразить (n) через i (0). Именно,

. (1.7)

Напишем теперь в строку значения

... (-2) (-1) (0) (1) (2) (3)...

Если внизу написать между каждой парой последовательных членов (i), (i +1) их разность (i +1)  (i) = (i), то получим последовательность

...(-2) (-1) (0) (1) (2) ... .

Повторение этой процедуры приводит к таблице разностей функции , k-ая строка которой состоит из значений k(n). Диагональ, начинающаяся в (0) и идущая направо вниз, состоит из разностей k (0) в 0. Например, пусть (n) = n4 . Таблица разностей (начинающаяся с (0) ) выглядит так:

0




1




16




81




256




625

...




1




15




65




175




369













14




50




110




194



















36




60




84

























24




24































0





















Из формулы ( 1 .7) следует, что

(1.8)

В этом случае, так как n4 - многочлен четвертой степени и при фиксированном k есть многочлен степени k, написанное выше разложение обрывается после члена , то есть k 04 = 0, если k > 4 (или, более общим образом, k n4 = 0, если k > 4).

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

1. Функция  - полином степени, не превосходящей d, тогда и только тогда. когда d+1(n) =0 (или d(n) - постоянная).

2. Если многочлен (n) степени, не превосходящей d, разложен в ряд по базису , 0  k  d, то коэффициенты разложения есть k (0), то есть

.

Еще одна связь комбинаторных объектов с исчислением конечных разностей дается формулой ( 1 .15).

1.3.4.4. Разложения


Существует тесная связь между подмножествами множеств и разложениями целого числа.

Определение. Разложение n есть представление числа n в виде упорядоченной суммы положительных целых. Например, существует восемь разложений числа 4, а именно:

1+1+1+1 3+1

2+1+1 1+3

1+2+1 2+2

1+1+2 4

Если разложение  содержит в точности k слагаемых, то говорят, что  имеет k частей и называется k -разложением. Если a1 + a2 +...+ ak - k -разложение  числа n, определим (k 1) - элементное подмножество () (или (k 1)- подмножество ) множества {1, 2, ..., n-1} формулой

() ={a1 , a1+a2 , ... , a1 + a2 + ... + ak-1 } .

Эта формула устанавливает взаимно однозначное соответствие (биекцию) между всеми k-разложениями и (k 1)- подмножествами () множества {1, 2, ..., n-1}. Следовательно, существует k -разложений n и 2n - 1 разложений n. Разложение часто схематично представляют, рисуя в строку n точек и k  1 разделяющую вертикальную черту. Точки разделяются по k линейно упорядоченным “отделениям”, числа точек в отделениях дают k -разложение числа n . Например, последовательность

        

соответствуют разложению 1+2+1+1+3+2 .

Другая проблема, тесно связанная с разложениями, есть задача подсчета числа N(n, k) решений уравнения

x1 + x2 +... +xk = n

в неотрицательных целых числах. Решение такого уравнения называется слабым разложением n на k частей, или слабым k- разложением числа n. (Решение в положительных целых числах есть просто k-разложение n.) Если мы положим y1 = x1 +1, y2 = x2 +1, ... , yk =xk +1, то получим, что N(n, k) есть количество решений в положительных числах уравнения

y1 + y2 +... +yk = n +k ,

то есть число k-разложений числа n+k .

Таким образом, .

Подобным же приемом (найти его предоставляется читателю) доказывается, что число решений неравенства x1 + x2 +... +xk  n в неотрицательных целых числах есть .

k - подмножество T n - множества S иногда называют k - сочетанием из S без повторений. Так возникает задача подсчета числа k - сочетаний из S с повторениями; то есть мы выбираем k элементов из множества S, не взирая на их порядок и допуская повторяющиеся элементы. Обозначим число таких способов . Например, . Если S = {1,2,3}, то подходящие сочетания есть 11, 22, 33, 12, 13, и 23. Эквивалентное, но более точное определение и исследование сочетаний с повторениями может быть проведено, если ввести понятие мультимножества. На интуитивном уровне мультимножество есть множество с повторяющимися элементами, например {1, 1, 2, 5, 5}. Более точно, конечное мультимножество M на множестве S есть функция : S ( - множество натуральных чисел), такая, что ; (x) рассматривается как число повторений элемента x. Целое число называют мощностью или числом элементов M и обозначают M . Если S = {x1 , x2 ,
... , xn}, и (xi) = ai , то мы пишем . Множество всех k - мультимножеств на S обозначается символом .

Если S = {y1 , ... , yn} и мы положим xi = (yi), то увидим, что есть число решений в неотрицательных целых числах уравнения x1 + x2 + ... + xn = k . Это число, как мы видели, есть

. (1.9)

Прямое комбинаторное доказательство утверждения ( 1 .9) таково. Пусть

{a1, a2, ... , ak}, 1  a1 < a2 < ... < ak  n + k  1,

есть k -подмножество множества [ n + k  1]= {1, 2, ... , n+k  1}. Положим bi = ai  i + 1. Тогда {b1 , b2 , ... , bn} - k -мультимножество на множестве [n].

Обратно, если дано k - мультимножество 1  b1  b2  bk  n на [n], то определив ai формулой ai = bi + i  1, видим, что {a1 , a2 , ..., ak } есть k -подмножество множества [n + k  1] . Следовательно, мы определили взаимно однозначное соответствие между и , что и требовалось доказать.

Поучителен подход к мультимножествам с точки зрения производящих функций. Cовершенно аналогично проведенному исследованию подмножеств множества S = {x1 , x2 , ... , xn } имеем



Положим xi = x. Тогда

.

Но

,

так что

.

Появление элегантной формулы



не случайно. Это простейший пример комбинаторной теории взаимности.

1.3.5.Полиномиальные коэффициенты


Утверждение 1.9. Пусть X множество n различных объектов и пусть n1, n2,..., np неотрицательные целые числа, удовлетворяющие условию n1+ n2 + ... +np = n; количество размещений n объектов по ячейкам Y1,...,Yp, при которых каждая ячейка содержит n1, n2, ..., np объектов соответственно, есть



Доказательство. Пусть n1 + n2 + ...+ np = n. Ящик Y1 можно наполнить различными способами, после чего ящик Y2 можно наполнить способами и так далее.

Следовательно, искомое число размещений равно

=





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

(1.10)

Доказательство. Для доказательства справедливости равенства ( 1 .10) достаточно заметить, что коэффициент при равен числу способов выбрать из n сомножителей n1 сомножителей, из которых в произведение войдет переменная x1 , n2 сомножителей, из которых в произведение войдет переменная x2 , и так далее.

Следствие 1.

(1.11)

Для доказательства следствия 1 достаточно заметить, что

.

Отсюда следует равенство коэффициентов при соответствующих степенях в левой и правой частях последнего равенства:



Следствие 2.



Указанное равенство есть непосредственное следствие следующего соотношения для производящих функций:

.

Следствие 3.
.

Равенство следствия 3 непосредственно вытекает из вида производящей функции для полиномиальных коэффициентов, если в ( 1 .10) положить:

x1 = x3 = x5 = ... = +1 ,

x2 =x4 = x6 = ... = –1 .
  1   2   3   4   5   6   7   8   9   ...   12


Журавлев Ю.И., Флеров Ю.А
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации