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

В математике телефонные номера или числа инволюции образуют последовательность целых чисел , которая подсчитывает способы $связи n$ людей посредством личных телефонных звонков. Эти числа также описывают количество паросочетаний ( индекс Хосои ) полного графа на $n$ вершинах, количество перестановок на $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]

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

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

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

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

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

Повторение

Телефонные номера удовлетворяют рекуррентному соотношению $T(0)=1,$ $T(n)=T(n-1)+(n-1)T(n-2),\quad \mathrm {for~} n\geq 1,$ впервые опубликовано в 1800 году Генрихом Августом Роте , с помощью которого их можно легко вычислить. ^[1]Один из способов объяснить эту повторяемость — разделить $T (n)$ шаблоны подключения $n$ абонентов к телефонной системе на шаблоны, в которых первый человек никому больше не звонит, и шаблоны, в которых первый человек звонит. . Существует $T (n - 1)$ паттернов соединения, в которых первый человек отключен, что объясняет первый член повторения. Если первый человек связан с кем-то, то для этого человека существует $n - 1$ вариантов выбора, а $человек существует T (n - 2)$ для остальных $n - 2$ шаблонов связи , что объясняет второй член повторения. ^[11]

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

Телефонные номера могут быть выражены точно как сумма $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$ дает количество совпавших пар, биномиальный коэффициент ${\tbinom {n}{2k}}$ подсчитывает количество способов выбора $2k$ элементы, которые необходимо сопоставить, и двойной факториал $(2k-1)!!={\frac {(2k)!}{2^{k}\,k!}}$ является произведением нечетных целых чисел до своего аргумента и подсчитывает количество способов полного сопоставления $2k выбранных элементов$ . ^[1]^[11] Из формулы суммирования и приближения Стирлинга что асимптотически следует , ^[1]^[11]^[12] $T(n)\sim \left({\frac {n}{e}}\right)^{n/2}{\frac {e^{\sqrt {n}}}{(4e)^{1/4}}}\,.$

Генерирующая функция

Экспоненциальная производящая функция телефонных номеров равна ^[11]^[13] $G(x)=\sum _{n=0}^{\infty }{\frac {T(n)x^{n}}{n!}}=\exp \left(x+{\frac {x^{2}}{2}}\right).$ Другими словами, телефонные номера можно считать коэффициентами Тейлора ряда $exp(x + x 2 /2)$ и, в частности, $n$ -й номер телефона является нулевым значением $n$ -й производной этой функции. Экспоненциальную производящую функцию можно получить несколькими способами; например, взяв рекуррентное соотношение для $T (n)$ выше, умножив его на $x п -1 / (n - 1)!$ , а суммирование по $n \geq 1$ дает $\sum _{n}T(n){\frac {x^{n-1}}{(n-1)!}}=\sum _{n}T(n-1){\frac {x^{n-1}}{(n-1)!}}+x\sum _{n}T(n-2){\frac {x^{n-2}}{(n-2)!}}\,\mathrm {,~which~is}$ $G'(x)=G(x)+xG(x)\,.$ Общим решением этого дифференциального уравнения является $G (x) \propto exp(x + x 2 /2)$ , а $T (0) = 1$ показывает, что константа пропорциональности равна 1.

Эта функция тесно связана с экспоненциальной производящей функцией полиномов Эрмита , которые являются соответствующими полиномами полных графов. ^[13]Сумма абсолютных значений коэффициентов $n$ -го (вероятностного) полинома Эрмита представляет собой $n-$ й телефонный номер, причем номера телефонов также могут быть реализованы как некоторые специальные значения полиномов Эрмита: ^[5]^[13] $T(n)={\frac {{\mathit {He}}_{n}(i)}{i^{n}}}.$

Основные факторы

При больших значениях $n$ n $- й$ номер телефона делится на большую степень двойки , $2 п /4 + О (1)$ . Точнее, 2-адический порядок (количество множителей два в простой факторизации ) $T (4 k)$ и $T (4 k + 1)$ равен $k$ ; для $T (4k + 2)$ это $k +1$ , а для $T (4k +3)$ это $k +2$ . ^[14]

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

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

Нечетные простые числа в этой последовательности были названы неэффективными . Каждый из них делит бесконечно много телефонных номеров. ^[16]

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Кнут, Дональд Э. (1973), Искусство компьютерного программирования , Том 3: Сортировка и поиск , Чтение, Массачусетс: Аддисон-Уэсли, стр. 65–67, MR 0445948
^ Риордан, Джон (2002), Введение в комбинаторный анализ , Дувр, стр. 85–86.
^ Пирт, Пол; Воан, Вэнь-Цзинь (2000), «Построение функций с помощью матриц Ханкеля и Стилтьеса» (PDF) , Журнал целочисленных последовательностей , 3 (2), статья 00.2.1, Бибкод : 2000JIntS...3...21P , MR 1778992
^ Гету, Сейюм (1991), «Оценка определителей с помощью производящих функций», Mathematics Magazine , 64 (1): 45–53, doi : 10.2307/2690455 , JSTOR 2690455 , MR 1092195
^ Jump up to: ^а ^б Соломон, А.И.; Блазиак, П.; Дюшан, Г.; Хорзела, А.; Пенсон, К.А. (2005), «Комбинаторная физика, нормальный порядок и модельные графы Фейнмана», Грубер, Бруно Дж.; Мармо, Джузеппе; Ёсинага, Наотака (ред.), «Симметрии в науке XI» , Kluwer Academic Publishers, стр. 527–536, arXiv : quant-ph/0310174 , doi : 10.1007/1-4020-2634-X_25 , ISBN 1-4020-2633-1 , S2CID 5702844
^ Блазиак, П.; Даттоли, Г.; Хорзела, А.; Пенсон, Калифорния; Жуковский, К. (2008), «Числа Моцкина, центральные триномиальные коэффициенты и гибридные полиномы» , Журнал целочисленных последовательностей , 11 (1), статья 08.1.1, arXiv : 0802.0075 , Bibcode : 2008JIntS..11...11B , МР 2377567
^ Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi : 10.1089/cmb.2005.12.1004 , PMID 16201918
^ Прямая биекция между инволюциями и таблицами, вдохновленная рекуррентным соотношением для телефонных номеров, определяется выражением Бейсингер, Джанет Симпсон (1987), «Подобные конструкции для таблиц Юнга и инволюций и их применение к смещаемым таблицам», Discrete Mathematics , 67 (2): 149–163, doi : 10.1016/0012-365X(87)90024-0 , МР 0913181
^ Халверсон, Том; Рикс, Майк (2015), «Модели Гельфанда для диаграммных алгебр», Журнал алгебраической комбинаторики , 41 (2): 229–255, arXiv : 1302.6150 , doi : 10.1007/s10801-014-0534-5 , MR 3306071 , S2CID 7419411
^ Холт, Д.Ф. (1974), «Неприкосновенные ладьи», The Mathematical Gazette , 58 (404): 131–134, doi : 10.2307/3617799 , JSTOR 3617799 , S2CID 250441965
^ Jump up to: ^а ^б ^с ^д Чола, С. ; Херштейн, Индиана ; Мур, WK (1951), «О рекурсиях, связанных с симметричными группами. I», Canadian Journal of Mathematics , 3 : 328–334, doi : 10.4153/CJM-1951-038-3 , MR 0041849 , S2CID 123802787
^ Мозер, Лео ; Вайман, Макс (1955), "О решениях $x д = 1$ в симметричных группах», Canadian Journal of Mathematics , 7 : 159–168, doi : 10.4153/CJM-1955-021-8 , MR 0068564
^ Jump up to: ^а ^б ^с Бандерье, Сирил; Буске-Мелу, Мирей ; Дениз, Ален; Флажоле, Филипп ; Гарди, Даниэль; Гую-Бошам, Доминик (2002), «Производящие функции для генерации деревьев», Discrete Mathematics , 246 (1–3): 29–55, arXiv : math/0411250 , doi : 10.1016/S0012-365X(01)00250-3 , MR 1884885 , S2CID 14804110
^ Ким, Донгсу; Ким, Чан Су (2010), «Комбинаторный подход к степени двойки в числе инволюций», Журнал комбинаторной теории , серия A, 117 (8): 1082–1094, arXiv : 0902.4311 , doi : 10.1016/j .jcta.2009.08.002 , MR 2677675 , S2CID 17457503
^ Слоан, Нью-Джерси (редактор), «Последовательность A264737» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
^ Амдеберхан, Теодрос; Молл, Виктор (2015), «Инволюции и их потомки», Journal of Combinatorics , 6 (4): 483–508, arXiv : 1406.2356 , doi : 10.4310/JOC.2015.v6.n4.a5 , MR 3382606 , S2CID 119708272

[knuth-1] Jump up to: ^а ^б ^с ^д ^и ^ж Кнут, Дональд Э. (1973), Искусство компьютерного программирования , Том 3: Сортировка и поиск , Чтение, Массачусетс: Аддисон-Уэсли, стр. 65–67, MR 0445948

[2] Риордан, Джон (2002), Введение в комбинаторный анализ , Дувр, стр. 85–86.

[3] Пирт, Пол; Воан, Вэнь-Цзинь (2000), «Построение функций с помощью матриц Ханкеля и Стилтьеса» (PDF) , Журнал целочисленных последовательностей , 3 (2), статья 00.2.1, Бибкод : 2000JIntS...3...21P , MR 1778992

[4] Гету, Сейюм (1991), «Оценка определителей с помощью производящих функций», Mathematics Magazine , 64 (1): 45–53, doi : 10.2307/2690455 , JSTOR 2690455 , MR 1092195

[sbdhp-5] Jump up to: ^а ^б Соломон, А.И.; Блазиак, П.; Дюшан, Г.; Хорзела, А.; Пенсон, К.А. (2005), «Комбинаторная физика, нормальный порядок и модельные графы Фейнмана», Грубер, Бруно Дж.; Мармо, Джузеппе; Ёсинага, Наотака (ред.), «Симметрии в науке XI» , Kluwer Academic Publishers, стр. 527–536, arXiv : quant-ph/0310174 , doi : 10.1007/1-4020-2634-X_25 , ISBN 1-4020-2633-1 , S2CID 5702844

[6] Блазиак, П.; Даттоли, Г.; Хорзела, А.; Пенсон, Калифорния; Жуковский, К. (2008), «Числа Моцкина, центральные триномиальные коэффициенты и гибридные полиномы» , Журнал целочисленных последовательностей , 11 (1), статья 08.1.1, arXiv : 0802.0075 , Bibcode : 2008JIntS..11...11B , МР 2377567

[7] Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi : 10.1089/cmb.2005.12.1004 , PMID 16201918

[b-8] Прямая биекция между инволюциями и таблицами, вдохновленная рекуррентным соотношением для телефонных номеров, определяется выражением Бейсингер, Джанет Симпсон (1987), «Подобные конструкции для таблиц Юнга и инволюций и их применение к смещаемым таблицам», Discrete Mathematics , 67 (2): 149–163, doi : 10.1016/0012-365X(87)90024-0 , МР 0913181

[9] Халверсон, Том; Рикс, Майк (2015), «Модели Гельфанда для диаграммных алгебр», Журнал алгебраической комбинаторики , 41 (2): 229–255, arXiv : 1302.6150 , doi : 10.1007/s10801-014-0534-5 , MR 3306071 , S2CID 7419411

[10] Холт, Д.Ф. (1974), «Неприкосновенные ладьи», The Mathematical Gazette , 58 (404): 131–134, doi : 10.2307/3617799 , JSTOR 3617799 , S2CID 250441965

[chm-11] Jump up to: ^а ^б ^с ^д Чола, С. ; Херштейн, Индиана ; Мур, WK (1951), «О рекурсиях, связанных с симметричными группами. I», Canadian Journal of Mathematics , 3 : 328–334, doi : 10.4153/CJM-1951-038-3 , MR 0041849 , S2CID 123802787

[12] Мозер, Лео ; Вайман, Макс (1955), "О решениях $x д = 1$ в симметричных группах», Canadian Journal of Mathematics , 7 : 159–168, doi : 10.4153/CJM-1955-021-8 , MR 0068564

[gfgt-13] Jump up to: ^а ^б ^с Бандерье, Сирил; Буске-Мелу, Мирей ; Дениз, Ален; Флажоле, Филипп ; Гарди, Даниэль; Гую-Бошам, Доминик (2002), «Производящие функции для генерации деревьев», Discrete Mathematics , 246 (1–3): 29–55, arXiv : math/0411250 , doi : 10.1016/S0012-365X(01)00250-3 , MR 1884885 , S2CID 14804110

[14] Ким, Донгсу; Ким, Чан Су (2010), «Комбинаторный подход к степени двойки в числе инволюций», Журнал комбинаторной теории , серия A, 117 (8): 1082–1094, arXiv : 0902.4311 , doi : 10.1016/j .jcta.2009.08.002 , MR 2677675 , S2CID 17457503

[15] Слоан, Нью-Джерси (редактор), «Последовательность A264737» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS

[16] Амдеберхан, Теодрос; Молл, Виктор (2015), «Инволюции и их потомки», Journal of Combinatorics , 6 (4): 483–508, arXiv : 1406.2356 , doi : 10.4310/JOC.2015.v6.n4.a5 , MR 3382606 , S2CID 119708272

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]