THE TELEPHONE EXCHANGE PROBLEM REVISITED: A combinatorial approach

Sithembele Nkonkobe · 2025

Read THE TELEPHONE EXCHANGE PROBLEM REVISITED: A combinatorial approach by Sithembele Nkonkobe (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-05145.txt.

Introduction

Sithembele Nkonkobe returns to the telephone exchange problem in a 2025 math paper. The classic problem counts the ways callers can be linked through an exchange, and its counts tie to a known family of Bessel polynomials. Nkonkobe builds two wider families of those polynomials and studies their traits. He shows how their counts link to Whitney numbers and to Dowling numbers, two known count sets. A phone network puzzle thus sits at a cross of counting worlds.

Catalog record

CREATORSithembele Nkonkobe
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-05145

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

THE TELEPHONE EXCHANGE PROBLEM REVISITED: A combinatorial approach Sithembele Nkonkobe Abstract . In this study we revisit the telephone exchange problem. We discuss a generalization of the telephone exchange problem by discussing two generalizations of the Bessel numbers. We study combinatorial properties of these numbers and show how these numbers are related to the well-known Whitney numbers and Dowling numbers. 1. Introduction The Bessel polynomials are defined as the unique solutions of the differential equation (see [ 9 , 12 , 18 , 26 ] ) (1) x^{2}y^{\prime\prime}_{n}+(2x+2)y^{\prime}_{n}=n(n+1)y_{n}, which is a Sturm-Liouville type second order differential equation. These polynomials seem to first appeared in the year 1929 paper [ 4 ] . The first systematic study of these polynomials seems to first been done by Krall and Frink in their 1949 paper [ 18 ] . It is known that the Bessel polynomial y_{n}(x) may be written in the form y_{n}(x)=\sum\limits_{k=0}^{\infty}B_{n,k}x^{n-k} where B_{n,k}=\frac{(2n-k)!}{2^{n-k}k!(n-k)!} , see, for instance, [ 9 ] . The numbers B_{n,k} are known as the Bessel coefficients. For non-negative integers n and k , the (n,k)th Bessel number of the second kind B(n,k) is defined as the Bessel coefficient B_{k,2k-n} (see [ 9 ] ). The generating function of the Bessel numbers of the second kind, B(n,k) , is [ 26 ] (2) \sum\limits_{n=0}^{\infty}B(n,k)\frac{z^{n}}{n!}=\frac{1}{k!}\begin{pmatrix}z+\frac{z^{2}}{2}\end{pmatrix}^{k}. The Bessel numbers of the second kind B(n,k) have the following combinatorial interpretation: They represent the total number of ways of partitioning the set [n]=\{1,2,\ldots,n\} into k non-empty subsets each subset having cardinality of at most two [ 8 , 9 ] . One of the problems of interest in enumerative combinatorics is the telephone exchange problem. The telephone exchange problem is as follows. Definition 1.1 (Telephone exchange problem) . [ 23 ] Suppose a telephone exchange has n subscribers, in how many ways can the subscribers be connected satisfying the following conditions; a). subscribers may be connected in pairs only i.e. no conference calls are allowed, b). each of the n subscribers is in one of two states; connected to exactly one other subscriber or not connected to any other subscriber at all. Definition 1.2 . We denote by (i,j) to denote that subscribers i , and j are connected with each other, where i and j are from the set [n] . We also denote by \overline{i} to denote that subscriber i is not connected to any other subscriber. We let T_{n} be the total number of possible configurations in Definition 1.1 . We refer to the numbers T_{n} as telephone numbers. It turns out that the number of ways in which n-k pairs out of n subscribers can be connected by a telephone exchange is given by the Bessel numbers B(n,k) [ 8 ] . It is known that the telephone numbers T_{n} have the following closed form, T_{n}=\sum\limits^{n}_{k=0}B(n,k) where B(n,k) are the Bessel numbers discussed above, see, for instance, [ 15 , 20 ] . Example 1.1 . We demonstrate the possibilities for two telephone numbers. For T_{2} we have the following possibilities (i) \overline{1} , \overline{2} , (ii) (1,2) . Hence T_{2}=2 . For T_{3} we have the following possibilities (i) \overline{1} , \overline{2} , \overline{3} , (ii) \overline{1} , (2,3) , (iii) \overline{2} , (1,3) , (iv) \overline{3} , (1,2) . Hence, T_{3}=4 . In general we have the following n 0 1 2 3 4 5 6 7 8 \cdots T_{n} 1 1 2 4 10 26 76 232 764 \cdots Table 1. Telephone numbers T_{n} . The telephone exchange problem has a reach history, see, for instance, [ 8 , 9 ] and references therein. The telephone exchange problem seem to first appeared in Riordan’s book [ 23 ] . There are several alternative interpretations of the telephone numbers. The telephone numbers T_{n} also represent the Hosoya index (number of matchings) of the complete graph K_{n} [ 26 ] . They also represent the number of involutions of the symmetric group S_{n} [ 2 , 5 , 24 , 25 ] . They also represent the total number of tableaux that can be formed from n distinct elements [ 11 ] . The Hermite polynomials are defined in the following way [ 3 ] (3) \sum\limits_{n=0}^{\infty}H_{e_{n}}(x)\frac{t^{n}}{n!}=exp\begin{bmatrix}xt-\frac{t^{2}}{2}\end{bmatrix}. Also, the numbers T_{n} are related to the hermit polynomials in the following way (see [ 3 ] ) (4) T_{n}=i^{n}H_{e_{n}}(-i),\qquad i=\sqrt{-1}. Equation 4 means that the telephone numbers are the absolute values of the coefficients of the Hermite polynomials. A problem that can be considered as a generalization of the telephone number problem is that of the restricted Bell numbers studied in [ 20 ] , which restrict the number of elements each subsets may have. Definition 1.3 . A generalization of the Bessel numbers of the second kind B(n,k) , which is the r -Bessel numbers of second kind B_{r}(n,k) represents the number of partitions of [n+r] elements into k+r subsets of size one or two such that the first r elements are in distinct blocks [ 15 ] . We denote by B_{r}(n) the total number of all such possible configurations where k runs from 0 to n . The n+r elements denote n+r subscribers. We will refer to the first r subscribers the distinguished subscribers, and the rest as non-distinguished subscribers. The numbers B_{r}(n,k) have the following generating function(see [ 15 ] ), (5) \sum\limits_{n=0}^{\infty}B_{r}(n,k)\frac{z^{n}}{n!}=\frac{1}{k!}(1+z)^{r}\begin{pmatrix}z+\frac{z^{2}}{2}\end{pmatrix}^{k}. The Bessel numbers B_{r}(n,k) can alternatively be interpreted in the following way. Suppose G is a complete semi-bipartite graph having bipartitions V_{1}=\{1,2,\ldots,r\} , and V_{2}=\{r+1,r+2,\ldots,n+r\} , then B_{r}(n,k) is the number of matchings of G having n-k edges [ 8 ] . From Definition 1.3 we have B_{r}(n)=\sum\limits_{k=0}^{n}B_{r}(n,k) . We have (see [ 8 ] ) (6) \sum\limits_{n=0}^{\infty}B_{r}(n)\frac{z^{n}}{n!}=(1+z)^{r}e^{z+z^{2}/2}. We will refer to the numbers B_{r}(n) as the r -Bessel numbers. We denote by i_{r} to indicate that the element i is one of the first r elements. Example 1.2 . We note that for B_{2}(2) we have \{1_{2},2_{2},1,2\} . The eight partitions given by B_{2}(2) are: (1) \{1_{2}\}\{2_{2}\}\{1,2\} , (2) \{1_{2}\}\{2_{2}\}\{1\}\{2\} , (3) \{1_{2},1\}\{2_{2}\}\{2\} , (4) \{1_{2},2\}\{2_{2}\}\{1\} , (5) \{1_{2},2\}\{2_{2},1\} , (6) \{1_{2}\}\{2_{2},2\}\{1\} , (7) \{1_{2}\}\{2_{2},1\}\{2\} , (8) \{1_{2},2\}\{2_{2},1\} . It turns out that B_{2}(n) has the following sequence n 0 1 2 3 4 5 6 7 8 \cdots B_{2}(n) 1 3 8 22 66 206 688 2388 8732 \cdots Table 2. The numbers B_{2}(n) . Another generalization of the Bessel Numbers related to the telephone exchange problem is the following (see [ 8 ] ) (7) \sum\limits_{n=0}^{\infty}T_{r}(n,k)\frac{z^{n}}{n!}=e^{rz}\frac{(z+z^{2}/2)^{k}}{k!}. Definition 1.4 . The numbers T_{r}(n,k) represent the number of ways of selecting n-k pairs (number of connections) out of n+r subscribers where r pre-specified subscribers cannot be connected with each other, however every conference call involves one of these r subscribers [ 8 ] . We will refer to the r subscribers as the distinguished subscribers, and the rest as non-distinguished subscribers. We denote by T_{r}(n) the total number of all possible such configurations, where k runs from 0 to n . The numbers T_{r}(n)=\sum\limits_{k=0}^{n}T_{r}(n,k) , have also been studied in [ 8 ] . We have (see [ 8 ] ) (8) \sum\limits_{n=0}^{\infty}T_{r}(n)\frac{z^{n}}{n!}=e^{(r+1)z+z^{2}/2}. Remark 1.1 . Note that in the context of subsets the main difference between the subsets

Read the complete text