Формула Добиньского - Dobińskis formula - Wikipedia

В комбинаторный математика, Формула Добинского^[1] заявляет, что п-го Номер звонка B_п (т.е. количество перегородки набора размера п) равно

${\displaystyle B_{n}={1 \over e}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}},}$

куда ${\displaystyle e}$ обозначает Число Эйлера Формула названа в честь Г. Добиньского, опубликовавшего ее в 1877 году.

Вероятностное содержание

В обстановке теория вероятности, Формула Добинского представляет собой пth момент из распределение Пуассона с иметь в виду 1. Иногда формула Добинского утверждается, что количество разделов набора размера п равно п-й момент этого распределения.

Сокращенная формула

Вычисление суммы ряда Добинского можно свести к конечной сумме п + о (п) сроки с учетом информации, ${\displaystyle B_{n}}$ целое число. Точно, для любого целого К> 1

${\displaystyle B_{n}=\left\lceil {1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}\right\rceil }$

при условии ${\displaystyle {\frac {K^{n}}{K!}}\leq 1}$ (условие, которое подразумевает К> п, но это устраивает некоторых K размера п + о (п)). Действительно, есть ${\displaystyle {\frac {(K+j)^{n}}{(K+j)!}}\leq {\frac {K^{n}}{K!}}{1 \over j!}\leq {1 \over j!}}$ для всех j ≥ 0так что хвост ${\displaystyle \sum _{k\geq K}{\frac {k^{n}}{k!}}=\sum _{j\geq 0}{\frac {(K+j)^{n}}{(K+j)!}}}$ преобладает сериал ${\displaystyle \sum _{j\geq 0}{\frac {1}{j!}}=e}$, что означает ${\displaystyle 0<B_{n}-{1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}<1}$, откуда и приведена формула.

Обобщение

Формулу Добинского можно рассматривать как частный случай для ${\displaystyle x=0}$, более общего отношения:

${\displaystyle {1 \over e}\sum _{k=x}^{\infty }{\frac {k^{n}}{(k-x)!}}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}x^{n-k}.}$

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

Одно доказательство^[2] опирается на формулу для производящая функция для чисел Белла,

${\displaystyle e^{e^{x}-1}=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}.}$

Степенной ряд для экспоненты дает

${\displaystyle e^{e^{x}}=\sum _{k=0}^{\infty }{\frac {e^{kx}}{k!}}=\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{n=0}^{\infty }{\frac {(kx)^{n}}{n!}}}$

так

${\displaystyle e^{e^{x}-1}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{n=0}^{\infty }{\frac {(kx)^{n}}{n!}}}$

Коэффициент ${\displaystyle x^{n}}$ в этом степенном ряду должны быть ${\displaystyle B_{n}/n!}$, так

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.}$

Другой способ доказательства был дан Рота.^[3] Напомним, что если Икс и п неотрицательные целые числа, то количество индивидуальные функции что карта размера-п установить в размер-Икс набор - это падающий факториал

${\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1)}$

Позволять ƒ быть любой функцией от размера-п набор А в размер-Икс набор B. Для любого б ∈ B, позволять ƒ ⁻¹(б) = {а ∈ А : ƒ(а) = б}. потом {ƒ ⁻¹(б) : б ∈ B} является разделом А. Рота называет этот раздел "ядро "функции ƒ. Любая функция из А в B факторы в

• одна функция, которая отображает член А элементу ядра, которому он принадлежит, и
• другая функция, которая обязательно взаимно однозначна, которая отображает ядро ​​в B.

Первый из этих двух факторов полностью определяется разделением π это ядро. Количество взаимно однозначных функций от π в B является (Икс)_|π|, где |π| количество частей в разделе π. Таким образом, общее количество функций от размера-п набор А в размер-Икс набор B является

${\displaystyle \sum _{\pi }(x)_{|\pi |},}$

индекс π пробегает множество всех разделов А. С другой стороны, количество функций из А в B ясно Икс^п. Следовательно, мы имеем

${\displaystyle x^{n}=\sum _{\pi }(x)_{|\pi |}.}$

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

${\displaystyle E(X^{n})=\sum _{\pi }E((X)_{|\pi |})}$

куда E означает ожидаемое значение. Но мы покажем, что все величины E((Икс)_k) равным 1. Отсюда следует, что

${\displaystyle E(X^{n})=\sum _{\pi }1,}$

а это просто количество разделов набора А.

Количество E((Икс)_k) называется kth факторный момент случайной величины Икс. Чтобы показать, что это равно 1 для всех k когда Икс случайная величина с распределением Пуассона со средним значением 1, напомним, что эта случайная величина принимает каждое значение целого числа ${\displaystyle j\geq 0}$ с вероятностью ${\displaystyle 1/(ej!)}$. Таким образом

${\displaystyle E((X)_{k})=\sum _{j=0}^{\infty }{\frac {(j)_{k}}{ej!}}={\frac {1}{e}}\sum _{j=0}^{\infty }{\frac {j(j-1)\cdots (j-k+1)}{j(j-1)\cdots 1}}={\frac {1}{e}}\sum _{j=i}^{\infty }{\frac {1}{(j-i)!}}=1.}$

Примечания и ссылки

1. Добинский, Г. (1877). "Summirung der Reihe ${\displaystyle \textstyle \sum {\frac {n^{m}}{n!}}}$ мех м = 1, 2, 3, 4, 5, …". Архив Грюнерта (на немецком). 61: 333–336.
2. Бендер, Эдвард А .; Уильямсон, С. Гилл (2006). «Теорема 11.3, формула Добинского». Основы комбинаторики с приложениями (PDF). Дувр. С. 319–320. ISBN  0-486-44603-4.
3. Рота, Джан-Карло (1964), «Количество перегородок в комплекте» (PDF), Американский математический ежемесячный журнал, 71: 498–504, Дои:10.2307/2312585, МИСТЕР  0161805.