Telephone number (mathematics)

In mathematics, the telephone numbers or involution numbers are a sequence of integers that count the number of connection patterns in a telephone system with n subscribers, where connections are made between pairs of subscribers. 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, giving the values (starting from n = 0)

John Riordan provides the following explanation for these numbers: suppose that a telephone service has n subscribers, any two of whom may be connected to each other by a telephone call. 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. For this reason, the numbers counting how many patterns are possible are sometimes called the telephone numbers.

Every pattern of pairwise connections between n subscribers defines an involution, a permutation of the subscribers that is its own inverse, in which two subscribers who are making a call to each other are swapped with each other and all remaining subscribers stay 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 and these numbers have also been called involution numbers.

...
Wikipedia