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

Полный граф К ₄ имеет десять паросочетаний, соответствующий значению Т (4) = 10 четвертых телефонный номер.

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

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

Приложения

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

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

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

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

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

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

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

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

Математические свойства

Повторение

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

${\ Displaystyle Т (п) = Т (п-1) + (п-1) Т (п-2),}$

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

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

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

${\ Displaystyle Т (п) = \ сумма _ {к = 0} ^ {\ lfloor n / 2 \ rfloor} {\ binom {n} {2k}} (2k-1) !! = \ sum _ {k = 0} ^ {\ lfloor n / 2 \ rfloor} {\ frac {n!} {2 ^ {k} (n-2k)! K!}}.}.}$

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

${\displaystyle T(n)\sim \left({\frac {n}{e}}\right)^{n/2}{\frac {e^{\sqrt {n}}}{(4e)^{1/4}}}\,.}$^{[1] [10] [11]}

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

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

${\displaystyle \sum _{n=0}^{\infty }{\frac {T(n)x^{n}}{n!}}=\exp \left({\frac {x^{2}}{2}}+x\right).}$^{[10] [12]}

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

${\displaystyle T(n)={\frac {{\mathit {He}}_{n}(i)}{i^{n}}}.}$

главные факторы

При больших значениях п , то п - й номер телефона делится на большой степени двух , 2 ^{н / 4 + O (1)} .

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

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

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

Рекомендации