Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Перестановки без единичных циклов

Читайте также:
  1. Глава 12 Под треск мотоциклов
  2. Глава 12. Признание циклов духовной жизни
  3. Глава 12. Признание циклов духовной жизни.
  4. Голова циклової комісії__________________
  5. Значение рыночных циклов при выборе периода расчета
  6. Использование циклов for
  7. ИСПОЛЬЗОВАНИЕ ЦИКЛОВ В ТОРГОВЛЕ
  8. История как наука об уникальных и единичных явлениях
  9. История как наука об уникальных и единичных явлениях – с. 25-28
  10. Классификация циклов

Каково число перестановок из n элементов, каждая из которых состоит из k циклов, отличных от единичных.

Ясно, что ответ на этот вопрос по самому определению функции Сn дается коэффициентом при tk в выражении для Сn(0, t,…, t), или для краткости dn(t). На основании соотношения (3а)

exp(ud(t))= = exp(t(u2/2+u3/3+…) =(1-u)-t exp(-tu) (5)

откуда, сравнивая с (4), получаем

dn(t)= Cn-k(t)(-t)k, (6)

где C0(t)=1, Cn(t)=t(t+1)…(t+n-1), n>0, как и ранее.

Тогда если

dn(t)= ,

то соотношение для коэффициентов, вытекающее из (6), окажется следующее:

d(n,k)= (-1)j C(n-j,k-j) (7)

Ввиду (7) числа d(n,k) называются присоединенными числами Стирлинга первого рода. Следует отметить, что соотношением, двойственным соотношению (6), полученным умножением (5) на etu и приравниванием коэффициентов при un является

Cn(t)= dn-j(t)(t)j.

Последний результат соответствует любопытному представлению чисел Стирлинга

С(n,k)= (-1)j d(n-j,k-j). (8)

Теперь полученный ответ формально является полным, однако существуют более простые зависимости. Так путем дифференцирования (5) по u получаем [ при обычном условии d(t)n≡dn(t)], что

d(t)exp(ud(t))=−t exp(ud(t))+t(1−u)-1exp(ud(t)) (9)

или

(1−u)d(t)exp(ud(t))=tu exp(ud(t)).

Это соответствует соотношению

dn+1(t)=n dn(t)+ntdn-1(t), (10)

что в свою очередь соответствует простому рекуррентному соотношению

d(n+1,k)=nd(n,k) +nd(n-1,k-1), (11)

которое также может быть получено простым комбинаторным рассуждением.

 

Разбиение чисел. [2]

Пусть n – натуральное число и n=b1+b2+…+bk, где k, b1,b2,…,bk>0, при этом будем считать суммы эквивалентными, если они отличаются только порядком слагаемых. Класс эквивалентных сумм можно представить однозначно последовательностью a1,a2,…,ak, где a1≥a2≥…≥ak, и числа a1,a2,…,ak являются числами b1,b2,…,bk, упорядоченными по невозрастанию. Каждую такую последовательность a1,a2,…,ak будем называть разбиением числа n на k слагаемых.

Замечание. Если в сумме b1+b2+…+bk порядок слагаемых считается существенным, то такие представления числа n обычно называются композицией числа n на k слагаемых.

Число разбиений числа n на k слагаемых будем обозначать P(n,k), а число всех разбиений числа n (на произвольное число слагаемых) – через P(n). Очевидно,

P(n)= , n>0.

Положим, P(0,0)=P(0)=1.

Теорема 1. P(n,k) равно числу разбиений числа n c наибольшим слагаемым равным k.

Доказательство.

Рассмотрим способ представления разбиения числа в виде диаграмм Ферреса (Феррера):

Она состоит для разбиения n= a1+a2+…+ak из k строк, i строка содержит ai точек.

 

 

Пример 16=6+4+4+2

 

· · · · · · · · · ·

· · · · · · · ·

· · · · · · · сопряженное разбиение

· · · · ·

·

·

Каждому разбиению числа n однозначно соответствует сопряженное разбиение этого числа, которое получается транспонированием диаграммы Ферреса. Отсюда следует, что транспонирование диаграммы Ферреса определяет взаимно однозначное соответствие между разбиениями числа n на k слагаемых и разбиением числа n с наибольшим слагаемым, равным k.

 

Теорема 2. Число разбиений числа n на попарно различные слагаемые равно числу разбиений числа n на нечетные слагаемые.

 

Доказательство (соответствие Глейшера).

 

Установим взаимно однозначное соответствие между разбиениями, о которых идет речь в теореме.

Пусть n разбито на нечетные слагаемые b1,b2,…,bp, где bi появляется в разбиении ri раз, 1≤i≤p. Положим ri= … (q1>q2>….).

Произведем замену ri слагаемых bi на попарно различные слагаемые

bi bi

т. е.

ri bi= bi bi …,

 

Повторяя эту замену для каждого i, 1≤i≤p, и упорядочивая слагаемые по невозрастанию, получаем в результате разбиение числа n на попарно различные слагаемые. (Здесь использована теорема об однозначном представлении каждого натурального числа в виде произведения нечетного числа на степень числа два.)

Пример.

26=7+5+5+3+3+1+1+1: 7·20+5·21+3·21+1·(21+20)=7+10+6+2+1=10+7+6+2=1

И обратно,

Пусть n=b1+b2+…+bk, где 0 <bk,…<b1, тогда bi= p·2q, 1≤i≤p.

Заменяем каждое bi на 2q слагаемых p, затем упорядочиваем по невозрастанию, получаем разбиение n на сумму нечетных слагаемых.

Таким образом, описанное преобразование определяет взаимно однозначное соответствие между разбиениями на нечетные слагаемые и разбиениями на попарно различные слагаемые.

Теорема 3. Число разбиений числа n, в котором ни одно из слагаемых не превосходит k, равно числу разбиений числа n+k на k слагаемых, т. е. P(n+k,k).

 

Доказательство.

Пусть δ – разбиение числа n, в котором ни одно из слагаемых не превосходит k, a δ′ сопряженное с δ, тогда δ′ содержит не более k слагаемых. Пусть δ′=(b1,b2,…, ), k′≤k, тогда разбиение (k,b1,b2,…, ) является разбиением числа n+k ровно на k слагаемых. Заметим, что (k,b1,b2,…, ) определяется однозначно через δ.

Пусть ε= (b1,b2,…,bk) разбиение n+k на k слагаемых, а ε′ – разбиение сопряженное с ε′. Пусть ε′=(k,b1,b2,…, ), тогда (b1,b2,…, ), разбиение числа n, при этом (b1,b2,…, ) определяется однозначно. Теорема доказана!

 

Теорема 4. Число разбиений числа а–с равно с b–1 частями, не превосходящими с, равно числу разбиений числа a–b с c–1 – частями, не превосходящими b.

Доказательство.

Рассмотрим графическое представление типичного разбиения первого типа и преобразуем это разбиение следующим образом: добавим новую строку из c точек, затем удалим первый столбец (который теперь имеет b точек) и произведем сопряжение полученного разбиения:

сразу видно, что такое последовательное преобразование представляет собой взаимно однозначное соответствие между этими двумя типами разбиений и, следовательно, доказывает теорему.

В качестве примера рассмотрим случай a=14, b=5, c=4:

4+4+1+1→3+3+3

4+3+2+1→4+3+2

4+2+2+2→5+2+2

3+3+3+1→4+4+3

3+3+3+2→5+3+1

 

Введем производящие функции, которые применяются в некоторых задачах, связанных с разбиением чисел.

Пусть n=a1+a2+…+ak, тогда <λ1, λ2,…, λn>, где λi=|{(j:aj=i)&(1≤j≤k)}|. Имеем, очевидно,

,

и каждая последовательность<λ1, λ2,…, λn>, (λ1, λ2,…, λn≥0), отвечающая этому условию однозначно определяет разбиение числа n, содержащее λi слагаемых равных i, 1≤j≤n.

Обозначим, Ph(n) – число разбиений числа n на слагаемые не превышающие h, а P(n) определяет число всех разбиений числа n.

Теорема 4. Производящая функция для последовательности Ph(0), Ph(1), Ph(2),… равна

(1+t+t2+t3+…)(1+t2+t4+t6+…)…(1+th+t2h+t3h+…)=(1-t)-1(1-t2)-1…(1-th)-1.

Доказательство.

Согласно определению произведения h рядов с правой стороны является суммой слагаемых вида · ·…· i – номер члена выбранного из i-го ряда). Таким образом, коэффициент при tn равен числу последовательностей <λ1, λ2,…, λn>, таких что , а, следовательно, в соответствие с предыдущими замечаниями он равен Ph(n).

Аналогичным образом доказывается следующая теорема:

Теорема 6. Производящая функция для последовательности P(0), P(1), P(2),… равна

(1+t+t2+t3+…)(1+t2+t4+t6+…)…(1+th+t2h+t3h+…)…= 1-th)-1.

Замечание. В этом месте следовало бы строго определить ряд, являющийся бесконечным произведением рядов F1(t)·F2(t)·F3(t)·…. Обозначим In(t) “частичное” произведение F1(t)·F2(t)·…·Fn(t) и через pn – наименьшую ненулевую степень с ненулевым коэффициентом в Fn(t). Положим, что коэффициент при нулевой степени в каждом из рядов Fn(t) равен единице, и что pn=∞ (оба эти условия выполнены в условии теоремы). Тогда коэффициент при tn в Im(t) один и тот же для всех m, больших некоторого числа mn. Именно этот коэффициент принимается как коэффициент при tn в ряде, определенном бесконечным произведением F1(t)·F2(t)·F3(t)·….

 

Техника производящих функций позволяет провести простые доказательства некоторых свойств разбиений числа. Приведем в качестве примера другое доказательство теоремы 2.

Пусть R(t) – производящая функция для разбиений на попарно различные слагаемые, тогда

R(t)=(1+t)(1+t2)(1+t3) ·…·(1+tk)·…,

а производящая функция для разбиений на нечетные слагаемые равна

N(t)=(1-t)-1(1-t3)-1·…·(1-t2k-1)-1·….

(заметим, что оба произведения абсолютно сходящиеся при 0<t<1)

Пользуясь зависимостью 1+tk=(1-t2k)/(1-tk), получаем

R(t)= …= …=N(t)

 

Теорема 7. Пусть Pe(D,n) (соответственно Pо(D,n)) число разбиений n на четное (соответственно нечетное) число различных частей[3]. Тогда

Pe(D,n)− Pо(D,n)=

Доказательство.

Мы попытаемся установить взаимно однозначное соответствие между разбиениями, перечисляемыми функцией Pe(D,n), и разбиениями, перечисляемыми функцией Pо(D,n). Для большинства целых n наша попытка увенчается успехом; однако, если n является одним из пятиугольных чисел , то это и составит единственный исключительный случай.

Введем два параметра разбиения α= (a1,a2,…,ak): s(α)=ak (наименьшая часть разбиения α) и σ(α) – наибольшее j, для которого aj=a1-j+1 (при αÎ D – число членов в монотонно убывающей последовательности с разницей между соседними членами, равной 1, начинающейся с a1 и состоящей из первых частей разбиения α). Графически эти параметры описываются очень просто:

α=(7 6 4 3 2) α=(8 7 6 5)

...............

.............

.... σ(α)=2...... σ(α)=4

........

.. s(α)=5

s(α)=2

Преобразуем разбиение следующим образом.

Случай 1. s(α) ≤ σ(α). В этом случае увеличение на единицу каждую из s(α) наибольших частей α и отбрасываем наименьшую часть. Таким образом

α=(7 6 4 3 2) → (8 7 4 3),

т. е.

 

...............

.............

.... →....

......

..

 

Случай 2. s(α) > σ(α). В этом случае, наоборот, уменьшаем на единицу каждую из σ(α) наибольших частей α и образуем наименьшую часть величины σ(α). Таким образом

α=(8 7 4 3) → (7 6 4 3 2),

т. е.

................

..............

.... →....

......

..

Описанная процедура в обоих случаях меняет четность числа частей разбиения; замечая, что к разбиению можно применять лишь один из этих случаев, видим, что такое отображение устанавливает взаимно однозначное соответствие. Однако имеются определенные разбиения, для которых это отображение не работает, например, α=(8 7 6 5). К нему нужно было бы применять случай 2, но получаемое посредством него новое разбиение уже содержит одинаковые части, т. е. не принадлежит нашему множеству D. Итак, случай 2 не работает, когда разбиение имеет вид σ(α)=r, s(α) =r+1, и в этом случае само разбиваемое число, очевидно, равно

(r+1)+(r+2)+…+2r= r(3r+1).

С другой стороны, случай 1 не работает, когда разбиение имеет r частей, σ(α)=r, s(α) =r, а само разбиваемое число, очевидно, равно

r+(r+1)+…+(2r-1)= r(3r-1).

Таким образом, если n не является пятиугольным числом, то Pe(D,n)=Pо(D,n), а если n= r(3r 1), то Pe(D,n) = Pо(D,n)+(-1)r

 

Следствие 1. (Пентагональная теорема Эйлера).

1-tn) = 1+ (1+tm)= .

Доказательство.

=1+ + =1+ + =1+ (1+tm)=1+ Pe(D,n) - Pо(D,n))tn.

Для полноты доказательства нужно еще показать, что

1+ Pe(D,n) - Pо(D,n))tn.= 1-tn).

Теперь

1-tn)=

как и в доказательстве формулы теоремы 5. Заметим, каждое разбиение с различными частями подсчитывается с весом , который равен +1, если это разбиение имеет четное число частей, и -1 в случае нечетного числа частей. Следовательно,

1-tn)= =1+ Pe(D,n) - Pо(D,n))tn

и тем самым имеем требуемое.

Следствие 2. (Эйлер). Если n>0, то

P(n)–P(n–1)–P(n–2)+P(n–5)+P(n–7)+…

…+(-1)m P(n–m(3m-1)/2)+(-1)m P(n–m(3m+1)/2)=0, (*)

где P(M)= 0 для всех отрицательных M.

Доказательство.

Пусть аn обозначает левую часть равенства (*). Тогда

 

= [1+ (1+tm)]= 1-tn)-1 1-tn)=1,

где предпоследнее равенство сразу следует из 6 и следствия1. поэтому аn = 0, для n>0.

Следствие 2 представляет собой весьма эффективный адгоритм для вычисления P(n).

 

Значения P(n) растут очень быстро с ростом n. Имеем:

 

P(1)=1; P(2)=2; P(3)=3; P(4)=5; P(5)=7; P(6)=11; P(10)=42; P(20)=627; P(50)=204 226; P(100)=190 569292; P(200)=3 972 999 029 388.

 

Однако, имеется точная формула для P(n) – результат, выведенный Харди и Рамануджаном и усовершенствованный Радемахером. Этот результат относится к одному из высших достижений теории разбиений:

Теорема (Харди – Рамануджана – Радемахера).

P(n)= , (1)

где

Аk(n)= h,ke-2πinh/k

и ωh,k – корень 24k-й степени из единицы, определяемый специальным образом.

Это необычайное тождество, котором левой частью служит простая арифметическая функция P(n), а в правой – бесконечный ряд, включающий в себя π, квадратные корни, комплексные корни из единицы и производные гиперболических функций, являет собой не только чисто теоретическую формулу для P(n), но формулу, обеспечивающую действительно быстрое вычисление.[4] (Для малых значений n можно, конечно, пользоваться рекуррентностью из приведенной ниже пентагональной теоремы Эйлера.) Кроме того, довольно просто показать, что каждый член бесконечного ряда в (1) есть O(exp{π(2n)1/2/k }). Следовательно, первый член k=1 дает нам асимптотическую формулу для P(n); замечая, что A1(n)=1, без особых трудностей получаем, что при n→∞

P(n)≈ .

 

 

Задачи.

1. (Саббарао). Число разбиений числа n, в которых части встречаются дважды, трижды или по пять раз, равно числу разбиений n на части, сравнимые с 2, 3, 6, 9, 10 по модулю 12.

2. Число разбиений числа n, в которых могут повторяться только нечетные части, равно числу разбиений n в которых нет части, встречающейся более чем три раза.

3. (Сильвестр). Число разбиений числа n с различными нечетными частями равно числу разбиений n, которые являются самосопряженными (т. е. совпадают со своим сопряжением).

4. (Эйлер). Абсолютное значение излишка числа разбиений n с нечетным числом частей над числом разбиений n с четным числом частей равно числу разбиений n на различные нечетные части.

 




Дата добавления: 2015-09-11; просмотров: 23 | Поможем написать вашу работу | Нарушение авторских прав

Конкретная математика | Производящие функции для сочетаний. | Производящие функции для перестановок. | Решение линейных рекуррентных уравнений. | Числа Стирлинга первого и второго рода. | Представление перестановок в циклической форме. | Принцип включения и исключения. | Число способов, которыми можно пометить граф. | Связные графы. | Эйлеровы графы |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.022 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав