Числа Стирлинга первого рода

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

Числа Стирлинга первого рода (без знака) — количество перестановок порядка n с kциклами.

Определение

Числами Стирлинга первого рода (со знаком) s(n, k) называются коэффициенты многочлена:

где (x)_n — символ Похгаммера (убывающий факториал):

Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения задают количество перестановок множества, состоящего из n элементов с kциклами.

Рекуррентное соотношение

Числа Стирлинга первого рода задаются рекуррентным соотношением:

s(n,n) = 1, для n ≥ 0,

s(n,0) = 0, для n > 0,

для 0 <k<n.

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

Для n=1 это равенство проверяется непосредственно. Пусть перестановка (n-1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки — различные и содержат k циклов, их количество (n-1)·s(n-1, k). Из любой перестановки (n-1)-го порядка, содержащей k-1 цикл, можно сформировать единственную перестановку n порядка, содержащую k циклов, добавив цикл образованный единственным числом n. Очевидно, что эта конструкция описывает все перестановки n-го порядка, содержащие k циклов. Тем самым равенство доказано.

Пример

Первые ряды:

n\k
		−1
			−3
		−6		−6
			−50		−10
		−120		−225		−15

В комбинаторикечислом Стирлинга второго рода из n по k, обозначаемым или , называется количество неупорядоченных разбиенийn-элементного множества на k непустых подмножеств.

Рекуррентная формула

Числа Стирлинга второго рода удовлетворяют рекуррентному соотношению:

, для n ≥ 0,

, для n > 0,

для

Явная формула

Пример

Начальные значения чисел Стирлинга второго рода приведены в таблице:

n\k

Свойства

• где
• 
• — число Белла.

Биективным отображением называется отображение, обладающее признаками инъективности и сюръективности одновременно.

Биекция

Материал из Википедии — свободной энциклопедии

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 18 февраля 2012; проверки требуют 2 правки.

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 18 февраля 2012; проверки требуют 2 правки.

Перейти к: навигация, поиск

Биективная функция.

Биекция — это отображение, которое является одновременно и сюръективным, и инъективным. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом, определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием), одно-однозначным отображением.

Если между двумя множествами можно установить взаимно-однозначное соответствие (биекция), то такие множества называются равномощными. С точки зрения теории множеств, равномощные множества неразличимы.

Взаимно-однозначное отображение конечного множества в себя называется перестановкой (элементов этого множества).

Определение

Функция называется биекцией (и обозначается ), если она:

1. Переводит разные элементы множества в разные элементы множества (инъективность). Иными словами,
• .
2. Любой элемент из имеет свой прообраз (сюръективность). Иными словами,
• .

Примеры

• Тождественное отображение на множестве биективно.
• — биективные функции из в себя. Вообще, любой моном одной переменнойнечетнойстепени является биекцией из в себя.
• — биективная функция из в .
• не является биективной функцией, если считать её определённой на всём .

Свойства

Композиция инъекции и сюръекции, дающая биекцию.

• Функция является биективной тогда и только тогда, когда существует обратная функция такая, что

и

• Если функции и биективны, то и композиция функций биективна, в этом случае . Коротко: композиция биекций является биекцией. Обратное, однако, неверно: если биективна, то мы можем утверждать лишь, что инъективна, а сюръективна.

Применения

В информатике

Организация связи «один к одному» между таблицамиреляционной БД на основе первичных ключей.

Числа Каталана

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

ЧислаКатала́на — числовая последовательность, встречающаяся во многих задачах комбинаторики. Последовательность названа в честь бельгийского математика Каталана, хотя была известна ещё Л. Эйлеру.

Первые несколько чисел Каталана:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (последовательность A000108 в OEIS)

Содержание

Определения

n-е число Каталана можно определить одним из следующих способов:

• Количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями.
• Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих.

Например, для n=3 существует 5 таких последовательностей:

((())), ()(()), ()()(), (())(), (()())

то есть .

• Количество способов соединения 2n точек на окружности n непересекающимися хордами.
• Количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями.

Свойства

• Числа Каталана удовлетворяют рекуррентному соотношению:

и для

Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w=(w₁)w₂, где w₁, w₂ — правильные скобочные последовательности.

• Производящая функция чисел Каталана равна:

• Числа Каталана можно выразить через биномиальные коэффициенты:

Другими словами, число Каталана равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.

• Асимптотически

Чтобы не ограничиваться одной только ссылкой, напишу приведенный в "Конкретной математике" вывод формулы для чисел Каталана. Красивое и очень простое рассуждение.

Определение (одно из многих). Числом Каталана C_n называется количество последовательностей длины (2n+1) a₀, a₁, ..., a_2n, составленных из +1 и -1, таких что сумма чисел равна +1, а все частичные суммы
a₀, a₀+a₁, ..., a₀+...+a_2n
положительны.

Лемма Рени. Если x₁, x₂, ..., x_m - любая последовательность целых чисел, сумма которых равна +1, то ровно у одного из её циклических сдвигов
x₁, x₂, ..., x_m
x₂, ..., x_m, x₁
x_m, x₁, ..., x_m-1
частичные суммы все положительны.
Доказательство.Продолжим последовательность периодически до бесконечной последовательности: x_m+k=x_k, для всех k>0. Если для этой бесконечной последовательности нарисовать график частичных сумм s_n=x₁+...+x_n, то он будет иметь "средний наклон" 1/m, поскольку s_n+m=s_n+1. Весь график может быть заключён между двумя прямыми наклона 1/m. Эти прямые касаются графика ровно один раз на каждом периоде из m точек, поскольку прямые с наклоном 1/m могут проходить через точки с целыми координатами только один раз на m единиц. Единственная нижняя точка касания-- это то единственное место в цикле, начиная с которого все частные суммы будут положительны.

Подсчёт последовательностей из +1 и -1 с общей суммой +1.
Всего есть C_2n+1ⁿ последовательностей, содержащих n элементов -1 и (n+1) элементов +1. Построим все C_2n+1ⁿ последовательностей и все (2n+1) их циклических сдвигов в виде таблицы из C_2n+1ⁿ строк и (2n+1) столбцов. Очевидно, что каждая последовательность встречается в таблице (2n+1) раз, по одному разу в каждом столбце. По лемме Рени в каждой строке содержится ровно одна последовательность с положительными частичными суммами. Таким образом, всего в таблице искомые последовательности встречается C_2n+1ⁿ раз. Каждая встречается (2n+1) раз. Следовательно
C_n = C_2n+1ⁿ/(2n+1) = C_2nⁿ/(n+1).

28) Биномиальный коэффициент

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

В математике биномиальные коэффициенты — это коэффициенты в разложениибинома Ньютона по степеням x. Коэффициент при обозначается (иногда ) и читается «биномиальный коэффициент из n по k» (или «це из n по k»):

В комбинаторике биномиальный коэффициент интерпретируется как количество сочетаний из n по k, то есть количество всех подмножеств (выборок) размера k в n-элементном множестве.

Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.

Явные формулы

Значение биномиального коэффициента определено для всех целых чисел n и k. Явные формулы для вычисления биномиальных коэффициентов:

для

для или

для

где обозначает факториал числа m.

Треугольник Паскаля

Тождество

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).

Строки в треугольнике Паскаля в пределе стремятся к функции нормального распределения.

Если взять квадратную матрицу, отсчитав N элементов по катетам треугольника и повернув квадрат на любой из четырёх углов, то детерминант этих четырёх матриц по модулю равен 1 при любом N. Если поставить уголом из 1 в верхний левый угол, то детерминант матрицы будет равен 1.

В матрице числа на диагонали i+j = const повторяют числа строк треугольника Паскаля. (i,j = 0...∞)

Матрицу где i, j = 0…p можно разложить в произведение двух строго диагональных матриц. Первая нижнетреугольная, а вторая получается из первой путем транcпонирования. Элементы такой матрицы

где i,j = 0...p Далее обратная матрица к U

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

i,j,m,n = 0...p, если выражение в кваратных скобках ложно, то элемент суммы равен 0. Элементы обратной матрицы меняются при изменение её размера и в отличие от матрицы недостаточно приписать новую строку и столбец.

Свойства

Производящие функции

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

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

Двумерной производящей функцией биномиальных коэффициентов является:

Делимость

Из теоремы Люка следует, что:

• нечётен в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
• некратен простому p в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
• В последовательности биномиальных коэффициентов :
• все числа не кратны заданному простому p , где натуральное число m<p;
• все числа, кроме первого и последнего, кратны заданному простому p ;
• количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
• не может быть поровну чётных и нечётных чисел;
• количество не кратных простомуp чисел равно , где числа — разряды p-ичной записи числа n; а число — её длина.

Тождества

• 
• (правило симметрии).
• 
• Следствия тождества :
• 
• 
• для .
• Это тождество можно усилить
• 0<a<n
• a>=n
• если — более общий вид тождества выше.
• 
• 
• (свёртка Вандермонда).
• — m-оегармоническое число.
• Мультисекция ряда даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t в виде замкнутой суммы из s слагаемых:

Асимптотика и оценки

• 
• при
• , при

где

• 

Алгоритмы вычисления

Биномиальные коэффициенты могут быть вычислены с помощью формулы , если на каждом шаге хранить значения при . Этот алгоритм особенно эффективен, если нужно получить все значения при фиксированном . Алгоритм требует памяти ( при вычислении всей таблицы биномиальных коэффициентов) и времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле с начальным значением . Для вычисления значения этот метод требует памяти и времени.