Answer to Question #272498 in Discrete Mathematics for khan

Question

1. Discuss ways in which the current telephone numbering plan can be extended to accommodate the rapid demand for more telephone numbers. (See if you can find some of the proposals coming from the telecommunications industry.) For each new numbering plan you discuss, show how to find the number of different telephone numbers it supports.
2. Describe at least one way to generate all the partitions of a positive integer n. (You can get idea from Exercise 49 in Section 5.3.)
3. Proof that an undirected graph has an even number of vertices of odd degree.
4. In Exercises i) and ii) determine whether the given graph has a Hamilton circuit. If it does, find such a circuit. If it does not, give an argument to show why no such circuit exists.

Answer 1

1.

Telephone numbering system has some design strategies so that no

one get the same number means unique number.This design strategies

varies from country to country. For example :in India:

Landline format =area code+number

Mobile number = country code+10 digit number

As we know with the increase in technology, demands are also

increases which need an extending plan:

1)Relocating the existing numbers for paging services and

re-allocating some of the numbers in the “7(0-3)X” levels for

mobile services.

for X = n digits can support $4\cdot10^n$ numbers

2) Re-allocating numbers in the “4X” level for mobile services,

which will be able to release 5.6 million numbers to meet the

demand

for X = n digits can support $10^n$ numbers

3) Re-allocating vacant numbers in the “8(1-3)X” levels for

mobile services

for X = n digits can support $3\cdot10^n$ numbers

4) Raising the threshold of utilisation rate for allocation of

additional numbers to network operators, which will be able to

release 2.42 million numbers to meet the demand

5) Releasing most of the Special Number Blockss1for normal

allocation, which will be able to release a maximum of 3.52 million

numbers to meet the demand.

3.

Let G be a graph with e edges and n vertices v₁,v₂,v₃,...,v_n.

Since each edge is incident on two vertices, it contributes 2 to the sum of degree of vertices in graph G. Thus the sum of degrees of all vertices in G is twice the number of edges in G:$∑^n_{i=1}degree(v_i)=2e$

Let the degrees of first r vertices be even and the remaining (n−r) vertices have odd degrees, then:

$∑^n_{i=1}degree(v_i)=∑^r_{i=1}degree(v_i)+∑^n_{i=r+1}degree(v_i)$

$\implies ∑^n_{i=1}degree(v_i)+∑^r_{i=1}degree(v_i)$

$\implies ∑^n_{i=r+1}degree(v_i)$ is even.

But, the for $i=r+1,r+2,...,n$ each $d(v_i)$ is odd. So, the number of terms in

$∑^n_{i=r+1}degree(v_i)$ must be even. So, $(n-r)$ is even.

2.

A partition of a positive integer n is a multiset of positive integers that sum to n. We denote the number of partitions of n by p_n

we seek a product of factors so that when the factors are multiplied out, the coefficient of x_n

 is p_n. We would like each x_n term to represent a single partition, before like terms are collected. A partition is uniquely described by the number of 1s, number of 2s, and so on, that is, by the repetition numbers of the multiset. We devote one factor to each integer:

$(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)...(1+x^k+x^{2k}+x^{3k}+...)$

Each factor is a geometric series; the kth factor is

$1+x^k+x^{2k}+x^{3k}+...=\frac{1}{1-x^k}$

so the generating function can be written

$\displaystyle{\Pi}_{k=1}^n\frac{1}{1-x^k}$

4.

A simple graph with n vertices in which the sum of the degrees of any two non-adjacent vertices is greater than or equal to n has a Hamiltonian cycle.