Файл: Учебное пособие ульяновск 2018 msc2010 05 Combinatorics ббк 22. 176 Удк 519. 1 В313 Рецензенты.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 70
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
10
Будем рассматривать X как возможно бесконечный ал- фавит из букв натурального веса. Будем составлять конеч- ные слова – упорядоченные последовательности букв. Сло- во ω длины n можно считать элементом тотально взвешен- ного множества X × · · · × X = X
n
. Вес ω – сумма весов входящих в него букв. Мы допускаем пустое слово нулевого веса – ∅. Это единственный элемент X
0
. Приписывание слов зада¨
ет умножение на множестве Ω = ∪
k ≥ 0
X
k
– свободном ассоциативном моноиде с единицей ∅ . Тогда
Ω(t) =
X
k ≥ 0
(X
k
)(t) =
X
k ≥ 0
X(t)
k
= 1 − X(t)
−1
Зафиксируем натуральное d ≥ 1 и рассмотрим Ω
(d)
– мно- жество слов веса, кратного d. Относительно приписывания слов Ω
(d)
– подмоноид Веронезе Ω , для которого:
Ω
(d)
(t) =
X
n ≥ 0
] (Ω
nd
) · t nd
= d
−1
·
d
X
r = 1
Ω t · exp {2πir/d}
,
поскольку d
X
r = 1
exp {2πirn/d} = d · [ d \ n ] .
Здесь и далее использована числовая функция Айверсона.
Для логического высказывания S определяется значение:
[ S ] =
0 , если S ложно;
1 , если S истинно.
Рассмотрим X
(d)
– подмножество слов Ω
(d)
строго положи- тельной длины (положительного веса), никакое собственное начало которых не лежит в Ω
(d)
. Тогда X
(d)
порождает Ω
(d)
и
11
любое слово из Ω
(d)
представляется в виде произведения слов из X
(d)
единственным образом. То есть, Ω
(d)
– ассоциативный моноид, свободно порожд¨енный X
(d)
. Для Ω
(d)
(t) применимо ранее привед¨
енное рассуждение, и мы получаем равенство:
1 − X
(d)
(t)
−1
= d
−1
·
d
X
r = 1
1 − X t · exp {2πir/d}
−1
Для d = 1 нет ничего нового: X
(d)
= X, Ω
(d)
= Ω. Рассмот- рим более содержательный случай.
Пусть X = {x, y}, где w
X
(x) = 1, w
X
(y) = 2. Получаем:
X(t) = t + t
2
,
Ω(t) =
1 1 − t − t
2
=
X
k ≥ 0
F
k
· t k
,
где (F
k
)
k ≥ 0
= (1, 1, 2, 3, 5, 8, . . . ) – числа Фибоначчи. Тогда
1−X
(2)
(t)
−1
=
1 2
·
1 1 − t − t
2
+
1 1 + t − t
2
=
1 − t
2 1 − 3t
2
+ t
4
,
X
(2)
(t) = 1 −
1 − 3t
2
+ t
4 1 − t
2
= t
2
+
t
2 1 − t
2
= 2t
2
+ t
4
+ t
6
+ · · · ,
Моноид Ω
(2)
свободно порожд¨ен бесконечным множеством слов ч¨
етного веса:
X
(2)
= {y , x · y s
· x ; s ≥ 0} .
В общем случае можно получить формулу, доказывающую бесконечную порожд¨енность моноида Ω
(d)
при d > 1:
X
(d)
(t) =
F
d
· t d
− (−1)
d
· t
2d
1 − F
d−2
· t d
, где F
−1
:= 0 .
12
Бесконечная пророжд¨енность Ω
(d)
в предыдущем примере
– следствие более общего факта, доказанного в ([2]).
2.3. Предложение. Пусть Ω – ассоциативный моноид, сво- бодно порожд¨енный взвешенным множеством X и d ≥ 1. Тог- да равносильно:
1. Ω
(d)
– конечнопорождена;
2. для некоторого многочлена P (t), X(t) = t n
· P (t d
).
Поэтому, если X содержит элементы различных весов, то моноид Ω
(d)
– конечнопорожд¨ен лишь для конечного числа значений d.
2.4. Замечание. Из взвешенного множества X можно орга- низовать иные объекты. Например, S – ассоциативно-ком- мутативный моноид, свободно порожд¨
енный X, состоящий из мультимножеств, собираемых из элементов X, с операцией объединения мультимножеств (при этом кратности вхожде- ния элементов складываются). Или Λ – ассоциативно-анти- коммутативную алгебру, свободно порожд¨
енную X. Е¨
е бази- сом можно считать подмножества X с фиксированным по- рядком. В этих случаях
S(t) =
Y
k ≥ 1 1 − t k
−] (X
k
)
, Λ(t) =
Y
k ≥ 1 1 + t k
] (X
k
)
Но соответствующие подобъекты Веронезе S
(d)
и Λ
(d)
уже не обязательно будут свободно порождены, что затрудняет вычисление производящих функций их порождающих мно- жеств. Хотя нахождение их в каждом конкретном случае при небольшом X не представляет труда.
13
Последние формулы дают пример производящих функций нового вида. Поэтому провед¨ем систематизацию предмета.
2.5. Определение. Пусть (a n
, n ≥ 0) – числовая последова- тельность. Определим е¨
е ряды Гильберта и Гурвица:
H
a
(t) =
X
n ≥ 0
a n
· t n
, G
a
(t) =
X
n ≥ 0
a n
·
t n
n!
О втором ряде сказано в ([19, т. II, с. 159]). Его также на- зывают экспоненциальным, и с ним работал Лаплас. Такие производящие функции применяются в теории вероятностей
([26, с. 58-62]). Они удобны для линейно-рекуррентных после- довательностей ([19, т. II, с. 117], [31, гл. 4]), для исчисления
Блиссара ([26, с. 53]), поскольку линейны по индексу:
H
a+b
(t) = H
a
(t) + H
b
(t) ,
H
λ · a
(t) = λ · H
a
(t) ;
G
a+b
(t) = G
a
(t) + G
b
(t) ,
G
λ · a
(t) = λ · G
a
(t) .
Они согласованы со сдвигом последовательности: если
(a
0
, a
1
, . . . ) ⇑ = (0, a
0
, a
1
, . . . ), (a
0
, a
1
, . . . ) ⇓ = (a
1
, a
2
, . . . ) , то
H
a ⇑
(t) = t · H
a
(t) ,
G
a ⇑
(t) =
Z
t
0
G
a
(x) dx ;
H
a ⇓
(t) = (H
a
(t) − H
a
(0))/ t ,
G
a ⇓
(t) = G
a
0
(x) .
Линейны ряд Дирихле и ряды Ламберта, важные в ариф- метических задачах:
D
a
(s) =
X
n ≥ 1
a n
n s
,
L
∓
a
(t) =
X
n ≥ 1
a n
·
t n
1 ∓ t n
В алгебраической комбинаторике полезны функции Эйлера и дзета-функция Вейля:
E
∓
a
(t) =
Y
n ≥ 1
(1 ∓ t n
)
∓ a n
,
Z
a
(t) = exp
X
n ≥ 1
a n
·
t n
n
14
Своей мультипликативностью они похожи на экспоненту:
E
∓
a + b
(t) = E
∓
a
(t) · E
∓
b
(t) ,
Z
a + b
(t) = Z
a
(t) · Z
b
(t) .
Дзета функция А. Вейля связана с гипотезами в алгеб- раической геометрии (см. [35, с. 559-570]). Функции Эйлера связаны с разбиениями чисел и перестановками. Замечатель- ным результатом тут является Пентагональная лемма Эйле- ра (см. [37, с. 24-27]):
Y
n ≥ 1
(1 − t n
) = 1 − x − x
2
+ x
5
+ x
7
− x
12
− x
15
+ x
22
+ · · · =
=
X
k ∈ Z
(−1)
k
· t k · (3k + 1)/2
Смысл е¨
е в том, что при разложении натуральных чисел в сумму различных слагаемых, количество разбиений на ч¨
етное число слагаемых от количества разбиений на неч¨
етное число слагаемых отличается не более, чем на единицу. И Эйлер ука- зал – когда и каково это единичное отклонение.
Видимо, ещ¨
е не изученным фактом является аналогичное наблюдение о разбиении в сумму чисел Фибоначчи:
(1 − x)·(1 − x
2
)·(1 − x
3
)·(1 − x
5
)·(1 − x
8
)·(1 − x
13
)· . . . =
= 1 − x − x
2
+ x
4
+ x
7
− x
8
+ x
11
− x
12
− x
13
+ x
14
+ . . . .
Ясно, что перечисленным набором производящие функции не исчерпываются. Линейные варианты сворачивают после- довательности с некоторой системой функций, мультиплика- тивные – экспонируют такие представления. Мыслимы иные способы вовлечения последовательностей в алгебраические
15
или аналитические выражения с неограниченным количест- вом операций, которые можно рассматривать либо как функ- ции, либо как формальные комбинации. Действия с ними всегда подразумевают некоторое обоснование. Свойства про- изводящих функций должны быть предварительно исследо- ваны. Наиболее изучены степенные ряды (см. [9, 10, 11, 19]),
поэтому популярны производящие функции на их основе.
Вышеуказанные производящие функции зависимы:
E
∓
a
(t) = exp nX
k ≥ 1
(±1)
k − 1
k
· H
a
(t k
) − H
a
(0)
o
,
L
∓
a
(t) =
X
k ≥ 1
(±1)
k−1
· H
a
(t k
) − H
a
(0)
,
D
a
(s) =
1
Γ(s)
·
Z
+∞
0
H
a
(e
−x
) − H
a
(0)
· x s−1
dx ,
Z
a
(t) = exp n
Z
t
0
H
a
(x) − H
a
(0)
x dx o
,
H
a
(t) =
Z
+∞
0
G
a
(tx) · e
−x dx .
Но “символически-операционно” все производящие функ- ции эквивалентны. Различаются они только тем, насколь- ко св¨
ернуто могут представлять изучаемые конфигурации.
Поэтому, гипотетически, для каждой задачи должна быть своя “идеально подходящая” производящая функция. Удиви- тельно, что некоторые из них подходят ко многим, на первый взгляд несходным задачам.
16 3. БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ
Комбинаторный анализ в математике начался с биномиаль- ного разложения. Слово бином означает некоторую двусо- ставленность, передаваемую латинским словом binominis –
двуим¨
енный. До середины XVI в. слово
”
бином“ означало арифметический двучлен любого рода. Современный смысл понятие приобрело у голландца Стевина в “La Disme” 1585 г.
Отдельные случаи разложения степени бинома появлялись и ранее. Открытие биномиальной теоремы приписывают древ- некитайским и арабским математикам. Известно, что немец
Штифель в “Arithmetica integra” 1544 г. разобрал бином 17-ой степени. Предполагают, что англичанин Бриггс в “Arithmetica logarithmica” 1624 г. для вычисления логарифмов использо- вал биномы с дробными показателями. В XVII в. бином зна- ли уже многие математики, например, – Паскаль, Лейбниц,
Грегори и Валлис.
Смысл биномиальной теоремы в том, что для натурально- го n разложение n-ой степени бинома содержит 2
n слагае- мых. Но перестановочность сомножителей позволяет привес- ти подобные слагаемые в сумме, уменьшив их до (n + 1)-го:
(a + b)
n
=
n
X
k = 0
n k
· a k
· b n−k
, где
n k
=
n!
k! · (n − k)!
Современная формула биномиальных коэффициентов поя- вилась после того, как немецкий математик Крамп в 1808 г.
предложил обозначение n! = 1 · 2 · . . . · n. Такое произведение множителей (факторов) называется факториалом. Ранее его обозначали символом Эйлера П(n).
17
Ньютон в письме Ольденбургу 1676 г. сообщил биномиаль- ное правило для вещественных показателей. Абель в 1826 г.
обосновал применение комплексных степеней, и так появи- лась формула Ньютона-Абеля:
(1 + x)
α
=
X
k ≥ 0
α
k
· x k
(ℵ)
3.1. Замечание. Коэффициенты ряда (ℵ) легко получить из формулы Тейлора. Но сходимость ряда к указанной функции не очевидна. Она следует из регулярности композиции:
(1 + z)
α
= exp α · ln (1 + z)
в области {z ∈ C , |z| < 1} .
Вещественное обоснование формулы Ньютона-Абеля тако- во. Найд¨
ем коэффициенты ряда a
0
+ a
1
x + a
2
x
2
+ . . . , удов- летворяющего свойствам функции f (x) = (1 + x)
α
:
f
0
(x) = α · (1 + x)
α−1
=
α
1 + x
· f (x) ,
f (0) = 1 .
При подстановке ряда получим равенства:
(1 + x) ·
X
k ≥ 0
ka k
· x k−1
= α ·
X
k ≥ 0
a k
· x k
,
a
0
= 1 ;
a
1
+
X
k ≥ 1
(ka k
+ (k + 1)a k+1
) · x k
= α +
X
k ≥ 1
α a k
· x k
Приравнивая коэффициенты при одинаковых степенях x,
получим цепочку равенств:
a
0
= 1 ; a
1
= α ; k · a k
+ (k + 1) · a k+1
= α · a k
, k ≥ 1 ;
a k+1
=
α−k k+1
· a k
=
α−k k+1
·
α−(k−1)
k
· . . . ·
α−1 2
·
α−0 1
И окончательно находим:
18
α
k
= a k
=
α · (α−1) · . . . · (α−(k−1))
k!
,
α
0
= 1 .
При α ∈ N
0
= N ∪ {0} все слагаемые разложения бинома,
начиная с k = α + 1 , содержат нулевой сомножитель в числи- теле дроби и поэтому обнуляются. Ненулевые коэффициенты при этом преобразуются к известному факториальному виду.
Биномиальный ряд и f (x) в этом случае являются всюду сов- падающими полиномами степени α.
При α 6∈ N
0
все коэффициенты разложения бинома – нену- левые. Существует предел отношения их модулей:
lim k → ∞
a k+1
a k
= lim k → ∞
α − k k + 1
= 1 .
Поэтому радиус сходимости формального степенного ря- да равен 1. На интервале (−δ, δ ), при 0 < δ < 1, он схо- дится равномерно к бесконечно дифференцируемой функции,
удовлетворяющей дифференциальным условиям f (x). Поэто- му биномиальный ряд сходится к f (x) на (−1, 1).
Мы считаем, что биномиальные коэффициенты с отрица- тельными или нецелыми нижними индексами – нулевые.
3.2. Замечание. Биномиальные коэффициенты подчиняют- ся многим закономерностям. Авторы книги ([10]) отмечают:
”
Биномиальные коэффициенты подобны хамелеонам, с л¨егкостью изменяющим свою внешность.“(с. 232)
Из несложных формул могут вытекать интересные следс- твия. Например, при n, k ∈ N
0
имеем равенства:
k ·
n k
= n·
n − 1
k − 1
, (n − k)·
n k
= n·
n − 1
k
(./)
19
Далее, при n ∈ N
0
рассмотрим биномиальное тождество:
1 = (1 − x + x)
n
=
n
X
k = 0
n k
· (1 − x)
k
· x n − k
Справа, чисто формально, стоит полином степени n, но фактически его степень нулевая – ведь он тождественно равен единице. Теперь для целых 0 ≤ s ≤ n определим полиномы –
неполные биномиальные суммы:
n
B
s
(x) =
s
X
k = 0
n k
· (1 − x)
k
· x n − k
;
n
B
0
(x) = x n
,
n
B
1
(x) = nx n−1
−(n−1)x n
, . . . ,
n
B
n
(x) = 1 .
Они имеют целые коэффициенты и составляют базис про- странства Q[x]
≤ n
, – полиномов над Q степени не выше n , –
что следует из линейной независимости системы:
x n
, (1−x)· x n−1
, (1−x)
2
· x n−2
, . . . , (1−x)
n−1
· x , (1−x)
n
Некоторые свойства n
B
s
(x) очевидны, другие – не очень:
n
B
s
(0) = [ s = n ] ,
n
B
s
(1) = 1 .
3.3. Лемма. Полиномы n
B
s
(x) монотонно растут на [0, 1].
Доказательство. Вычислим производные n
B
s
(x):
n
B
0
s
(x) =
s
X
k = 0
n k
· (1 − x)
k
· x n − k
0
=
=
s
X
k = 0
n k
·
−k·(1−x)
k−1
· x n−k
+ (n−k)·(1−x)
k
· x n−k−1
=
20
= −
s
X
k = 0
n k
·k(1−x)
k−1
x n−k
+
s
X
k = 0
n k
·(n−k)·(1−x)
k x
n−k−1
=
= n·
−
s
X
k = 1
n−1
k−1
(1−x)
k−1
x n−k
+
s
X
k = 0
n−1
k
(1−x)
k x
n−k−1
!
=
= n·
−
s−1
X
k = 0
n−1
k
(1−x)
k x
n−k−1
+
s
X
k = 0
n−1
k
(1−x)
k x
n−k−1
!
=
= n·
n−1
s
·(1−x)
s
·x n−s−1
= (n−s)·
n s
·(1−x)
s
·x n−s−1
Здесь мы использовали формулы (./) на стр. 18. Итак,
ясно, что n
B
0
s
(x) ≥ 0 на [0, 1], что доказывает Лемму 3.3.
Заметим, что для s < n здесь же доказана строгая монотон- ность полиномов n
B
s
(x) на [0, 1] .
3.4. Следствие. При фиксированном s и x ∈ (0, 1)
lim n → ∞
n
B
s
(x) = 0 , lim n → ∞
n
X
k = s
n k
· (1 − x)
k
· x n−k
= 1 .
Доказательство. Можно считать, что s < n. Рассмотрим два случая: 0 < x ≤ 0.5 и 0.5 < x < 1 . В первом случае имеется оценка:
0 <
n
B
s
(x) ≤
n
B
s
(0.5) =
1 2
n
·
s
X
k = 0
n k
Сумма в правой части является полиномом от n степени s,
и поэтому по оценочному признаку получаем:
lim n → ∞
n
B
s
(x) = lim n → ∞
1 2
n
·
s
X
k = 0
n k
= 0 .