Файл: Учебное пособие ульяновск 2018 msc2010 05 Combinatorics ббк 22. 176 Удк 519. 1 В313 Рецензенты.pdf

87
двойки, и, тем самым, – его тотальную минимальность – оно кратчайшее из разложений n по степеням двоек. Количест- во слагаемых такого разложения называется двоичным весом числа n. Следуя тексту ([10, с. 29, 596]), обозначим его ν (n).
В этой главе мы изучим свойства двоичного веса. Интерес к теме вызван IV разделом книги ([30, с. 172-200]).
Разложение натурального числа по степеням можно изу- чать разными способами. Сначала напомним алгоритм раз- ложения n > 0 в сумму разных степеней двоек.
7.1. Алгоритм.
Возьм¨
ем такое целое K, что выполняются неравенства:
2
K
≤ n ≤ 2
K+1
Ясно, что K = blog
2
(n)c. Полученное 2
K
будет старшей степенью двойки в разложении n. Вычтем его из всех сторон неравенства:
0 ≤ n
0
= n − 2
K
≤ 2
K+1
− 2
K
= 2
K
При n
0
= 0 разложение завершается: n = 2
K
. Если же n
0
> 0, то 2
K
0
– старшая степень двойки в разложении n
0
будет строго меньше 2
K
. В этом случае n
0
< n (и более то- го: n
0
< n/ 2), что да¨ет нам индуктивный шаг разложения.
Количество таких шагов ограничено и равно ν(n).
Алгоритм 7.1 да¨ет экономную рекурсию для вычисления двоичного веса, – она предложена в ([30, с. 173]):
ν (n) = ν (n − 2
blog
2
(n)c
) + 1 ,
ν (0) = 0 .
Арифметическую природу алгоритма и рекурсии проясня- ет полезное утверждение.

88 7.2. Лемма. Следующее уравнение разрешимо только при вещественных неотрицательных a :
x − 2
blog
2
(x)c
= a .
Если a = 0, то x = 2
k
, где k ∈ Z. Если a > 0, то x = a + 2
k
,
где k > blog
2
(a)c.
Доказательство. Заметим, что функция blog
2
(x)c задана только для вещественных положительных x. Поэтому урав- нение может быть совместно лишь при вещественных a.
Представим вещественное x > 0 в двоичном редуцирован- ном виде – без 2-ичного периода 1 в разложении. Целочис- ленный набор m i
может быть конечным, но непустым:
x = 2
m
0
+ 2
m
1
+ . . . ,
m
0
> m
1
> . . . .
Тогда имеются неравенства:
2
m
0
≤ x <
X
k ≤ m
0 2
k
= 2
m
0
+ 1
;
m
0
≤ log
2
(x) < m
0
+ 1 .
Следовательно, blog
2
(x)c = m
0
, и есть оценки:
0 ≤ x − 2
blog
2
(x)c
= x − 2
m
0
= 2
m
1
+ 2
m
2
+ · · · <
< 2
m
1
+1
≤ 2
m
0
≤ x .
Итак, преобразование φ (x) = x − 2
blog
2
(x)c убирает из ре- дуцированной двоичной записи x старший разряд. Простое исследование образа φ доказывает Лемму 7.2.
На ином пути изучения двоичных разложений можно раз- вернуть следующее произведение в степенной ряд:
f (t) =
Y
k ≥ 0 1 + t
2
k
= 1 +
X
n ≥ 1
A(n) · t n

89
И вывести постоянство его коэффициентов: A(n) ≡ 1 . Что докажет единственность разложения натуральных чисел в сумму разных неотрицательных степеней двойки, ведь A(n)
считает количество таких разложений n. Заметим:
f (t) = (1 + t) ·f (t
2
)
⇒
(1 − t) ·f (t) = (1 − t
2
) ·f (t
2
) ;
g(t) := (1 − t) ·f (t) = g(t
2
) = g(t
4
) = . . . = g(t
2
k
) ∀ k ≥ 0 .
Поэтому разложение g(t) в степенной ряд не содержит по- ложительных степеней t:
g(t) = g(0) = 1
⇒
f (t) = (1 − t)
−1
= 1 +
X
n ≥ 1
t n
Равенство f (t) = (1 + t) ·f (t
2
) подсказывает простой алго- ритм двоичного разложения. Для этого запишем:
1 +
X
n ≥ 1
A(n) · t n
= (1 + t) · 1 +
X
s ≥ 1
A(s) · t
2s
=
= 1 +
X
s ≥ 1
A(s) · t
2s
+ t +
X
s ≥ 1
A(s) · t
2s+1
Теперь приравнивая коэффициенты при одинаковых сте- пенях t, получим рекуррентное выражение A(n):
A(1) = 1 ;
A(n) = A(bn/2c) при n > 1 .
Обозначим A(n) – разложение n в сумму разных степеней двойки. Укажем правило и пример построения A(n):
7.3. Рекурсия.
1 : A(1) =“ 1 ” ;
n > 1 – неч¨
етное : A(n) = A(n − 1) + 1 ;
n ≥ 2 – ч¨
етное : A(n) = 2 · A(n/2) .

90 7.4. Пример.
2 : A(2) = 2 · A(1) = 2 · “ 1 ” = “ 2 ” ;
4 : A(4) = 2 · A(2) = 2 · “ 2 ” = “ 2 2
” ;
5 : A(5) = A(4) + 1 = “ 2 2
”+1 = “ 2 2
+ 1 ” ;
10 : A(10) = 2 · A(5) = 2 · “ 2 2
+ 1 ” = “ 2 3
+ 2 ” .
Для разнообразия разбер¨ем задачу, интересную возможны- ми обобщениями. Найти D(n) – количество разложений n в сумму степеней двоек, если каждая степень может повторять- ся не чаще 3-х раз. В этом случае мы получаем:
1 +
X
n ≥ 1
D(n) · t n
=
Y
k ≥ 0 1 + t
2
k
+ t
2 · 2
k
+ t
3 · 2
k
=
=
Y
k ≥ 0 1 − t
4 · 2
k
1 − t
2
k
=
Y
k ≥ 0 1 − t
2
k+2 1 − t
2
k
=
1 1 − t
·
1 1 − t
2
=
=
X
k ≥ 0
t k
·
X
s ≥ 0
t
2s
=
X
k , s ≥ 0
t
2s+k
=
=
X
n ≥ 0
t n
·
bn/2c
X
s = 0 1 =
X
n ≥ 0
bn/2c + 1
· t n
Поэтому D(n) = bn/2c + 1. Но если разложить производя- щую функцию D(n) в сумму простейших дробей:
1 1 − t
·
1 1 − t
2
=
1
(1 − t)
2
·
1 1 + t
=
1/2
(1 − t)
2
+
1/4 1 − t
+
1/4 1 + t
,
то получается выражение иного вида:
D(n) =
n + 1 2
+
1 + (−1)
n
4

91
Последовательность подчиняется рекуррентным правилам:
D(2n + 1) = D(2n) = D(n) + D(n − 1) = n + 1 .
С начальными условиями D(1) = 1, D(2) = 2 они впол- не задают
D(n), n ≥ 1
. И более того, позволяют стро- ить соответствующие двоичные разложения. Для демонстра- ции алгоритма обозначим D(n) – набор разложений n в сум- му степеней двойки с не более, чем тройными повторениями каждой степени. Заметим, что такое разложение неч¨
етного числа содержит одно или три вхождения 1 = 2 0
, а разложе- ние ч¨етного содержит либо две 1, либо не имеет их вообще
– и тогда все степени двойки в разложении строго положи- тельны. По этим признакам D(n) распадается на непересека- ющиеся множества искомых разложений.
7.5. Рекурсия.
1, 2 : D(1) =“ 1 ” ; D(2) =“ 2, 1 + 1 ” ;
n > 1 – неч¨
етное : D(n) = D(n − 1) + 1 ;
n > 2 – ч¨
етное : D(n) = 2·D(n/2) ∪
2·D (n/2)−1+1+1 .
Проясним этот алгоритм на примере.
7.6. Пример.
4 : D(4) = 2 · D(2) ∪
2 · D(1) + 1 + 1 =
= 2·“ 2 , 1 + 1 ” ∪
2·“ 1 ”+ 1 + 1 = “ 2 2
, 2 + 2 , 2 + 1 + 1 ” ;
5 : D(5) = D(4) + 1 = “ 2 2
+ 1 , 2 + 2 + 1 , 2 + 1 + 1 + 1 ” ;
10 : D(10) = 2 · D(5) ∪
2 · D(4) + 1 + 1 =
= “ 2 3
+ 2 , 2 2
+ 2 2
+ 2 , 2 2
+ 2 + 2 + 2 , 2 3
+ 1 + 1 ,
2 2
+ 2 2
+ 1 + 1 , 2 2
+ 2 + 2 + 1 + 1 ” .

92 7.7. Замечание. Алгоритм 7.1 предлагает последователь- ное разложение натурального числа в сумму различных сте- пеней двойки – от старших степеней к младшим. Вместе с тем, известна процедура, указывающая – входит ли в иско- мое разложение n конкретная степень двойки или нет.
7.8. Определение. Для всех k ≥ 0 зададим целые числа:
a k
(n) = 2
k
· bn/ 2
k c .
В частности:
a
0
(n) = n , a
1
(n) = 2bn/ 2c, . . . , a k
(n) = 0 , при k > log
2
(n) .
Докажем, что последовательность a k
(n)
не раст¨ет по k :
a k
(n) − a k+1
(n) = 2
k
· bn/ 2
k c − 2
k+1
· bn/ 2
k+1
c =
= 2
k
· bn/ 2
k c − 2 · bn/ 2
k+1
c
= 2
k
·
j n
2
k
− 2 · bn/ 2
k+1
c k
=
= 2
k
·
j
2 ·

n
2
k+1
−
j n
2
k+1
kk
≤ 2
k
·

2 ·

n
2
k+1
−
j n
2
k+1
k
=
= 2
k+1
·

n
2
k+1
−
j n
2
k+1
k
< 2
k+1
Таким образом, имеем оценки:
0 ≤ 2
−k
· a k
(n) − a k+1
(n)
=
j
2 ·

n
2
k+1
−
j n
2
k+1
kk
< 2 .
Из целочисленности предпоследнего выражения следует:
ε
k
(n) := 2
−k
· a k
(n) − a k+1
(n)
∈ {0, 1} ;
a k
(n) − a k+1
(n) = ε
k
(n) · 2
k
Из этого, в итоге, вытекает двоичное разложение n:
n = a
0
(n) = a
0
(n) − a
1
(n)
+ a
1
(n) − a
2
(n)
+ . . . =

93
=
X
k ≥ 0
a k
(n) − a k+1
(n)
=
blog
2
(n)c
X
k = 0
a k
(n) − a k+1
(n)
=
=
blog
2
(n)c
X
k = 0
ε
k
(n) · 2
k
= ε
blog
2
(n)c
(n). . . ε
2
(n)ε
1
(n)ε
0
(n)
(2)
Вспомним, что количество ненулевых слагаемых двоично- го разложения n мы называем двоичным весом – ν(n). Сейчас мы готовы найти его вид (обобщения см. [16, с. 7-12]).
7.9. Теорема (формулы двоичного веса).
ν(n) = n −
X
k ≥ 1
n/2
k
=
X
k ≥ 1
n/2
k
= n − ord
2
(n!) ;
Доказательство. Воспользуемся формулой двоичного раз- ложения (учт¨
ем, что начальные значения k ≤ blog
2
(n)c):
ν(n) =
X
k ≥ 0
ε
k
(n) =
X
k ≥ 0 2
−k
· a k
(n) − a k + 1
(n)
=
=
X
k ≥ 0 2
−k
· a k
(n) −
X
k ≥ 0 2
−k
· a k + 1
(n) =
=
X
k ≥ 0 2
−k
· a k
(n) − 2 ·
X
k ≥ 0 2
−(k + 1)
· a k + 1
(n) =
=
X
k ≥ 0 2
−k
· a k
(n) − 2 ·
X
k ≥ 1 2
−k
· a k
(n) =
= 2 0
· a
0
(n) −
X
k ≥ 1 2
−k
· a k
(n) =
= n −
X
k ≥ 1
bn/ 2
k c = n −
blog
2
(n)c
X
k = 1
bn/ 2
k c .

94
Далее продолжим равенство, представив n суммой геомет- рической прогрессии с множителем 1/ 2:
ν(n) =
∞
X
k = 1
n/ 2
k
−
blog
2
(n)c
X
k = 1
bn/ 2
k c =
=
∞
X
k = 1

n
2
k
−
j n
2
k k
=
X
k ≥ 1
n/ 2
k
Эту формулу можно вывести из более простых соображе- ний, использовав равенство ν(2
k
) = 1. Усиление е¨е упомянуто в ([10, с. 596, упр. 6.37]). Последнее выражение можно свер- нуть к конечной сумме:
ν(n) =
blog
2
(n)c
X
k = 1
n/ 2
k
+
X
k > blog
2
(n)c
n/ 2
k
=
=
blog
2
(n)c
X
k = 1
n/2
k
+
X
k > blog
2
(n)c n/2
k
=
blog
2
(n)c
X
k = 1
n/2
k
+
n
2
blog
2
(n)c
Завершающее равенство теоремы открыл А.-М. Лежандр.
Для доказательства найд¨ем количество 1 ≤ m ≤ n, крат- ных 2
k
, но не 2
k + 1
. Оно равно
n/2
k
− n/2
k + 1
. Поэтому кратность двойки в n! выражается формулой:
ord
2
(n!) =
X
k ≥ 1
k ·
n/2
k
− n/2
k + 1
=
=
X
k ≥ 1
k ·
n/2
k
−
X
k ≥ 1
k ·
n/2
k + 1
=
= bn/2c +
X
k ≥ 2
k ·
n/2
k
−
X
k ≥ 2
(k − 1) ·
n/2
k
=
= bn/2c +
X
k ≥ 2
n/2
k
=
X
k ≥ 1
n/2
k
.

95
Следовательно, при n ≥ 0 получаем искомое равенство:
ν(n) = n −
X
k ≥ 1
n/ 2
k
= n − ord
2
(n!) .
7.10. Следствие. При n, m ≥ 1 есть соотношения:
ν (n) − ν (n − 1) = 1 − ord
2
(n) ;
ν (n) + ν (m) ≥ ν (n + m) ;
ν (n) · ν (m) ≥ ν (n · m) .
Доказательство. Рекурсия вытекает из предыдущего:
ν(n) − ν(n−1) = n − ord
2
(n!) − (n−1) − ord
2
(n−1)!
=
= 1 − ord
2
(n! / (n − 1)!) = 1 − ord
2
(n) .
Аналогично получаем неравенство:
ν(n) + ν(m) − ν(n + m) = n − ord
2
(n!) +
+ m − ord
2
(m!) − n + m − ord
2
(n + m)!
=
= ord
2
(n+m)!
− ord
2
(n!) − ord
2
(m!) = ord
2

n+m n


≥ 0 .
Для вывода мультипликативного неравенства разложим m в сумму разных степеней двойки, воспользуемся аддитивным неравенством и очевидным тождеством ν n · 2
k
= ν (n):
m = 2
k
1
+ · · · + 2
k d
, где 0 ≤ k
1
< . . . < k d
, ν (m) = d ;
ν (n · m) = ν n · 2
k
1
+ . . . + n · 2
k d
≤
≤ ν n · 2
k
1
+ · · · + ν n · 2
k d
= ν (n) + . . . + ν (n)
|
{z
}
d
=
= ν (n) · d = ν (n) · ν (m) .

96
Другое доказательство этого неравенства да¨ет минималь- ность длины разложения в сумму разных степеней двоек.
Действительно, произведение суммы ν (n) степеней двоек раз- ложения n на сумму ν (m) степеней разложения m да¨ет сумму
ν (n) · ν (m) степеней двоек разложения n · m , – но, возможно,
с повторами. Сливая одинаковые степени, получим ν (n · m)
различных степеней двоек. Поэтому ν (n · m) ≤ ν (n) · ν (m).
Прич¨
ем, неравенство становится равенством при отсутствии повторов в вышеупомянутой сумме из ν (n) · ν (m) степеней.
7.11. Замечание. Равенство ν(2
k
− 1) = k свидетельствует о неограниченности последовательности ν(n)
. Осмысленно дополнив е¨
е – ν(0) = 0, укажем начальные значения:
01121223122323341223233423343445122323342 . . .
Они выглядят несколько запутанно. И это не случайно.
Рассмотрим е¨
е остатки от деления на 2:
01101001100101101001011001101001100101100 . . .
Это бесконечное слово Туэ-Морса. Оно не содержит по- следовательных троекратных повторений своих частей и да- же сильнобескубно (см. [38, с. 229] или [27, с. 11-16]). Сле- довательно, и последовательность двоичных весов обладает этими же свойствами.
7.12. Определение. Двоичным весам можно сопоставить разные производящие функции. Одна из них такова:
N (t, z) :=
X
n ≥ 0
z
ν (n)
· t n
=
Y
k ≥ 0

1 + z · t
2
k

97
Она участвует во многих тождествах. Так, через не¨е выра- жаются производящие функции этой главы:
N (t
2
, −1)
N (t, −1)
= N (t, 1) =
Y
k ≥ 0

1 + t
2
k

=
X
n ≥ 0
t n
=
1 1 − t
;
N (t
4
, −1)
N (t, −1)
= 1 +
X
n ≥ 1
D(n) · t n
=
1 1 − t
·
1 1 − t
2
Перемена знаков в степенном разложении N (t, −1) совпа- дает с чередованием 0 и 1 в последовательности Туэ-Морса:
N (t, −1) =
Y
k ≥ 0

1 − t
2
k

=
X
n ≥ 0
(−1)
ν (n)
· t n
Ряд N (t, −1)

−1
считает количество представлений n сум- мой степеней двоек без ограничений на повторения.
Из формулы Теоремы 7.9. ord
2
(n!) = n − ν(n) вытекают интересные разложения:
N (t, t
−1
) =
Y
k ≥ 0

1 + t
2
k
−1

=
X
n ≥ 0
t n − ν (n)
=
=
X
n ≥ 0
t ord
2
n!

= 2 ·
X
m ≥ 0
t ord
2
(2m)!

=
= 2 · 1 + t + t
3
+ t
4
+ t
7
+ t
8
+ t
10
+ t
11
+ t
15
+ . . .
;
N (t, t) =
Y
k ≥ 0

1 + t
2
k
+1

=
X
n ≥ 0
t n + ν (n)
=
=
X
n ≥ 0
t
2n − ord
2
n!

= 1 + t
2
+ t
3
+ 2t
5
+ t
7
+ t
8
+ . . .
Функцию N (t, z) можно разложить по степеням z:
N (t, z) =
X
s ≥ 0
z s
· T
s
(t) ,
где
T
s
(t) =
X
n ≥ 0; ν (n) = s t
n

98
В частности, T
< 0
(t) = 0, T
0
(t) = 1, T
1
(t) =
P
k ≥ 0
t
2
k
–
и этот ряд в комплексной плоскости определяет функцию с областью голоморфности |z| < 1 .
7.13. Лемма. Ряды T
s
(t) подчиняются соотношениям:
T
s
(t) = T
s
(t
2
) + t · T
s−1
(t
2
) ;
T
1
(t) =
X
k ≥ 0
µ(2k + 1) ·
t
2k+1 1 − t
2k+1
=
=
X
m ≥ 1 2 ord
2
(m)· µ

m
2 ord
2
(m)

·
t m
1 + t m
Доказательство. Воспользуемся тождеством:
N (t, z) = (1 + zt) ·
Y
k ≥ 0

1 + z · t
2 · 2
k

= (1 + zt) · N (t
2
, z) ;
X
s ≥ 0
z s
· T
s
(t) = (1 + zt) ·
X
s ≥ 0
z s
· T
s
(t
2
) =
=
X
s ≥ 0
z s
· T
s
(t
2
) +
X
s ≥ 0
z s+1
· t · T
s
(t
2
) =
= 1 +
X
s ≥ 1
z s
· T
s
(t
2
) + t · T
s−1
(t
2
)
.
Сравнение степенных рядов от t при одинаковых степе- нях z да¨
ет первое из соотношений. В частности, получаем рекурсию, определяющую T
1
(t):
T
1
(t) = t + T
1
(t
2
) = t + t
2
+ T
1
(t
4
) = t + t
2
+ t
4
+ T
1
(t
8
) = . . .
В начале 4 главы упоминалась функция М¨
ебиуса µ(k). Е¨
е свойства разобраны в книге ([10], с. 160-161). Определим ряд f (t) = t + o(t):
f (t) :=
X
k ≥ 0
µ(2k + 1) ·
t
2k+1 1 − t
2k+1

99
Из определения функции М¨ебиуса получим равенство:
X
n ≥ 1
µ(n) ·
t n
1 − t n
=
X
n ≥ 1
µ(n) ·
X
m ≥ 1
t nm
=
=
X
u ≥ 1
t u
·
X
n \ u
µ(n) = t .
Заметим, что это равенство так же получается из логариф- мической производной известного тождества:
e t
=
Y
n ≥ 1
(1 − t n
)
−µ(n)/n
Разложение t преобразуем с уч¨етом µ(n) = 0, при 4 \ n:
X
n ≥ 1
µ(n) ·
t n
1 − t n
=
X
2 6\ n ≥ 1

µ(n) ·
t n
1 − t n
+ µ(2n) ·
t
2n
1 − t
2n

=
=
X
2 6\ n ≥ 1

µ(n) ·
t n
1 − t n
− µ(n) ·
t
2n
1 − t
2n

= f (t) − f (t
2
) .
Так как ряд f (t) связан той же рекурсией, что и T
1
(t) , –
они совпадают. Чтобы привести T
1
(t) к ряду Ламберта про- тивоположного вида, воспользуемся арифметической связью базовых функций L
+
(t) и L
−
(t), вытекающей из логарифми- ческой производной равенства 1 + t n
= (1 − t
2n
)/(1 − t n
):
t
1 + t
−
t
1 − t
= −2 ·
t
2 1 − t
2
;
t
1 + t
=
t
1 − t
− 2 ·
t
2 1 − t
2
,
t n
1 + t n
=
t n
1 − t n
− 2 ·
t
2n
1 − t
2n
Для обращения предыдущих равенств используем единст- венность разложения в ряды Ламберта L
+
(t) и L
−
(t):
t
1 − t
=
X
n ≥ 1
a n
·
t n
1 + t n
=
X
n ≥ 1
a n
·

t n
1 − t n
− 2 ·
t
2n
1 − t
2n

=

100
=
X
n ≥ 1
a n
·
t n
1 − t n
−
X
n ≥ 1 2 · a n
·
t
2n
1 − t
2n
=
=
X
2 6\ n ≥ 1
a n
·
t n
1 − t n
−
X
2 \ n ≥ 1
(a n
− 2 · a n/2
) ·
t n
1 − t n
Поэтому для неч¨
етных индексов n: a n
= [ n = 1 ] , а для ч¨
етных: a n
= 2 · a n/2
. Следовательно, a n
= n · [ n = 2
d
, d ≥ 0 ] ,
и мы получаем выражения:
t
1 − t
=
X
d ≥ 0 2
d
·
t
2
d
1 + t
2
d
;
t n
1 − t n
=
X
d ≥ 0 2
d
·
t
2
d
· n
1 + t
2
d
· n
Снова отметим, что это равенство можно вывести из лога- рифмической производной полученного ранее тождества:
(1 − t)
−1
=
Y
n ≥ 0 1 + t
2
n
.
Теперь несложно пересчитать T
1
(t) :
T
1
(t) =
X
2 6\ n ≥ 1
µ(n) ·
t n
1 − t n
=
X
2 6\ n ≥ 1
µ(n) ·
X
d ≥ 0 2
d
·
t
2
d
· n
1 + t
2
d
· n
=
=
X
m ≥ 1
t m
1 + t m
·
X
d ≥ 0 2
d
· µ(m/2
d
)·[ 2
d
\m & m/2
d
– неч¨
етное ] =
=
X
m ≥ 1 2 ord
2
(m)· µ

m
2 ord
2
(m)

·
t m
1 + t m
И, тем самым, Лемма 7.13 полностью доказана.
7.14. Замечание. Из указанного выше правила:
N (t, z) = (1 + zt) · N (t
2
, z)