Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 51

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 104 >> Следующая

У"' 0.
(:)
поскольку при к > п не существует сочетаний из п по к. В дальнейшем, если не будет специальных оговорок, считаем, что к ^ п. Отметим одно тождество, которое легко получается из (7)
если 0 Г I П. 12 С. В. Яблонский
178 Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
По аналогии с понятием унимодальной функции m введем понятие унимодальной последовательности {а*}, где к — 0, 1, ..п.
Определение. Последовательность (aj действительных чисел называется унимодальной, если существует такое Ап, что а0 < ах < ... < ahn ^ akn+i > >
> ... >ant т. е.:
1) последовательность строго возрастает на отрезке [О, &„] при кп > 0;
2} последовательность строго убывает на отрезке [А'„ + 1, п] при ка + 1 < п;
3) максимальное значение принимается не более чем в двух точках: кп и, быть может, кп+ 1 *).
Теорема 1. Последовательность чисел [(jt )]* &
*= 0, 1, ..nf унимодальна, и кп «= [л/2]. При четпом п максимум достигается в точке кп = [п/2] = п/2, а при нечетном п — в двух точках: кп = [п/2] = (п — 1)/2 н A;Il-f' + 1 =(п + 1)/2.
Доказательство. Оценим отношение двух сосед-
них ЧЛеНОВ ПОСЛеДОВатеЛЬНОСТИ у ^ Jj[k _ jT
а) При к < [п/2], т, е. к <(п + 1)/2, имеем (п — А: 4-
>1.
б) При к — 1 > п — [п/2], т. е. к — 1 > п — ^— =
” НГ * имееы "~|± ' < Поэтому (? )Д4 ",)<!. Теорема доказана.
Следствие. Максимальное значение ( ) ПРИ фик-
( п \
сированном п равно
Обозначим через С„1Й множество всех сочетаний из {«!, ..., ал) по А и через Сп^.Лж к(Сп^11 ь_а) — множество всех сочетаний из {аЛ, ..., ап-^ по к (соответственно по к~ 1). Так как каждому сочетанию из С?«.*, если оно содержит элемент а„, соответствует сочетание из а если оно не содержит а„, соответствует сочетание из
*) Си. [1]. Легко усмотреть следующую связь: если существует f{x), определенная на [0. л] и f(k) = й*, тогда из строгой унимодальности }[х) следует унимодальность {с*}.
Ч. II КОМБИНАТОРНЫЙ АНАЛИЗ 1"9
(?л-1, то существует взаимно однозначное соответствие между
^ и Сп~& и Сл—1, ь—1»
В силу этого
Дапиое рекуррентное соотношение позволяет (и при том С линей ПОЙ СЛОЖПОСТЫО) построить ДЛЯ чисел ^ к j таблицу, называемую треугольником Паскаля.
Таблица 2
п к
0 1 2 | 8 5 « 7 8 *
0 1
1 1 1
2 1 2 1 0
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
У 1 9 - 36 84 126 126 84 36 9 1

Сочетания элементов из Е = {аи ,.яп1 по к являются специальными подмножествами из Е, содержащими ровно к элементов. Соответствующие им наборы (аь а„) содержат ровно к единиц и образуют к-й слой «-мерного
куба Е**' Отсюда следует, что к-й слой содержит ( ? )
Ч. 11. UEri.bJ.Il АНАЛИЗ
точек. Следовательно, Е™ разбивается в прямую сумму слоев с номерами к = 0, 1, ..п и
(о)+(:)+- + (:Н"- о)
С числами ^ ^ связано функциональное тождество, называемое формулой для бинома Ньютона:
+ = ... + ( & )ж + **• (п)ж”’
В самом деле, коэффициент при хк получается всевозможными выборами из к скобок (14-д;) переменного х и из
остальных скобок 1, что дает как раз ^ ^ слагаемых.
Полагая в (10) х = 1, мы получаем тождество (9). Если в (10) езять х = — 1, то получим
(оН?)+???+<-? «я(")-а (“>
Покажем, далее, что
"0 4 7 V ( / \ Г / (0 при г с п.
Опираясь па тождества (8) и (11), имеем
|0 (-1)1_г (0(') - & (- 1>5-г (") (" -;)
1 при г = я, О при г <; п.
Аналогично доказывается, что при т 5* п .
уцг-К')!-'].!1”1"""’ аз,
1 \m~nj\m-t) I 0 при < 'Ы)
5. Сочетания с повторениями элементов из Е по к.
ттк
Обозначим через пп число сочетаний с повторениями элементов из множества Е = (щ, ..о„) по к.
Теорема 2. Ип = * 1 } •
Доказательство; Рассмотрим некоторое сочетание с повторениями из этого множества, содержащее к
Ч. II. КОМЕИНАТОГНЫЙ АНАЛИЗ 1S1
объектов. Пусть в сочетании встречаются s элементов - - ? » ал& (1 ^ h < ? ? ? < ? ^ п) соответственно с кратностями ки ..кя, где /<?! + ... + кй = к. Мы будем это соче-
тание записывать в следующем виде:
Ч fta k»
Ci[a-il ... au.
Установим взаимно одвозпачное соответствие между сочетаниями С повторениями объектов множества {«1, . . по к и обычными сочетаниями из множества {аь ..я„, Ьи ..JA_t} по где символы аи ..., аП} Ь1( ..., ио-парпо различны. Для этого сочетанию с повторениями
кя
di а*... аи Ч h г*
поставим в соответстЕпе сочетание
ai±atz ? * ? l^ftj+l^fej+2 • ? »
* * ? ^k^+fr.2—+ l • * ‘ ^A^+-.-+fes i4 1 ? * •
Как видно, объекты из множества {&1} Ь2, ..входят в данное сочетание массивами:
Ь1Ь2 ,,. b * • •
* ? ?*> ? • • ^Ai+...+йs-l*
Число массивов равно s, и каждый из них содержит соответственно по ki— 1, к2 — 1, ks—i объектов. Корректность такого построения вытекает из тождества
(fci-1 ) + (**- !)+... + (*,-!) + (*- 1) = к-1.
Отсюда вытекает также, что число объектов в сочетании равно
s + (&i — 1) + (кг — 1)“Ь ... + (kt — 1)'?= к.
Таким образом, построенное сочетание содержит по одному представителю каждого сорта объектов, встречающихся в сочетании с повторениями, т. е. «jL, .. - а длины массивов объектов из множества являются
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed