Номер телефона (математика)

На полном графике K4есть десять соответствий, соответствующих значению T (4) = 10 четвертого телефонного номера.

In математика, телефонные номера или инволюционные числа представляют собой последовательность целых чисел, которые подсчитывают способы соединения n телефонных линий друг с другом, где каждая линия может быть соединена максимум с одной другой линией. Эти числа также описывают количество соответствий (индекс Хосоя ) полного графа на n вершинах, количество перестановок на n элементов, которые являются инволюциями, суммой абсолютных значений коэффициентов многочленов Эрмита, количеством стандартных таблиц Юнга с n ячейками и суммой степени неприводимых представлений симметрической группы . Числа инволюции были впервые изучены в 1800 году Генрихом Августом Роте, который дал рекуррентное уравнение, с помощью которого они могут быть вычислены, дав значения (начиная с n = 0)

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496,... (последовательность A000085 в OEIS ).

• 1 Приложения
• 2 Математические свойства
  • 2.1 Повторяемость
  • 2.2 Формула суммирования и приближение
  • 2.3 Производящая функция
  • 2.4 Основные множители
• 3 Ссылки

Джон Риордан дает следующее объяснение для этих номеров: предположим, что у телефонной службы есть n абонентов, любые двое из которых могут быть подключены друг к другу с помощью телефонного звонка. Сколько различных схем подключения возможно? Например, для трех абонентов существует три способа формирования один телефонный звонок и один дополнительный шаблон, в котором не производится никаких звонков, всего четыре шаблона. По этой причине числа, подсчитывающие, сколько шаблонов ssible иногда называют телефонными номерами.

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

В теории графов подмножество ребер графа, которое касается каждой вершины не более одного раза, называется соответствием. Количество различных совпадений данного графа важно в химической теории графов, где графы моделируют молекулы, а количество совпадений известно как индекс Хосоя. Наибольший возможный индекс Хосоя для n-вершинного графа задается полными графами, для которых возможен любой образец попарных соединений; таким образом, индекс Хосоя полного графа с n вершинами совпадает с индексом n-го телефонного номера.

Стандартная таблица Юнга

A диаграмма Феррерса представляет собой геометрическую фигуру, образованную набором n квадратов на плоскости., сгруппированные в полимино с горизонтальным верхним краем, вертикальным левым краем и единой монотонной цепочкой горизонтальных и вертикальных нижнего и правого краев. Стандартная таблица Юнга формируется путем размещения чисел от 1 до n в этих квадратах таким образом, чтобы числа увеличивались слева направо и сверху вниз по всей таблице. Согласно соответствию Робинсона – Шенстеда, перестановки взаимно однозначно соответствуют упорядоченным парам стандартных таблиц Юнга. Инвертирование перестановки соответствует перестановке двух таблиц, и поэтому самообратные перестановки соответствуют одиночным таблицам, спаренным сами с собой. Таким образом, телефонные номера также подсчитывают количество картин Юнга с n квадратами. В теории представлений диаграммы Феррерса соответствуют неприводимым представлениям симметрической группы перестановок, а таблицы Юнга с заданной формой образуют основу неприводимое представление с этой формой. Следовательно, телефонные номера дают сумму степеней неприводимых представлений.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Диагонально-симметричное не атакующее расположение восьми ладей на шахматной доске

В математике шахмат телефонные номера подсчитывают количество способов разместить n ладей на n × n шахматная доска таким образом, чтобы две ладьи не нападали друг на друга (так называемая головоломка с восемью ладьями ), и таким образом, чтобы расположение ладей было симметричным относительно диагонального отражения доска. В соответствии с теоремой перечисления Полиа эти числа образуют один из ключевых компонентов формулы для общего количества «существенно различных» конфигураций n взаимно не атакующих ладей, где две конфигурации считаются существенно разными, если нет симметрии доски, которая переводит один в другой.

Повторяемость

Телефонные номера удовлетворяют соотношению повторения

$T\; (\; п)\; знак\; равно\; Т\; (п\; -\; 1)\; +\; (п\; -\; 1)\; Т\; (п\; -\; 2),\; \{\backslash \; Displaystyle\; Т\; (п)\; =\; Т\; (п-1)\; +\; (п-1)\; Т\; (п-2),\}$

впервые опубликовано в 1800 году Генрихом Августом Роте, с помощью которого их можно легко вычислить. Один из способов объяснить это повторение - разделить шаблоны подключения T (n) n абонентов к телефонной системе на шаблоны, в которых первый абонент никому не звонит, и шаблоны, в которых первый абонент выполняет вызов.. Есть T (n - 1) шаблонов подключения, в которых первый абонент отключен, что объясняет первый член повторения. Если первый подписчик связан с кем-то еще, существует n - 1 вариантов, для которых другой подписчик он подключен, и T (n - 2) шаблонов подключения для оставшихся n - 2 подписчиков, что объясняет второй член повторяемости..

Формула суммирования и приближение

Телефонные номера могут быть выражены точно как суммирование

$T\; (n)\; =\; \sum \; k\; =\; 0\; \lfloor \; n\; /\; 2\; \rfloor \; (n\; 2\; л)\; (2\; к\; -\; 1)!\; !\; Знак\; равно\; \sum \; К\; знак\; равно\; 0\; \lfloor \; N\; /\; 2\; \rfloor \; N!\; 2\; к\; (п\; -\; 2\; к)!\; к!.\; \{\backslash \; Displaystyle\; Т\; (п)\; =\; \backslash \; сумма\; \_\; \{к\; =\; 0\}\; ^\; \{\backslash \; lfloor\; n\; /\; 2\; \backslash \; rfloor\}\; \{\backslash \; binom\; \{n\}\; \{2k\}\}\; (2k-1)\; !!\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\backslash \; lfloor\; n\; /\; 2\; \backslash \; rfloor\}\; \{\backslash \; frac\; \{n!\}\; \{2\; ^\; \{k\}\; (n-2k)!\; K!\}\}.\}$

В каждом члене этой суммы k дает количество совпадающих пар, биномиальный коэффициент $(n\; 2\; k)\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{2k\}\}\}$подсчитывает количество способов выбора 2k элементов для сопоставления и двойной факториал (2k - 1) !! = (2k)! / (2k!) - произведение нечетных целых чисел до его аргумента и подсчитывает количество способов полного совпадения 2k выбранных элементов. Из формулы суммирования и приближения Стирлинга следует, что асимптотически,

$T\; (n)\; \sim \; (n\; e)\; n\; /\; 2\; e\; n\; (4\; e)\; 1/4.\; \{\backslash \; displaystyle\; T\; (n)\; \backslash \; sim\; \backslash \; left\; (\{\backslash \; frac\; \{n\}\; \{e\}\}\; \backslash \; right)\; ^\; \{n\; /\; 2\}\; \{\backslash \; frac\; \{e\; ^\; \{\backslash \; sqrt\; \{n\}\}\}\; \{(4e)\; ^\; \{1/4\}\}\}\; \backslash ,.\}$

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

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

$\sum \; n\; =\; 0\; \infty \; T\; (n)\; xnn\; !\; знак\; равно\; ехр\; \; (х\; 2\; 2\; +\; х).\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{T\; (n)\; x\; ^\; \{n\}\}\; \{n!\}\}\; =\; \backslash \; exp\; \backslash \; left\; (\{\backslash \; frac\; \{x\; ^\; \{2\})\; \}\; \{2\}\}\; +\; x\; \backslash \; right).\}$

Другими словами, телефонные номера могут быть считаны как коэффициенты ряда Тейлора exp (x / 2 + x), и n-й телефонный номер - это значение n-й производной этой функции в нуле. Эта функция тесно связана с экспоненциальной производящей функцией полиномов Эрмита, которые являются совпадающими полиномами полных графов. Сумма абсолютных значений коэффициентов n-го (вероятностного) полинома Эрмита является n-м телефонным номером, и телефонные номера также могут быть реализованы как некоторые специальные значения полиномов Эрмита:

$T\; (n)\; =\; H\; en\; (\; i)\; в.\; \{\backslash \; displaystyle\; T\; (n)\; =\; \{\backslash \; frac\; \{\{\backslash \; mathit\; \{He\}\}\; \_\; \{n\}\; (i)\}\; \{i\; ^\; \{n\}\}\}.\}$

Основные множители

Для больших значений n, n-й телефонный номер делится на большую степень двойки, 2.

Точнее, 2-адический порядок (количество множителей из двух в разложении на простые множители ) T (4k) и T (4k + 1) равно k; для T (4k + 2) это k + 1, а для T (4k + 3) это k + 2.

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

2, 5, 13, 19, 23, 29, 31, 43, 53, 59,... (последовательность A264737 в OEIS )