View source for Telephone number (mathematics)

{{good article}}
{{Short description|Number of ways to pair up n objects}}
{{pp|small=yes}}
{{about|the integer sequence|the phone network address|Telephone number}}
[[File:K4 matchings.svg|thumb|The [[complete graph]] {{math|''K''<sub>4</sub>}} has ten matchings, corresponding to the value {{math|1=''T''(4)&nbsp;=&nbsp;10}} of the fourth telephone number.|alt=Ten drawings, each of the complete graph on four vertices. Besides the top one, each drawing has some number of connecting edges highlighted. Highlighted edges are chosen such that none share a vertex.]]
In [[mathematics]], the '''telephone numbers''' or the '''involution numbers''' form a [[integer sequence|sequence of integers]] that count the ways {{mvar|n}} people can be connected by person-to-person telephone calls. These numbers also describe the number of [[matching (graph theory)|matchings]] (the [[Hosoya index]]) of a [[complete graph]] on {{mvar|n}} vertices, the number of [[permutation]]s on {{mvar|n}} elements that are [[involution (mathematics)|involution]]s, the sum of absolute values of coefficients of the [[Hermite polynomial]]s, the number of standard [[Young tableau]]x with {{mvar|n}} cells, and the sum of the degrees of the [[irreducible representation]]s of the [[symmetric group]]. Involution numbers were first studied in 1800 by [[Heinrich August Rothe]], who gave a [[recurrence equation]] by which they may be calculated,<ref name="knuth">{{citation
 | last = Knuth | first = Donald E. | author-link = Donald Knuth
 | location = Reading, Mass.
 | mr = 0445948
 | pages = 65–67
 | publisher = Addison-Wesley
 | title = [[The Art of Computer Programming]], Volume 3: Sorting and Searching
 | year = 1973}}</ref> giving the values (starting from {{math|1=''n'' = 0}})
{{bi|left=1.6|1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... {{OEIS|A000085}}.}}

==Applications==
[[John Riordan (mathematician)|John Riordan]] provides the following explanation for these numbers: suppose that {{mvar|n}} people subscribe to a telephone service that can connect any two of them by a call, but cannot make a single call connecting more than two people. How many different patterns of connection are possible? For instance, with three subscribers, there are three ways of forming a single telephone call, and one additional pattern in which no calls are being made, for a total of four patterns.<ref>{{citation
 | last = Riordan | first = John | author-link = John Riordan (mathematician)
 | pages = 85–86
 | publisher = Dover
 | title = Introduction to Combinatorial Analysis
 | year = 2002}}</ref> For this reason, the numbers counting how many patterns are possible are sometimes called the telephone numbers.<ref>{{citation
 | last1 = Peart | first1 = Paul
 | last2 = Woan | first2 = Wen-Jin
 | issue = 2
 | journal = Journal of Integer Sequences
 | mr = 1778992
 | at = Article 00.2.1
 | title = Generating functions via Hankel and Stieltjes matrices
 | url = http://www.emis.de/journals/JIS/VOL3/PEART/peart1.pdf
 | volume = 3
 | year = 2000| bibcode = 2000JIntS...3...21P
 }}</ref><ref>{{citation
 | last = Getu | first = Seyoum
 | doi = 10.2307/2690455
 | issue = 1
 | journal = Mathematics Magazine
 | mr = 1092195
 | pages = 45–53
 | title = Evaluating determinants via generating functions
 | volume = 64
 | year = 1991| jstor = 2690455
 }}</ref>

Every pattern of pairwise connections between {{mvar|n}} people defines an [[involution (mathematics)|involution]], a [[permutation]] of the people that is its own inverse. In this permutation, each two people who call each other are swapped, and the people not involved in calls remain fixed in place. Conversely, every possible involution has the form of a set of pairwise swaps of this type. Therefore, the telephone numbers also count involutions. The problem of counting involutions was the original [[combinatorial enumeration]] problem studied by Rothe in 1800<ref name="knuth"/> and these numbers have also been called involution numbers.<ref name="sbdhp">{{citation
 | last1 = Solomon | first1 = A. I.
 | last2 = Blasiak | first2 = P.
 | last3 = Duchamp | first3 = G.
 | last4 = Horzela | first4 = A.
 | last5 = Penson | first5 = K.A.
 | editor1-last = Gruber | editor1-first = Bruno J.
 | editor2-last = Marmo | editor2-first = Giuseppe
 | editor3-last = Yoshinaga | editor3-first = Naotaka
 | arxiv = quant-ph/0310174
 | contribution = Combinatorial physics, normal order and model Feynman graphs
 | doi = 10.1007/1-4020-2634-X_25
 | pages = 527–536
 | publisher = Kluwer Academic Publishers
 | title = Symmetries in Science XI
 | year = 2005| isbn = 1-4020-2633-1
 | s2cid = 5702844
 }}</ref><ref>{{citation
 | last1 = Blasiak | first1 = P.
 | last2 = Dattoli | first2 = G.
 | last3 = Horzela | first3 = A.
 | last4 = Penson | first4 = K. A.
 | last5 = Zhukovsky | first5 = K.
 | issue = 1
 | journal = Journal of Integer Sequences
 | mr = 2377567
 | at = Article 08.1.1
 | title = Motzkin numbers, central trinomial coefficients and hybrid polynomials
 | url = http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Penson/penson131.html
 | volume = 11
 | year = 2008| arxiv = 0802.0075
 | bibcode = 2008JIntS..11...11B
 }}</ref>

In [[graph theory]], a subset of the edges of a graph that touches each vertex at most once is called a [[matching (graph theory)|matching]]. Counting the matchings of a given graph is important in [[chemical graph theory]], where the graphs model molecules and the number of matchings is the [[Hosoya index]]. The largest possible Hosoya index of an {{mvar|n}}-vertex graph is given by the [[complete graph]]s, for which any pattern of pairwise connections is possible; thus, the Hosoya index of a complete graph on {{mvar|n}} vertices is the same as the {{mvar|n}}-th telephone number.<ref>{{citation
 | last1 = Tichy | first1 = Robert F.
 | last2 = Wagner | first2 = Stephan
 | doi = 10.1089/cmb.2005.12.1004
 | issue = 7
 | journal = [[Journal of Computational Biology]]
 | pages = 1004–1013
 | title = Extremal problems for topological indices in combinatorial chemistry
 | url = http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf
 | volume = 12
 | year = 2005
 | pmid = 16201918}}</ref>

[[File:Young tableaux for 541 partition.svg|thumb|A standard Young tableau|alt=Five squares on top of four squares on top of one square, all justified left. They read, from left to right, bottom to top: 1,2,4,7,8,3,5,6,9,10]]
A [[Ferrers diagram]] is a geometric shape formed by a collection of {{mvar|n}} squares in the plane, grouped into a [[polyomino]] with a horizontal top edge, a vertical left edge, and a single monotonic chain of edges from top right to bottom left. A standard [[Young tableau]] is formed by placing the numbers from 1 to {{mvar|n}} into these squares in such a way that the numbers increase from left to right and from top to bottom throughout the tableau.
According to the [[Robinson–Schensted correspondence]], permutations correspond one-for-one with ordered pairs of standard [[Young tableau]]x. Inverting a permutation corresponds to swapping the two tableaux, and so the self-inverse permutations correspond to single tableaux, paired with themselves.<ref name="b">A direct bijection between involutions and tableaux, inspired by the recurrence relation for the telephone numbers, is given by {{citation
 | last = Beissinger | first = Janet Simpson
 | doi = 10.1016/0012-365X(87)90024-0
 | issue = 2
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 913181
 | pages = 149–163
 | title = Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux
 | volume = 67
 | year = 1987| doi-access = free
 }}</ref> Thus, the telephone numbers also count the number of Young tableaux with {{mvar|n}} squares.<ref name="knuth"/> In [[representation theory]], the Ferrers diagrams correspond to the [[irreducible representation]]s of the [[symmetric group]] of permutations, and the Young tableaux with a given shape form a basis of the irreducible representation with that shape. Therefore, the telephone numbers give the sum of the degrees of the irreducible representations.<ref>{{citation
 | last1 = Halverson | first1 = Tom
 | last2 = Reeks | first2 = Mike
 | doi = 10.1007/s10801-014-0534-5
 | issue = 2
 | journal = Journal of Algebraic Combinatorics
 | mr = 3306071
 | pages = 229–255
 | title = Gelfand models for diagram algebras
 | volume = 41
 | year = 2015| s2cid = 7419411
 | doi-access = free
 | arxiv = 1302.6150
 }}</ref>

{{Chess diagram
| tright
|
|__|__|__|rl|__|__|__|__
|__|__|__|__|__|__|rl|__
|__|__|rl|__|__|__|__|__
|rl|__|__|__|__|__|__|__
|__|__|__|__|rl|__|__|__
|__|__|__|__|__|__|__|rl
|__|rl|__|__|__|__|__|__
|__|__|__|__|__|rl|__|__
|A diagonally symmetric non-attacking placement of eight rooks on a chessboard
}}
In the [[Mathematical chess problem|mathematics of chess]], the telephone numbers count the number of ways to place {{mvar|n}} rooks on an {{math|''n'' × ''n''}} [[chessboard]] in such a way that no two rooks attack each other (the so-called [[Eight queens puzzle|eight rooks puzzle]]), and in such a way that the configuration of the rooks is symmetric under a diagonal reflection of the board. Via the [[Pólya enumeration theorem]], these numbers form one of the key components of a formula for the overall number of "essentially different" configurations of {{mvar|n}} mutually non-attacking rooks, where two configurations are counted as essentially different if there is no symmetry of the board that takes one into the other.<ref>{{citation
 | last = Holt | first = D. F.
 | issue = 404
 | journal = The Mathematical Gazette
 | jstor = 3617799
 | pages = 131–134
 | title = Rooks inviolate
 | volume = 58
 | year = 1974| doi = 10.2307/3617799
 | s2cid = 250441965
 }}</ref>

==Mathematical properties==
===Recurrence===
The telephone numbers satisfy the [[recurrence relation]]
<math display=block>T(0) = 1,</math>
<math display=block>T(n) = T(n-1) + (n-1)T(n-2), \quad \mathrm{for~} n \ge 1,</math>
first published in 1800 by [[Heinrich August Rothe]], by which they may easily be calculated.<ref name="knuth"/>
One way to explain this recurrence is to partition the {{math|''T''(''n'')}} connection patterns of the {{mvar|n}} subscribers to a telephone system into the patterns in which the first person is not calling anyone else, and the patterns in which the first person is making a call. There are {{math|''T''(''n'' − 1)}} connection patterns in which the first person is disconnected, explaining the first term of the recurrence. If the first person is connected to someone, there are {{math|''n'' − 1}} choices for that person, and {{math|''T''(''n'' − 2)}} patterns of connection for the remaining {{math|''n'' − 2}} people, explaining the second term of the recurrence.<ref name="chm"/>

===Summation formula and approximation===
The telephone numbers may be expressed exactly as a [[summation]]
<math display=block>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!}.</math>
In each term of the first sum, <math>k</math> gives the number of matched pairs, the [[binomial coefficient]] <math>\tbinom{n}{2k}</math> counts the number of ways of choosing the <math>2k</math> elements to be matched, and the [[double factorial]]
<math display=block>(2k-1)!!=\frac{(2k)!}{2^k\,k!}</math> is the product of the odd integers up to its argument and counts the number of ways of completely matching the {{math|2''k''}} selected elements.<ref name="knuth"/><ref name="chm"/> It follows from the summation formula and [[Stirling's approximation]] that, [[Asymptotic analysis|asymptotically]],<ref name="knuth"/><ref name="chm">{{citation
 | last1 = Chowla | first1 = S. | author1-link = Sarvadaman Chowla
 | last2 = Herstein | first2 = I. N. | author2-link = Israel Nathan Herstein
 | last3 = Moore | first3 = W. K.
 | doi = 10.4153/CJM-1951-038-3
 | journal = [[Canadian Journal of Mathematics]]
 | mr = 0041849
 | pages = 328–334
 | title = On recursions connected with symmetric groups. I
 | volume = 3
 | year = 1951| s2cid = 123802787 | doi-access = free
 }}</ref><ref>{{citation
 | last1 = Moser | first1 = Leo | author1-link = Leo Moser
 | last2 = Wyman | first2 = Max
 | doi = 10.4153/CJM-1955-021-8
 | journal = [[Canadian Journal of Mathematics]]
 | mr = 0068564
 | pages = 159–168
 | title = On solutions of {{math|1=''x<sup>d</sup>'' = 1}} in symmetric groups
 | volume = 7
 | year = 1955| doi-access = free
 }}</ref>
<math display=block>T(n) \sim \left(\frac{n}{e}\right)^{n/2} \frac{e^{\sqrt{n}}}{(4e)^{1/4}}\,.</math>

===Generating function===
The [[exponential generating function]] of the telephone numbers is<ref name="chm"/><ref name="gfgt">{{citation
 | last1 = Banderier | first1 = Cyril
 | last2 = Bousquet-Mélou | first2 = Mireille | author2-link = Mireille Bousquet-Mélou
 | last3 = Denise | first3 = Alain
 | last4 = Flajolet | first4 = Philippe | author4-link = Philippe Flajolet
 | last5 = Gardy | first5 = Danièle
 | last6 = Gouyou-Beauchamps | first6 = Dominique
 | arxiv = math/0411250
 | doi = 10.1016/S0012-365X(01)00250-3
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1884885
 | pages = 29–55
 | title = Generating functions for generating trees
 | volume = 246
 | year = 2002| s2cid = 14804110
 }}</ref>
<math display=block>G(x) = \sum_{n=0}^{\infty}\frac{T(n)x^n}{n!}=\exp\left(x+\frac{x^2}{2}\right).</math>
In other words, the telephone numbers may be read off as the coefficients of the [[Taylor series]] of {{math|exp(''x'' + ''x''<sup>2</sup>/2)}} and, in particular, the {{mvar|n}}-th telephone number is the value at zero of the {{mvar|n}}-th derivative of this function.  The exponential generating function can be derived in a number of ways; for example, taking the recurrence relation for {{math|''T''(''n'')}} above, multiplying it by {{math|''x''<sup>''n''−1</sup> / (''n'' − 1)!}}, and summing over {{math|''n'' ≥ 1}} gives
<math display=block>\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}</math>
<math display=block>G'(x) = G(x) + x G(x)\,.</math>
The general solution to this differential equation is {{math|''G''(''x'') ∝ exp(''x'' + ''x''<sup>2</sup>/2)}}, and {{math|1=''T''(0) = 1}} shows that the constant of proportionality is 1.

This function is closely related to the exponential generating function of the [[Hermite polynomial]]s, which are the [[matching polynomial]]s of the complete graphs.<ref name="gfgt"/>
The sum of absolute values of the coefficients of the {{mvar|n}}-th (probabilist's) Hermite polynomial is the {{mvar|n}}-th telephone number, and the telephone numbers can also be realized as certain special values of the Hermite polynomials:<ref name="sbdhp"/><ref name="gfgt"/>
<math display=block>T(n)=\frac{\mathit{He}_n(i)}{i^n}.</math>

===Prime factors===
For large values of {{mvar|n}}, the {{mvar|n}}-th telephone number is divisible by a large [[power of two]], {{math|2<sup>''n''/4 + ''O''(1)</sup>}}. More precisely, the [[p-adic order|2-adic order]] (the number of factors of two in the [[prime factorization]]) of {{math|''T''(4''k'')}} and of {{math|''T''(4''k'' + 1)}} is {{mvar|k}}; for {{math|''T''(4''k'' + 2)}} it is {{math|''k'' + 1}}, and for {{math|''T''(4''k'' + 3)}} it is {{math|''k'' + 2}}.<ref>{{citation
 | last1 = Kim | first1 = Dongsu
 | last2 = Kim | first2 = Jang Soo
 | doi = 10.1016/j.jcta.2009.08.002
 | issue = 8
 | journal = [[Journal of Combinatorial Theory]] | series = Series A
 | mr = 2677675
 | pages = 1082–1094
 | title = A combinatorial approach to the power of 2 in the number of involutions
 | volume = 117
 | year = 2010| arxiv = 0902.4311
 | s2cid = 17457503
 }}</ref>

For any prime number {{mvar|p}}, one can test whether there exists a telephone number divisible by {{mvar|p}} by computing the recurrence for the sequence of telephone numbers, modulo {{mvar|p}}, until either reaching zero or [[Cycle detection|detecting a cycle]]. The primes that divide at least one telephone number are<ref>{{cite OEIS|A264737|mode=cs2}}</ref>
{{bi|left=1.6|2, 5, 13, 19, 23, 29, 31, 43, 53, 59, ... {{OEIS|A264737}}}}
The odd primes in this sequence have been called ''inefficient''. Each of them divides infinitely many telephone numbers.<ref>{{citation
 | last1 = Amdeberhan | first1 = Tewodros
 | last2 = Moll | first2 = Victor
 | arxiv = 1406.2356
 | doi = 10.4310/JOC.2015.v6.n4.a5
 | issue = 4
 | journal = Journal of Combinatorics
 | mr = 3382606
 | pages = 483–508
 | title = Involutions and their progenies
 | volume = 6
 | year = 2015| s2cid = 119708272
 }}</ref>

==References==
{{reflist|colwidth=30em}}

[[Category:Integer sequences]]
[[Category:Enumerative combinatorics]]
[[Category:Factorial and binomial topics]]
[[Category:Matching (graph theory)]]
[[Category:Permutations]]