В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 6
Текст из файла (страница 6)
. . , pr — все простые числа, не превосходящие n. Показать, что число простых чисел p таких,r√что n < p 6 n, равно n − 1 + ∑ (−1)k Sk , где суммаk=1Sk = ∑берется по всевозможнымостальные равны 0.rknpα1 1 · · · pαr rнаборам показателей α1 , . . . , αr , в которых ровно k из показателей равны 1, а(f) Найти число простых чисел, не превосходящих 100.1.2Производящие функцииРазбиения множества. Пусть X — некоторое конечное множество, |X| = n, на котором задано разбиение X = X1 ∪X2 ∪ · · · ∪ Xk , то есть ∀ i = 1, k ⇒ Xi 6= ∅ & i 6= j ⇒ Xi ∩ X j = ∅.
Заметим, что порядок блоков и элементов в блоке не важен.Определение 1.2.1. Числом Стирлинга второго рода S (n, k) для n > 1, k > 1 называется число разбиений nэлементного множества на k блоков.В качестве примера рассмотрим случай n = 3. Заметим предварительно, что разбиения можно упорядочить: разбиение D2 предшествует разбиению D1 (D2 4 D1 ), если D2 можно получить из D1 , разбивая блоки последнего на подблоки.Иными словами, любой блок из D2 содержится лишь в одном блоке D1 . Это отношение можно рассматривать какуточнение эквивалентности: из эквивалентности по разбиению D2 следует эквивалентность по разбиению D1 , но ненаоборот.
Итак, диаграмма Хассе частично упорядоченного множества разбиений выглядит следующим образом:{{1, 2, 3}}HHHHH{{1, 2} , {3}}{{2, 3} , {1}}{{3, 1} , {2}}HHHHH{{1} , {2} , {3}}Отсюда видно, что S (3, 1) = 1, S (3, 2) = 3, S (3, 3) = 1.Вообще, очевидны следующие тривиальные равенства:S (n, n) = 1 (n > 1) , S (n, 1) = 1 (n > 1) , S (n, k) = 0 (k > n > 1) .Опираясь на эти начальные условия, найдем рекуррентное соотношение для чисел Стирлинга второго рода, доказавследующую формулу:S (n, k) = S (n − 1, k − 1) + k · S (n − 1, k) .(1.16) Док-во. Действительно, выделим в n-элементном множестве последний элемент и рассмотрим всевозможные разбиения оставшегося множества. Возможны два случая:1.
последний элемент составляет отдельный блок. Но всего таких разбиений столько, сколько существует разбиений оставшегося (n − 1)-элементного множества на k − 1 блоков.2. Последний элемент не составляет отдельного блока. Но тогда он принадлежит одному из k блоков разбиения(n − 1)-элементного оставшегося множества.Поскольку эти два случая несовместны, получаем (1.16).191.2. ПРОИЗВОДЯЩИЕ ФУНКЦИИТаким образом, числа Стирлинга второго рода могут задаваться следующей таблицей:b kn b01234567010000000......10111111120013715316330001625903014500000000101016515350 1406000000121...........................×k700000001n−1, n−1,k−1kn,k...Эти числа растут очень быстро.
Так, например, S (10, 5) = 42525. Начальные условия могут задаваться по-другому: S (0, 0) = 1,S (n, n) = 1, n > 0,S (n, 0) = 0, n > 1;или S (0, 0) = 1,S (0, k) = 0, k > 1S (n, 0) = 0, n > 1.В качестве следующего примера найдем все разбиения четырехэлементного множества {1, 2, 3, 4}:D1,1 = {1, 2, 3, 4} ,D2,1 = {1} {2, 3, 4} ,D2,2 = {2} {1, 3, 4} ,D2,3 = {3} {1, 2, 4} ,D2,4 = {4} {1, 2, 3} ,D2,5 = {1, 2} {3, 4} ,D2,6 = {1, 3} {2, 4} ,D2,7 = {1, 4} {2, 3} ,D3,1 = {1} {2} {3, 4} ,D3,2 = {1} {3} {2, 4} ,D3,3 = {1} {4} {2, 3} ,D3,4 = {2} {3} {1, 4} ,D3,5 = {2} {4} {1, 3} ,D3,6 = {3} {4} {1, 2} ,D4,1 = {1} {2} {3} {4} .Диаграмма Хассе этого частичного упорядоченного множества будет иметь следующий вид:`{1, 2, 3, 4}{2, 3, 4}`{1, 3, 4}{3, 4}``{1, 2, 4}{2, 4}``{1, 2, 3}{2, 3}``` {1, 2}` {1, 4}``{1, 3}` {1, 3}{1, 4}`` {1, 2}{1} {2} {3} {4}Теорема 1.3.
Для k > 2 справедливо следующее соотношение:n−1 n−1S (n, k) = ∑S (i, k − 1) .ii=k−1(1.17)20ГЛАВА 1. КОМБИНАТОРИКА Док-во. Выделяем последний элемент и объявляем его уникальным.Затем, для каждого j = 0, n − k выделяем средиоставшихся элементов блок размера j (это можно сделать n−1способами)и присоединяем уникальный элемент этоjму блоку. После этого (для каждого j) рассматриваем все возможные разбиения оставшегося (n − j − 1)-элементногомножества S (n − j − 1, k − 1). Ввиду уникальности последнего элемента и одного из блоков все вышеописанные ситуации несовместны, то есть перебирают различные разбиения.
Таким образом,n−k n−1S (n, k) = ∑S (n − j − 1, k − 1) .jj=0Выполняя формальную замену переменной i = n − j − 1, получаемn−1 n−1 n−1n−1S (n, k) = ∑S (i, k − 1) = ∑S (i, k − 1) ,ii=k−1 n − i − 1i=k−1что и требовалось доказать.Заметим, что равенство 1.17 не может использоваться для корректного задания чисел Стирлинга второго рода.Обозначим для разбиения n-элементного множества на k блоков для i = 1, n через ki > 0 число блоков, содержащихi элементов. При этомn∑ iki = n,i=1n∑ ki = k.i=1Обозначим за B (n; k1 , . .
. , kn ) число разбиений n-элементного множества, содержащих ki блоков из i элементов дляi = 1, n. При условиях ∑ni=1 iki = n, ∑ni=1 ki = kB (n; k1 , . . . , kn ) =n!k1 ! · · · kn ! (1!)k1 . . . (n!)kn.Действительно, раскидываем n элементам по n позициям.[. . . ] . . . [. . . ] [. . . ] . . . [. . . ] .
. . [. . . ] . . . [. . . ]| {z } | {z } | {z }knkn−1k1Это можно сделать n! различными способами. Затем отождествляем порядок блоков внутри групп блоков одного размера и отождествляем порядок элементов в каждом блоке. Очевидно, при этом получается требуемое число. Очевидно,что согласно определениюS (n, k) = ∑ B (n; k1 , . .
. , kn ) .n∑ iki =ni=1Определение 1.2.2. Числом Белла Bn называется число всевозможных разбиений n-элементного множества на блоки:∞Bn =∑ S (n, k) ,B0 = 1.k=0В терминах диаграмм Хассе частично упорядоченного множества разбиений число Белла равно числу вершин вдиаграмме.Теорема 1.4. Для чисел Белла выполняется следующее равенство:n nBn+1 = ∑Bi .i=0 i(1.18) Док-во. Действительно, выбираем последний из n + 1 элементов исходного множества и называем его особым.
Длялюбого i = 0, n рассматриваем всевозможные различные блоки размера i оставшегося n-элементного множества и присоединяем к каждому из них по очереди особый элемент. Для оставшихся n − i элементов рассматриваем их всевозможные разбиения. Заметим, что таким образом перебираются различные разбиения ввиду различности выбираемыхблоков среди первых n неособых элементов. Далее, для разных i будут перебираться также все различные разбиения, так как в них особый элемент принадлежит блокам разных размеров. Таким образом, доказана справедливость(1.18).Заметим, что из симметричности биномиальных коэффициентов следуетn n nnBn+1 = ∑Bn− j = ∑Bi .jj=0i=0 i211.2.
ПРОИЗВОДЯЩИЕ ФУНКЦИИЧисла Белла растут быстрей чисел Стирлинга второго рода: так, например, B20 = 51724158235372.Рассмотрим два базиса полиномов над некоторым полем: стандартный1, x, x2 , . . . , xn , . . .и базис из убывающих факториалов[x]0 , [x]1 , [x]2 , . . . , [x]n , . . .Теорема 1.5. Числа Стирлинга второго рода суть коэффициенты перехода от второго базиса к первому:xn =n∑ S (n, k) [x]k .(1.19)k=00 Док-во. Докажем это по индукции.
Для n = 0 равенство (1.19) превращается в очевидное: 1 = x0 = ∑ S (0, k) [x]k =k=0S (0, 0) [x]0 = 1. Докажем индуктивный переход. Рассмотрим для этого конечные множества A и B с мощностями соответственно |A| = n ∈ N и |B| = x ∈ N, x > n. Рассматриваем далее всевозможные отображения f : A → B. Их число равноxn .ABi1 , . . . , iknkxВ то же время каждое отображение f с областью значений D f = {i1 , . .
. , ik } ⊆ B, |Ds | = k можно единственным образомпредставить следующим образом: выбираем какие-то k различных элементов множества B ( kx способов) и разбиениемножества A на k блоков (S (n, k) способов) и рассматриваем все взаимно однозначные отображения множества блоковна D f (их число — k!). При этом функция f будет очевидным образом всюду определена. Далее заметим, что разным k,разным разбиениям A на k блоков, разным биекциям разбиений A на D f соответствуют разные функции, отображающиеA в B. Таким образом,nx x[x]xxn = ∑(1.20)k! · S (n, k) = ∑ k k! · S (n, k) = ∑ S (n, k) [x]k ,k=0k=1 kk=1 k!поскольку S (n, 0) = 0, n > 1. Равенство (1.20) справедливо для всех натуральных n и k. Теперь заметим, что если дваполинома равны во всех целочисленных точках, то они равны тождественно на всей числовой оси.Определение 1.2.3.
Числом Стирлинга первого рода s (n, k) называется коэффициент перехода от стандартногобазиса полиномов к базису из убывающих факториалов:n[x]n =∑ s (n, k) xk .k=0Очевидно, s (0, 0) = 1, s (n, 0) = 1, n > 1. Также понятно, что s (n, n) = 1, ∀ n ∈ N, s (n, k) = 0, k > n, так как коэффициенты при любых равных степенях, в том числе и при старшей, у тождественно равных полиномов должны совпадать.Запишем определение числа Стирлинга первого рода:n−1[x]n = [x]n−1 (x − n + 1) =∑ s (n − 1, k) · x!kn(x − n + 1) =k=0∑ s (n, k) xk .k=0Приравнивая коэффициенты при равных степенях в последнем равенстве, получаем тождество, которое может служитьрекуррентным определением чисел Стирлинга первого рода:s (n, k) = s (n − 1, k − 1) − (n − 1) · s (n − 1, k) .Видно, что если n и k одной четности, то s (n, k) > 0, если же n и k разной четности, что s (n, k) < 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
