In
mathematics, the **telephone numbers** or the **involution numbers** form a
sequence of integers that count the ways n people can be connected by person-to-person telephone calls. These numbers also describe the number of
matchings (the
Hosoya index) of a
complete graph on n vertices, the number of
permutations on n elements that are
involutions, the sum of absolute values of coefficients of the
Hermite polynomials, the number of standard
Young tableaux with n cells, and the sum of the degrees of the
irreducible representations 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,^{
[1]} giving the values (starting from *n* = 0)

John Riordan provides the following explanation for these numbers: suppose that 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.^{
[2]} For this reason, the numbers counting how many patterns are possible are sometimes called the telephone numbers.^{
[3]}^{
[4]}

Every pattern of pairwise connections between n people defines an
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^{
[1]} and these numbers have also been called involution numbers.^{
[5]}^{
[6]}

In
graph theory, a subset of the edges of a graph that touches each vertex at most once is called a
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 n-vertex graph is given by the
complete graphs, for which any pattern of pairwise connections is possible; thus, the Hosoya index of a complete graph on n vertices is the same as the nth telephone number.^{
[7]}

A
Ferrers diagram is a geometric shape formed by a collection of 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 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 tableaux. Inverting a permutation corresponds to swapping the two tableaux, and so the self-inverse permutations correspond to single tableaux, paired with themselves.^{
[8]} Thus, the telephone numbers also count the number of Young tableaux with n squares.^{
[1]} In
representation theory, the Ferrers diagrams correspond to the
irreducible representations 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.^{
[9]}

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 |

In the
mathematics of chess, the telephone numbers count the number of ways to place n rooks on an *n* × *n*
chessboard in such a way that no two rooks attack each other (the so-called
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 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.^{
[10]}

The telephone numbers satisfy the recurrence relation

first published in 1800 by
Heinrich August Rothe, by which they may easily be calculated.

The telephone numbers may be expressed exactly as a summation

In each term of the first sum, gives the number of matched pairs, the
binomial coefficient counts the number of ways of choosing the elements to be matched, and the
double factorial

is the product of the odd integers up to its argument and counts the number of ways of completely matching the 2

The
exponential generating function of the telephone numbers is^{
[11]}^{
[13]}

In other words, the telephone numbers may be read off as the coefficients of the
Taylor series of exp(

For large values of n, the nth telephone number is divisible by a large
power of two, 2^{n/4 + O(1)}. More precisely, the
2-adic order (the number of factors of two in the
prime factorization) of *T*(4*k*) and of *T*(4*k* + 1) is k; for *T*(4*k* + 2) it is *k* + 1, and for *T*(4*k* + 3) it is *k* + 2.^{
[14]}

For any prime number p, one can test whether there exists a telephone number divisible by p by computing the recurrence for the sequence of telephone numbers, modulo p, until either reaching zero or
detecting a cycle. The primes that divide at least one telephone number are^{
[15]}

The odd primes in this sequence have been called *inefficient*. Each of them divides infinitely many telephone numbers.^{
[16]}

- ^
^{a}^{b}^{c}^{d}^{e}^{f}Knuth, Donald E. (1973),*The Art of Computer Programming, Volume 3: Sorting and Searching*, Reading, Mass.: Addison-Wesley, pp. 65–67, MR 0445948 **^**Riordan, John (2002),*Introduction to Combinatorial Analysis*, Dover, pp. 85–86**^**Peart, Paul; Woan, Wen-Jin (2000), "Generating functions via Hankel and Stieltjes matrices" (PDF),*Journal of Integer Sequences*,**3**(2), Article 00.2.1, Bibcode: 2000JIntS...3...21P, MR 1778992**^**Getu, Seyoum (1991), "Evaluating determinants via generating functions",*Mathematics Magazine*,**64**(1): 45–53, doi: 10.2307/2690455, JSTOR 2690455, MR 1092195- ^
^{a}^{b}Solomon, A. I.; Blasiak, P.; Duchamp, G.; Horzela, A.; Penson, K.A. (2005), "Combinatorial physics, normal order and model Feynman graphs", in Gruber, Bruno J.; Marmo, Giuseppe; Yoshinaga, Naotaka (eds.),*Symmetries in Science XI*, Kluwer Academic Publishers, pp. 527–536, arXiv: quant-ph/0310174, doi: 10.1007/1-4020-2634-X_25, S2CID 5702844 **^**Blasiak, P.; Dattoli, G.; Horzela, A.; Penson, K. A.; Zhukovsky, K. (2008), "Motzkin numbers, central trinomial coefficients and hybrid polynomials",*Journal of Integer Sequences*,**11**(1), Article 08.1.1, arXiv: 0802.0075, Bibcode: 2008JIntS..11...11B, MR 2377567**^**Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF),*Journal of Computational Biology*,**12**(7): 1004–1013, doi: 10.1089/cmb.2005.12.1004, PMID 16201918**^**A direct bijection between involutions and tableaux, inspired by the recurrence relation for the telephone numbers, is given by Beissinger, Janet Simpson (1987), "Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux",*Discrete Mathematics*,**67**(2): 149–163, doi: 10.1016/0012-365X(87)90024-0, MR 0913181**^**Halverson, Tom; Reeks, Mike (2015), "Gelfand models for diagram algebras",*Journal of Algebraic Combinatorics*,**41**(2): 229–255, doi: 10.1007/s10801-014-0534-5, MR 3306071, S2CID 7419411**^**Holt, D. F. (1974), "Rooks inviolate",*The Mathematical Gazette*,**58**(404): 131–134, doi: 10.2307/3617799, JSTOR 3617799, S2CID 250441965- ^
^{a}^{b}^{c}^{d}Chowla, S.; Herstein, I. N.; Moore, W. K. (1951), "On recursions connected with symmetric groups. I",*Canadian Journal of Mathematics*,**3**: 328–334, doi: 10.4153/CJM-1951-038-3, MR 0041849, S2CID 123802787 **^**Moser, Leo; Wyman, Max (1955), "On solutions of*x*= 1 in symmetric groups",^{d}*Canadian Journal of Mathematics*,**7**: 159–168, doi: 10.4153/CJM-1955-021-8, MR 0068564- ^
^{a}^{b}^{c}Banderier, Cyril; Bousquet-Mélou, Mireille; Denise, Alain; Flajolet, Philippe; Gardy, Danièle; Gouyou-Beauchamps, Dominique (2002), "Generating functions for generating trees",*Discrete Mathematics*,**246**(1–3): 29–55, arXiv: math/0411250, doi: 10.1016/S0012-365X(01)00250-3, MR 1884885, S2CID 14804110 **^**Kim, Dongsu; Kim, Jang Soo (2010), "A combinatorial approach to the power of 2 in the number of involutions",*Journal of Combinatorial Theory*, Series A,**117**(8): 1082–1094, arXiv: 0902.4311, doi: 10.1016/j.jcta.2009.08.002, MR 2677675, S2CID 17457503**^**Sloane, N. J. A. (ed.), "Sequence A264737",*The On-Line Encyclopedia of Integer Sequences*, OEIS Foundation**^**Amdeberhan, Tewodros; Moll, Victor (2015), "Involutions and their progenies",*Journal of Combinatorics*,**6**(4): 483–508, arXiv: 1406.2356, doi: 10.4310/JOC.2015.v6.n4.a5, MR 3382606, S2CID 119708272