Telephone number (mathematics)

Last updated March 04, 2024

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$ )

Applications

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 $n$ -th 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

A diagonally symmetric non-attacking placement of eight rooks on a chessboard

In the mathematics of chess, the telephone numbers count the number of ways to place $n$ rooks on an $n \times 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]

Mathematical properties

Recurrence

The telephone numbers satisfy the recurrence relation

T(0)=1,

T(n)=T(n-1)+(n-1)T(n-2),\quad \mathrm {for~} n\geq 1,

first published in 1800 by Heinrich August Rothe, by which they may easily be calculated.^[1] One way to explain this recurrence is to partition the $T (n)$ connection patterns of the $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 $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 $n - 1$ choices for that person, and $T (n - 2)$ patterns of connection for the remaining $n - 2$ people, explaining the second term of the recurrence.^[11]

Summation formula and approximation

The telephone numbers may be expressed exactly as a summation

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!}}.

In each term of the first sum, $k$ gives the number of matched pairs, the binomial coefficient ${\tbinom {n}{2k}}$ counts the number of ways of choosing the $2k$ elements to be matched, and the double factorial

(2k-1)!!={\frac {(2k)!}{2^{k}\,k!}}

is the product of the odd integers up to its argument and counts the number of ways of completely matching the $2 k$ selected elements.^[1]^[11] It follows from the summation formula and Stirling's approximation that, asymptotically,^[1]^[11]^[12]

T(n)\sim \left({\frac {n}{e}}\right)^{n/2}{\frac {e^{\sqrt {n}}}{(4e)^{1/4}}}\,.

Generating function

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

G(x)=\sum _{n=0}^{\infty }{\frac {T(n)x^{n}}{n!}}=\exp \left(x+{\frac {x^{2}}{2}}\right).

In other words, the telephone numbers may be read off as the coefficients of the Taylor series of $exp(x + x 2 /2)$ and, in particular, the $n$ -th telephone number is the value at zero of the $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 $T (n)$ above, multiplying it by $x n -1 / (n - 1)!$ , and summing over $n \geq 1$ gives

\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)\,.

The general solution to this differential equation is $G (x) \propto exp(x + x 2 /2)$ , and $T (0) = 1$ shows that the constant of proportionality is 1.

This function is closely related to the exponential generating function of the Hermite polynomials, which are the matching polynomials of the complete graphs.^[13] The sum of absolute values of the coefficients of the $n$ -th (probabilist's) Hermite polynomial is the $n$ -th telephone number, and the telephone numbers can also be realized as certain special values of the Hermite polynomials:^[5]^[13]

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

Prime factors

For large values of $n$ , the $n$ -th 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]

2, 5, 13, 19, 23, 29, 31, 43, 53, 59, ... (sequence A264737 in the OEIS)

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

Related Research Articles

In number theory and combinatorics, a partition of a non-negative integer $n$ , also called an integer partition, is a way of writing $n$ as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, $4$ can be partitioned in five distinct ways:

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Catalan.

<span class="mw-page-title-main">Involution (mathematics)</span> Function that is its own inverse

In mathematics, an involution, involutory function, or self-inverse function is a function $f$ that is its own inverse,

In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials.

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

In mathematics, a pyramid number, or square pyramidal number, is a natural number that counts the number of stacked spheres in a pyramid with a square base. The study of these numbers goes back to Archimedes and Fibonacci. They are part of a broader topic of figurate numbers representing the numbers of points forming regular patterns within different shapes.

In mathematics, the $n$ th Motzkin number is the number of different ways of drawing non-intersecting chords between $n$ points on a circle. The Motzkin numbers are named after Theodore Motzkin and have diverse applications in geometry, combinatorics and number theory.

In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by $or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.$

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles.

In mathematics, poly-Bernoulli numbers, denoted as $, were defined by M. Kaneko as$

In combinatorial mathematics, an alternating permutation of the set {1, 2, 3, ..., n} is a permutation (arrangement) of those numbers so that each entry is alternately greater or less than the preceding entry. For example, the five alternating permutations of {1, 2, 3, 4} are:

<span class="mw-page-title-main">Eulerian number</span> Polynomial sequence

In combinatorics, the Eulerian number $is the number of permutations of the numbers 1 to in which exactly elements are greater than the previous element.$

<span class="mw-page-title-main">Ordered Bell number</span> Number of weak orderings

In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of $elements. Weak orderings arrange their elements into a sequence allowing ties, such as might arise as the outcome of a horse race). Starting from, these numbers are$

In combinatorial mathematics, a rook polynomial is a generating polynomial of the number of ways to place non-attacking rooks on a board that looks like a checkerboard; that is, no two rooks may be in the same row or column. The board is any subset of the squares of a rectangular board with m rows and n columns; we think of it as the squares in which one is allowed to put a rook. The board is the ordinary chessboard if all squares are allowed and m = n = 8 and a chessboard of any size if all squares are allowed and m = n. The coefficient of x^k in the rook polynomial R_B(x) is the number of ways k rooks, none of which attacks another, can be arranged in the squares of B. The rooks are arranged in such a way that there is no pair of rooks in the same row or column. In this sense, an arrangement is the positioning of rooks on a static, immovable board; the arrangement will not be different if the board is rotated or reflected while keeping the squares stationary. The polynomial also remains the same if rows are interchanged or columns are interchanged.

In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices $A$ with non-negative integer entries and pairs $(P, Q)$ of semistandard Young tableaux of equal shape, whose size equals the sum of the entries of $A$ . More precisely the weight of $P$ is given by the column sums of $A$ , and the weight of $Q$ by its row sums. It is a generalization of the Robinson–Schensted correspondence, in the sense that taking $A$ to be a permutation matrix, the pair $(P, Q)$ will be the pair of standard tableaux associated to the permutation under the Robinson–Schensted correspondence.

In combinatorics, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin

In the theory of permutation patterns, a skew-merged permutation is a permutation that can be partitioned into an increasing sequence and a decreasing sequence. They were first studied by Stankova (1994) and given their name by Atkinson (1998).

References

1 2 3 4 5 6 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
1 2 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, ISBN 1-4020-2633-1, 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, arXiv: 1302.6150 , 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
1 2 3 4 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 d = 1$ in symmetric groups", Canadian Journal of Mathematics , 7: 159–168, doi: 10.4153/CJM-1955-021-8 , MR 0068564
1 2 3 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.), "SequenceA264737", 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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[knuth-1] 1 2 3 4 5 6 Knuth, Donald E. (1973), The Art of Computer Programming, Volume 3: Sorting and Searching, Reading, Mass.: Addison-Wesley, pp. 65–67, MR 0445948

[2] Riordan, John (2002), Introduction to Combinatorial Analysis, Dover, pp. 85–86

[3] 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

[4] Getu, Seyoum (1991), "Evaluating determinants via generating functions", Mathematics Magazine, 64 (1): 45–53, doi:10.2307/2690455, JSTOR 2690455, MR 1092195

[sbdhp-5] 1 2 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, ISBN 1-4020-2633-1, S2CID 5702844

[6] 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

[7] 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

[b-8] 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

[9] Halverson, Tom; Reeks, Mike (2015), "Gelfand models for diagram algebras", Journal of Algebraic Combinatorics, 41 (2): 229–255, arXiv: 1302.6150 , doi: 10.1007/s10801-014-0534-5 , MR 3306071, S2CID 7419411

[10] Holt, D. F. (1974), "Rooks inviolate", The Mathematical Gazette, 58 (404): 131–134, doi:10.2307/3617799, JSTOR 3617799, S2CID 250441965

[chm-11] 1 2 3 4 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

[12] Moser, Leo; Wyman, Max (1955), "On solutions of $x d = 1$ in symmetric groups", Canadian Journal of Mathematics , 7: 159–168, doi: 10.4153/CJM-1955-021-8 , MR 0068564

[gfgt-13] 1 2 3 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

[14] 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

[15] Sloane, N. J. A. (ed.), "SequenceA264737", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation

[16] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]