Номер телефона (математика) - Telephone number (mathematics) - Wikipedia

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

Повторение

Номера телефонов соответствуют требованиям отношение повторения

${\displaystyle T(n)=T(n-1)+(n-1)T(n-2),}$

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

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

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

${\displaystyle T(n)=\sum _{k=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 дает количество совпавших пар, биномиальный коэффициент ${\displaystyle {\binom {n}{2k}}}$ подсчитывает количество способов выбора 2k элементы, которые необходимо сопоставить, и двойной факториал (2k − 1)!! = (2k)!/(2^kk!) является произведением нечетных целых чисел до своего аргумента и подсчитывает количество способов полного соответствия 2k выбранные элементы.^[1][10] Из формулы суммирования и Приближение Стирлинга который, асимптотически,

${\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]

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

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

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

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

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

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

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

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

1. Кнут, Дональд Э. (1973), Искусство программирования, Том 3: Сортировка и поиск, Ридинг, Массачусетс: Addison-Wesley, стр. 65–67, МИСТЕР  0445948.
2. Риордан, Джон (2002), Введение в комбинаторный анализ, Dover, pp. 85–86..
3. Пирт, Пол; Воан, Вэнь-Цзинь (2000), «Производящие функции через матрицы Ганкеля и Стилтьеса» (PDF), Журнал целочисленных последовательностей, 3 (2), статья 00.2.1, МИСТЕР  1778992.
4. Гету, Сейюм (1991), «Оценка определителей с помощью производящих функций», Математический журнал, 64 (1): 45–53, Дои:10.2307/2690455, МИСТЕР  1092195.
5. Соломон, A. I .; Blasiak, P .; Duchamp, G .; Horzela, A .; Пенсон, К.А. (2005), «Комбинаторная физика, нормальный порядок и модельные графы Фейнмана», в Gruber, Bruno J .; Мармо, Джузеппе; Ёсинага, Наотака (ред.), Симметрии в науке XI, Kluwer Academic Publishers, стр. 527–536, arXiv:Quant-ph / 0310174, Дои:10.1007 / 1-4020-2634-X_25.
6. Blasiak, P .; Dattoli, G .; Horzela, A .; Пенсон, К. А .; Жуковский, К. (2008), «Числа Моцкина, центральные трехчлены коэффициенты и гибридные многочлены», Журнал целочисленных последовательностей, 11 (1), статья 08.1.1, arXiv:0802.0075, МИСТЕР  2377567.
7. Тихи, Роберт Ф .; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов комбинаторной химии» (PDF), Журнал вычислительной биологии, 12 (7): 1004–1013, Дои:10.1089 / cmb.2005.12.1004, PMID  16201918.
8. Прямое соответствие между инволюциями и таблицами, вдохновленное соотношением рекуррентности для телефонных номеров, дается выражением Бейсинджер, Джанет Симпсон (1987), «Подобные конструкции для таблиц Юнга и инволюций и их применение к сдвигаемым таблицам», Дискретная математика, 67 (2): 149–163, Дои:10.1016 / 0012-365X (87) 90024-0, МИСТЕР  0913181.
9. Холт, Д. Ф. (1974), «Грачи неприкосновенны», Математический вестник, 58 (404): 131–134, JSTOR  3617799.
10. Чоула, С.; Герштейн, И.; Мур, В. К. (1951), "О рекурсиях, связанных с симметрическими группами. I", Канадский математический журнал, 3: 328–334, Дои:10.4153 / CJM-1951-038-3, МИСТЕР  0041849.
11. Мозер, Лев; Вайман, Макс (1955), "О решениях Икс^d = 1 в симметрических группах », Канадский математический журнал, 7: 159–168, Дои:10.4153 / CJM-1955-021-8, МИСТЕР  0068564.
12. Бандерье, Кирилл; Буске-Мелу, Мирей; Дениз, Ален; Флажоле, Филипп; Гарди, Даниэль; Gouyou-Beauchamps, Dominique (2002), "Производящие функции для создания деревьев", Дискретная математика, 246 (1–3): 29–55, arXiv:математика / 0411250, Дои:10.1016 / S0012-365X (01) 00250-3, МИСТЕР  1884885.
13. Ким, Донсу; Ким, Чан Су (2010), "Комбинаторный подход к степени двойки в количестве инволюций", Журнал комбинаторной теории, Серия А, 117 (8): 1082–1094, arXiv:0902.4311, Дои:10.1016 / j.jcta.2009.08.002, МИСТЕР  2677675.