Файл: Учебное пособие ульяновск 2018 msc2010 05 Combinatorics ббк 22. 176 Удк 519. 1 В313 Рецензенты.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 73
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
35
Q
3
(t) = 8t
3
− 36t
2
+ 24t .
Из формулы следует, что Q
k
(0) = [ k = 0 ]. Из сравнения сте- пеней многочленов, и того, что старший коэффициент P
k
(t)
равен 2
k
, получим тождества:
m
X
n = 0
(−1)
n
·
m n
·
−2n k
= 0
при m > k ,
k
X
n = 0
(−1)
n
·
k n
·
−2n k
= 2
k
Остальные суммы можно пересчитать из иных комбинатор- ных соображений. Собер¨ем из Q
k
(t) экспоненциальную про- изводящую функцию:
G
Q(t)
(z) =
X
k≥0
Q
k
(t)
k!
· z k
=
=
X
k ≥ 0
z k
·
X
m ≥ 0
t m
m!
·
X
m n = 0
(−1)
n
·
m n
·
−2n k
=
=
X
m ≥ 0
t m
m!
·
X
m n = 0
(−1)
n
·
m n
·
X
k ≥ 0
−2n k
· z k
=
=
X
m ≥ 0
t m
m!
·
X
m n = 0
(−1)
n
·
m n
· (1 + z)
−2n
=
=
X
m ≥ 0
t m
m!
·
X
m n = 0
m n
· −(1 + z)
−2
n
=
=
X
m ≥ 0
t m
m!
· 1−(1+z)
−2
m
= exp
t · 1−(1+z)
−2
=
36
= exp
(
−t·
X
s ≥ 1
−2
s
·z s
)
= exp
(
t·
X
s ≥ 1
(−1)
s+1
·(s+1)·z s
)
=
=
Y
s ≥ 1
exp
t · (−1)
s+1
· (s + 1) · z s
=
=
Y
s ≥ 1
X
n s
≥ 0
t · (−1)
s+1
· (s + 1) · z s
n s
n s
! =
=
Y
s ≥ 1
X
n s
≥ 0
(−t · (s + 1) · (−z)
s
)
n s
/ n s
! =
=
X
k ≥ 0
(−z)
k
·
X
n1, n2, ... ≥ 0 1 · n1 + 2 · n2 + ... = k
(−t)
n
1
+ n
2
+ ...
·
2
n
1
· 3
n
2
· . . .
n
1
! · n
2
! · . . .
Поэтому Q
k
(t) выражается через разбиения числа k – разло- жения в сумму невозрастающих натуральных слагаемых:
λ = (λ
1
, λ
2
, . . . , λ
r
) ` k : λ
1
+ λ
2
+ . . . + λ
r
= k ,
λ
1
≥ λ
2
≥ . . . ≥ λ
r
> 0 .
Слагаемые λ
i называются частями разбиения, их количес- тво r = l(λ) – длиной разбиения, разбиваемое число k = |λ| –
мощностью разбиения, а количество повторений конкретного слагаемого в разбиении – кратностью этого слагаемого:
n s
(λ) = ]{λ
i
= s | i = 1, . . . , l(λ)} ,
n
1
(λ) + n
2
(λ) + n
3
(λ) + . . . = l(λ) ,
1 · n
1
(λ) + 2 · n
2
(λ) + 3 · n
3
(λ) + . . . = |λ| .
В этих обозначениях при k ≥ 1 получаем:
Q
k
(t) = (−1)
k
· k! ·
X
λ ` k
(−t)
l(λ)
·
Y
s ≥ 1
(s + 1)
n s
(λ)
n s
(λ)!
;
37
m
X
n = 0
(−1)
n
·
m n
·
−2n k
= (−1)
k−m
· m! ·
X
λ ` k l(λ) = m
Y
s ≥ 1
(s+1)
n s
(λ)
n s
(λ)!
Многочлены Q
k
(t) можно определять рекуррентно:
1
x k+1
· Q
k+1
1
x
2
· exp
−1
x
2
=
exp
−1
x
2
(k)
!
0
=
=
1
x k
· Q
k
1
x
2
· exp
−1
x
2
0
=
−k x
k+1
Q
k
1
x
2
· exp
−1
x
2
+
+
1
x k
Q
0
k
1
x
2
·
−2
x
3
· exp
−1
x
2
+
1
x k
Q
k
1
x
2
· exp
−1
x
2
·
2
x
3
=
=
−k x
k+1
Q
k
1
x
2
+
−2
x k+3
Q
0
k
1
x
2
+
2
x k+3
Q
k
1
x
2
· exp
−1
x
2
Следовательно, получаем соотношение (t = 1/x
2
, ∂ = d dt
):
Q
k+1
1
x
2
= −k Q
k
1
x
2
−
2
x
2
Q
0
k
1
x
2
+
2
x
2
Q
k
1
x
2
,
Q
k+1
(t) = (2t−k)·Q
k
(t)−2t·Q
0
k
(t) = {2t − k − 2t· ∂}Q
k
(t) .
Откуда следует “дифференциальная” формула:
Q
k+1
(t) = {2t−k−2t·∂}·{2t−k+1−2t·∂}· . . . ·{2t−1−2t·∂}2t ,
и е¨
е символическое “ биномиальное ” представление:
Q
k+1
(t) = (−1)
k
· k!·
2t·∂ + k − 2t k
2t.
38 4. ПОЧТИ ТОЖДЕСТВЕННЫЕ ФУНКЦИИ
Следующая комбинаторная задача возникла из анализа про- изводящих функций Эйлера вида E
−
a
(t). О ней сообщалось в заметке ([6]).
4.1. Определение. Пусть (a n
, n ≥ 1) – вещественная после- довательность. Сопоставим ей произведение:
I
a
(x) = x · E
−
a
(t) = x
. Y
k ≥ 1 1 − x k
a k
Разложим это выражение по степеням x:
I
a
(x) = x
Y
k ≥ 1 1−x k
−a k
= x
Y
k≥1
X
n k
≥ 0
(−1)
n k
−a k
n k
· x k·n k
=
= x ·
X
m ≥ 0
x m
·
X
λ ` m
(−1)
l(λ)
·
Y
k ≥ 1
−a k
n k
(λ)
=
= x ·
1 + x · a
1
+ x
2
·
a
2
+
a
1
· (a
1
+ 1)
2
+
+ x
3
·
a
3
+ a
1
· a
2
+
a
1
· (a
1
+ 1) · (a
1
+ 2)
6
+ . . .
=
= x + b
2
· x
2
+ b
3
· x
3
+ · · · = x + o (x) .
Любой вещественный степенной ряд вида x + o (x) одно- значно представим некоторым произведением I
a
(x), посколь- ку коэффициенты его – (b n
, n ≥ 2) выражаются разрешимы- ми относительно (a k
, k ≥ 1) полиномами:
b m+1
=
X
λ ` m
(−1)
l(λ)
·
Y
k ≥ 1
−a k
n k
(λ)
= a m
+ . . . .
39
Из вида уравнений следует, например, что связанные коэф- фициенты (a k
) и (b n
) являются целочисленными одновремен- но. Ясно, что из неотрицательности (a k
) следует неотрица- тельность (b n
), но обратное утверждение без дополнительных предположений неверно. Что иллюстрируется примером:
x + x
2
= x · (1 + x) = x · (1 − x)
−1
· (1 − x
2
)
−(−1)
4.2. Замечание. Области сходимости H
1 2 3 4 5 6 7
a
(x) и I
a
(x) могут не совпадать. Например, для a n
= [ n = 1 ] имеем:
I
a
(x) = x
(1 − x)
1
, H
a
(x) = x ;
а для a n
= µ(n)/n, n ≥ 1 наоборот – радиус сходимости ряда
H
a
(x) равен 1, но I
a
(x) = x · e x
– функция целая.
Здесь µ(n) – функция М¨
ебиуса, входящая в формулу обра- щения Дедекинда и Лиувилля ([10], с. 160-161).
Но различие сходимости I
a
(x) и H
a
(x), как свидетельствует следующее утверждение, не может быть фатальным.
4.3. Лемма. Регулярность в нуле функции I
a
(x) равносильна регулярности в нуле H
a
(x).
Доказательство. Регулярность в нуле функции I
a
(x) равно- сильна регулярности в нуле ln(I
a
(x)/x), для которой можно получить степенное разложение:
ln nY
k ≥ 1 1 − x k
−a k
o
=
X
k ≥ 1
a k
· ln n
1 − x k
−1
o
=
=
X
k ≥ 1
a k
·
X
s ≥ 1
x ks s
=
X
k, s ≥ 1
a k
· x ks s
=
ks = m k\m
=
=
X
m ≥ 1
x m
m
·
X
k \ m k · a k
=
X
m ≥ 1
β
m
· x m
40
Коэффициенты степенного разложения (β
m
, m ≥ 1) функ- ции ln(I
a
(x)/x) с показателями (a k
, k ≥ 1) связаны соотно- шениями:
m·β
m
=
X
k \ m k· a k
,
k· a k
=
X
m \ k
µ
k m
· m·β
m
Регулярный степенной ряд имеет ненулевой радиус схо- димости. По формуле Коши-Адамара, это равносильно экс- поненциальной ограниченности его коэффициентов. Предпо- ложим такую ограниченность всех показателей |a k
| < M
k
Можно считать, что M > 1. Тогда получаем оценку:
|m·β
m
| ≤
X
k \ m k· |a k
| <
X
1 ≤ k ≤ m m·M
m
= m
2
·M
m
,
|β
m
| < m·M
m
< 2
m
·M
m
= (2M )
m
Аналогично, из оценки коэффициентов |β
k
| < L
k
, с уч¨
етом неравенств L > 1 и |µ(s)| ≤ 1, получаем:
|k· a k
| ≤
X
m \ k
µ
k m
· m·|β
m
| <
X
1 ≤ m ≤ k k·L
k
= k
2
·L
k
,
|a k
| < k·L
k
< 2
k
·L
k
= (2L)
k
Поэтому экспоненциальные ограниченности (a k
) и (β
n
) рав- носильны, что и доказывает лемму.
Произведение I
a
(x) = x + o (x) интересно не только фун- кционально, но и символически,– оно выражает комбинатор- ные свойства любых вещественных последовательностей (a k
).
Например, степенные ряды вида x + o (x) образуют группу относительно подстановок, поэтому на числовых последова- тельностях можно задать новую групповую операцию:
I
a ∗ b
(x) = I
a
(I
b
(x)) .
41
Поскольку I
0
(x) = x, нулевая последовательность является нейтральным элементом этой группы:
(a k
) ∗ 0 = 0 ∗ (a k
) = (a k
) .
4.4. Пример. Пусть a n
= [ n = 1 ], тогда I
a
(x) = x/(1−x) и мы получим равенства:
I
a
2
(x) = I
a
(I
a
(x)) =
x
1 − x
1 −
x
1 − x
=
x
1 − 2x
Теперь вычислим эйлеровы показатели (u s
(α)) рациональ- ной функции I
u(α)
(x) = x/(1 − α · x):
ln
I
u(α)
(x)/x
= ln nY
s ≥ 1 1−x s
−u s
(α)
o
= ln n
(1−α·x)
−1
o
,
X
m ≥ 1
x m
m
·
X
s \ m s · u s
(α) =
X
m ≥ 1
α
m
· x m
m
,
α
m
=
X
s \ m s · u s
(α) ,
u s
(α) = s
−1
·
X
m \ s
µ (s/m) · α
m
Если q = p a
– степень простого, тогда u s
(q) – число не- приводимых над полем F
q полиномов степени s с единичным старшим коэффициентом. Этот факт теории конечных полей имеет комбинаторное доказательство, опирающееся на фак- ториальность кольца полиномов над полем.
Обозначим R
m
– множество унитальных над F
q полиномов степени m. У них m свободных коэффициентов (кроме еди- ничного старшего), их количество ] (R
m
) = q m
. Множество неприводимых унитальных над F
q полиномов степени s обо- значим U
s
⊂ R
s
: ] (U
s
) = u s
(q). Пусть U =
S
s ≥ 1
U
s
– мно- жество всех неприводимых унитальных над F
q полиномов.
42
Тогда получим равенства:
Y
u ∈ U
1 − t deg (u)
· u
−1
=
Y
u ∈ U
X
n u
≥ 0
t deg (u) · n u
· u n
u
=
= 1 +
X
m ≥ 1
t m
·
X
n n u ≥ 0,
P
u ∈ U deg (u) · n u = m o
Y
u ∈ U
u n
u
=
= 1 +
X
m ≥ 1
t m
·
X
r ∈ R
m r .
Если в это равенство вместо переменной-полинома u под- ставить единицу, то получим r =
Q
u ∈ U
u n
u
= 1 и, наконец:
Y
s ≥ 1 1 − x s
−u s
(q)
=
Y
u ∈ U
1 − t deg (u)
−1
=
= 1 +
X
m ≥ 1
t m
· ] (R
m
) = 1 +
X
m ≥ 1
q m
· t m
= 1 − q · t
−1
Поэтому, искомая последовательность a
2
= ([ n = 1 ])
2
= u(2) = (2, 1, 2, 3, 6, 9, 18, 30, . . . )
считает неприводимые унитальные полиномы над F
2 4.5. Пример. Пусть b n
= [ n = 2 ], тогда I
b
(x) = x/(1−x
2
) и мы получим равенства:
I
b ∗ a
(x) = I
b
(I
a
(x)) =
x
1−x
,
1−
x
1−x
2
!
=
x·(1−x)
1−2x
=
=
x
(1 − x)
−1
· (1 − 2x)
= I
u(2) − a
(x) ;
I
a ∗ b
(x) = I
a
(I
b
(x)) =
x
1−x
2
1−
x
1−x
2
=
x
1−x−x
2
=
43
= x + x
2
+ 2x
3
+ 3x
4
+ 5x
5
+ 8x
6
+ · · · =
X
n≥0
F
n
·x n+1
Здесь (F
n
) – числа Фибоначчи. Мы убеждаемся, что умно- жение последовательностей некоммутативно b ∗ a 6= a ∗ b . При этом результат a ∗ b можно вычислить точнее.
Пусть 1 − x − x
2
= (1 − αx) · (1 − βx). Тогда
(a ∗ b)
k
= u k
(α) + u k
(β) = k
−1
·
X
m \ k
µ (k/m) · (α
m
+ β
m
) .
Далее можно обойтись без вычисления значений α и β, вос- пользовавшись следующей леммой.
4.6. Лемма. Пусть P (x) = (1 − αx)·(1 − βx)· . . . ·(1 − θx) –
полином, тогда
(α + . . . + θ) + (α
2
+ . . . + θ
2
)·x + (α
3
+ . . . + θ
3
)·x
2
+ . . . =
=
α
1 − αx
+ . . . +
θ
1 − θx
= −
P
0
(x)
P (x)
Доказательство. Искомое тождество мы получим, продиф- ференцировав равенство:
− ln(P (x)) = − ln(1 − αx) − . . . − ln(1 − θx) .
Применим эту лемму к нашему частному примеру:
X
n ≥ 0
α
n+1
+ β
n+1
· x n
= −
(1 − x − x
2
)
0 1 − x − x
2
=
1 + 2x
1 − x − x
2
=
= (1 + 2x) ·
X
n≥0
F
n
· x n
= F
0
+
X
n≥1
(F
n
+ 2F
n−1
)· x n
=
= 1 +
X
n ≥ 1
(F
n+1
+ F
n−1
)· x n
44
Таким образом (полагая F
−1
= 0), получаем равенства:
α
m
+ β
m
= F
m
+ F
m−2
,
m ≥ 1 ;
(a ∗ b)
k
= k
−1
·
X
m \ k
µ (k/m) · (F
m
+ F
m−2
) ,
k ≥ 1 .
В итоге, последовательность a ∗ b такова :
1, 1, 1, 1, 2, 2, 4, 5, 8, 11, 18, 25, 40, 58, 90, 135, . . .
И теперь у нас есть задел для вычисления b
2
:
I
b
2
(x) = I
b
(I
b
(x)) =
x
1 − x
2
,
1 −
x
1 − x
2
2
!
=
=
x·(1 − x
2
)
(1 − x
2
)
2
− x
2
=
x
(1 − x
2
)
−1
·(1 − x − x
2
)·(1 + x − x
2
)
Мы уже нашли разложение:
1 1 − x − x
2
=
I
a ∗ b
(x)
x
=
Y
n ≥ 1
(1 − x n
)
−(ab)
n
Из него следует:
1 1+x−x
2
=
1 1−(−x)−(−x)
2
=
Y
n ≥ 1
(1−(−x)
n
)
−(ab)
n
=
=
Y
2 \ n ≥ 1
(1 − x n
)
−(ab)
n
·
Y
2 6\ n ≥ 1
(1 + x n
)
−(ab)
n
=
=
Y
2 \ n ≥ 1
(1 − x n
)
−(ab)
n
·
Y
2 6\ n ≥ 1
1 − x
2n
1 − x n
−(ab)
n
=
=
Y
2 6\ n
(1−x n
)
(ab)
n
·
Y
4 \ n
(1−x n
)
−(ab)
n
·
Y
4 6\ n
2
(1−x n
)
−(ab)
n
−(ab)
n/2
45
Отсюда вытекает окончательное выражение b
2
:
(b
2
)
n
=
0 ,
если n ≡ 1 mod 2 2 ,
если n = 2 2·(ab)
n
−(ab)
n/2
, если 2 < n ≡ 2 mod 4 2·(ab)
n
,
если n ≡ 0 mod 4
(b
2
) = (0, 2, 0, 3, 0, 5, 0, 11, 0, 24, 0, 52, 0, 120, 0, 275, . . . ) .
Иных усилий требует обращение последовательностей. На- чн¨
ем с очевидного 0
−1
= 0, которое означает эквивалентность равенств y = x и x = y.
Следующий по простоте случай такой:
([ n = 1 ])
−1
= ([ n = 2 ] − [ n = 1 ]) ,
поскольку равенство y = x/(1−x) равносильно выражению:
x =
y
1 + y
=
y · (1 − y)
1 − y
2
=
y
(1 − y)
−1
· (1 − y
2
)
1 4.7. Пример. Перейд¨
ем к более общей задаче вычисления
(a·[ n = 1 ])
−1
= (a, 0, 0, . . . )
−1
=: (c
1
, c
2
, c
3
, . . . ) = c (a) .
У нас есть два эквивалентных равенства:
y = x · (1 − x)
−a
,
x = y ·
Y
n ≥ 1
(1 − y n
)
−c n
Умножая их, получим тождества:
yx = xy · (1 − x)
−a
·
Y
n ≥ 1
(1 − y n
)
−c n
,
(1 − x)
a
=
Y
n ≥ 1
(1 − y n
)
−c n
,
46
a · ln(1 − x) =
X
n ≥ 1
c n
· ln
1 1 − y n
=
X
n ≥ 1
c n
·
X
k ≥ 1
y nk k
Для удобства записи введ¨ем новое обозначение:
γ
m
(a) = γ
m
=
X
n\m nc n
;
c n
= n
−1
·
X
m\n
µ(n/m) · γ
m
Тогда получим интересное выражение:
a · ln(1 − x) =
X
m ≥ 1
y m
m
· γ
m
=
X
m ≥ 1
γ
m m
·
x m
(1 − x)
am
Это равенство немного упрощается при дифференцировании:
−ax
1 + (a − 1)·x
=
X
m ≥ 1
γ
m
·
x m
(1 − x)
am
(∂)
Мы вычислим показатели γ
m
(a), и на этом пути у нас по- явятся биномиальные коэффициенты:
a· ln(1−x) = −a·
X
k ≥ 1
x k
k
=
X
m ≥ 1
γ
m m
· x m
·
X
s ≥ 0
−am s
(−x)
s
=
=
X
m ≥ 1
X
s ≥ 0
γ
m m
−am s
(−1)
s x
m+s
=
X
k≥1
x k
k
X
m=1
γ
m m
−am k−m
(−1)
k−m
Таким образом, получаем равенства:
−
a k
=
k
X
m=1
γ
m m
·
−am k − m
·(−1)
k−m
, k ≥ 1 .
47
Это бесконечная система линейных уравнений от (γ
m
), оп- редел¨
енная из-за строгой треугольности – главная неизвест- ная γ
k входит в k-ое уравнение с коэффициентом 1/k.
Аналогично, уравнение (∂) равносильно треугольной сис- теме линейных уравнений относительно тех же (γ
m
):
a · (a − 1)
k−1
=
k
X
m=1
γ
m
·
−am k − m
· (−1)
m
, k ≥ 1 .
Из уравнений легко вывести начальные значения γ
m
:
γ
1
= −a , γ
2
= 2a·(2a−1)/2 , γ
3
= −3a·(3a−1)·(3a−2)/6 ,
γ
4
= 4a · (4a − 1) · (4a − 2) · (4a − 3)/24 .
4.8. Гипотеза. Похоже, что неизвестные γ
m имеют вид:
γ
m
= (−1)
m
·
am m
,
m ≥ 1
(Γ)
В силу определ¨
енности вышеуказанных систем линейных уравнений, для доказательства предположения (Γ) достаточ- но обосновать одно из двух эквивалентных тождеств:
k
X
m = 1 1
m
·
am m
·
−am k − m
= (−1)
k−1
·
a k
,
k ≥ 1
(`)
k
X
m = 1
am m
·
−am k − m
= a · (a − 1)
k−1
,
k ≥ 1 .
Преобразуем левые слагаемые (`) – первого из них:
1
m
·
am m
·
−am k − m
=
1
m
·
am·(am−1)· . . . ·(am−m+1)
m!
×