**The Telephone Numbers – Graph Theory**

The telephone numbers are the following sequence:

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496…

(where we start from n=0).

This pattern describes the total number of ways which a telephone exchange with n telephones can place a connection between pairs of people.

To illustrate this idea, the graph below is for n=4. This is when we have 10 telephones:

Each red line represents a connection. So the first diagram is for when we have no connections (this is counted in our sequence). The next five diagrams all show a single connection between a pair of phones. The last three diagrams show how we could have 2 pairs of telephones connected at the same time. Therefore the 4th telephone number is 10. These numbers get very large, very quickly.

**Finding a recursive formula**

The formula is given by the recursive relationship:

**T(n) = T(n-1) + (n-1)T(n-2)**

This means that to find (say) the 5th telephone number we do the following:

**T(5) = T(5-1) + (5-1)T(5-2)**

**T(5) = T(4) + (4)T(3)**

**T(5) = 10 + (4)4**

**T(5) = 26**

This is a quick way to work out the next term, as long as we have already calculated the previous terms.

**Finding an nth term formula
**

The telephone numbers can be calculated using the nth term formula:

This is going to be pretty hard to derive! I suppose the first step would start by working out the total number of connections possible between n phones – and this will be the the same as the graphs below:

These clearly follow the same pattern as the triangular numbers which is 0.5(n² +n) when we start with n = 1. We can also think of this as n choose 2 – because this gives us all the ways of linking 2 telephones from n possibilities. Therefore n choose 2 also generates the triangular numbers.

But then you would have to work out all the permutations which were allowed – not easy!

Anyway, as an example of how to use the formula to calculate the telephone numbers, say we wanted to find the 5th number:

We have n = 5. The summation will be from k = 0 and k = 2 (as 5/2 is not an integer).

Therefore T(5) = 5!/(2^{0}(5-0)!0!) + 5!/(2^{1}(5-2)!1!) + 5!/(2^{2}(5-4)!2!)

T(5) = 1 + 10 + 15 = 26.

**Finding telephone numbers through calculus**

Interestingly we can also find the telephone numbers by using the function:

y = e^{0.5x2+x}

and the nth telephone number (starting from n = 1) is given by the nth derivative when x = 0.

For example,

So when x = 0, the third derivative is 4. Therefore the 3rd telephone number is 4.

The fifth derivative of the function is:

So, when x =0 the fifth derivative is 26. Therefore the 5th telephone number is 26.

If you liked this post you might also like:

Fermat’s Theorem on the Sum of two Squares – A lesser known theorem from Fermat – but an excellent introduction to the idea of proof.

Unbelievable: 1+2+3+4…. = -1/12 ? A result that at first glance looks ridiculous – and yet can be shown to be correct. How?

## 1 comment

Comments feed for this article

September 29, 2014 at 5:18 am

dinabonaDon’t do this for your maths IA, whoever is reading this, take this as a warning. It is hell.