Loading...

**M.M.M. University of Technology, Gorakhpur-273010 (UP) India**

**Applications of HCR’s Rank Formula** **15 March, 2014**

*

p<>{color:#000;}. **Circular to Linear Equivalence of Permutations:**

We are much familiar with the linear arrangements of different articles & their order of priority in linear fashions like alphabetic letters, digits & other things having different shape, size, colour, appearance, design etc. Any circular permutation having **singleton/non repetitive** **leading element**[***] can be changed into an equivalent linear permutation & its rank (position) in the set of all the circular permutations (both clockwise & anti-clockwise) obtained by permuting all the elements of that circular permutation, is computed by using HCR’s Rank Formula under some conditions. Each circular permutation may have two ranks one in clockwise & other in anti-clockwise sense depending on the condition of priority of as required. It depends on our desire to arrange the circular permutations according to either clockwise or anticlockwise ranks.

[***]**Leading element**: It is the element which leads or appears at the first or leftmost place in the predefined linear order/sequence of the elements. Ex. consider a set of circular permutations consisting of the letters N, N, P, M, L, K, Z, S, S, S. Then these letters have a (well known) predefined linear order i.e. alphabetic order as follows **.** Since, the letter **K** leads or appears at the first or leftmost place of the linear order so it is the **leading element** for given circular permutations. Now, the question arises that which circular permutation is equivalent to a linear permutation. Simply, any circular permutation having singleton/non repetitive leading element is equivalent to a linear permutation as in the above example **K** is the leading element which is **singleton/non repetitive** hence each of the circular permutations consisting of given elements K, L, M, N, N, P, S, S, S, Z is equivalent to a (unique) linear permutation whose rank can be easily determined by HCR’s rank formula in the desired sense of rotation.

Now, consider the circular permutations formed by the letters R, F, C, C, Y, U, U. The given letters have a predefined linear order i.e. alphabetic order **.** The letter **C** leads or appears at the first or leftmost place of linear order so it is the leading element but it repeats (twice) i.e. leading element C is not singleton hence none of the circular permutations formed by the letters C, C, F, R, U, U, Y is equivalent to a linear permutation and hence the ranks of such circular permutations having **repetitive leading element** can’t be determined using HCR’s rank formula.

*

p<>{color:#000;}. **Conditions for application of HCR’s Rank Formula on any circular permutation**

#

p<>{color:#000;}. All the elements in a given **circular permutation** must have a **pre-defined linear order** /**sequence**.

#

p<>{color:#000;}. **First (leading)/left-most element** in the **linear order** must be **singleton/non-repetitive** i.e. it must not repeat in the given circular permutation(s).

#

p<>{color:#000;}. Each of the set of circular permutations obtained by permuting all the elements together must have a sense of circulation (rotation) i.e. clockwise & anticlockwise circular permutations must be considered as to be the different permutations & all the circular permutations are assumed to be arranged in the same sense of ranking i.e. either all in clockwise or all in anti-clockwise ranks.

*

p<>{color:#000;}. **Derivation:** **Total Number () of circular permutations with at least one singleton element** is obtained by permuting ‘n’ no. of the elements out of which no. of the repetitive elements are p, q, r, s,…….. ,considering both clockwise & anti-clockwise permutations, is given by **HCR’s Rank Hypothesis**

Where,

But, **in any circular permutation**,

= total no. of the linear permutations obtained by elements out of which no. of the repetitive elements are , excluding any concerned element let it be taken from the group of p repetitive elements then we have

Hence, by setting the values of corresponding to the concerned element in the given circular permutation, total no. of the circular permutations is given as

Above is the **standard formula**, **to compute the total no. of the circular permutations (considering clockwise & anti-clockwise as distinct) obtained by permuting** **no. of the elements taken all at a time, out of which at least one element is singleton/non repetitive & numbers of the repetitive elements are**

*

p<>{color:#000;}. **Calculation of the rank (position) of any circular permutation in a set of all the circular permutations both clockwise & anti-clockwise**

**Working Steps:**

**Step 1:** Arrange all the elements (articles) in the correct linear order of their priority like alphabetic order of the letters, increasing or decreasing order of the digits etc. The first element in the linear order which is called **leading element** must be singleton/non-repetitive.

**Step 2:** Now, identify the leading element & consider the **desired sense of rotation** & write all the elements of given circular permutation, starting from the leading element, in a linear sequence. This linear sequence of elements we obtain is equivalent to the given circular permutation which is also called **equivalent linear permutation**[***].

**Step 3:** Now, apply the HCR’s Rank Formula on the equivalent linear permutation to calculate its rank & that will the rank of the given circular permutation in the desired sense of rotation.

[***]**Equivalent linear permutation:** The linear arrangement of the elements of a given circular permutation considered in the desired sense of rotation. It is obtained by writing all the elements of given circular permutation, starting from the leading element up to the last element, in a linear sequence.

**Illustrative Examples**

* Example 1*: Consider the following set of letters B, C, C, D, E, E, E, F, G. The total no. of the circular permutations obtained by permuting all these letters together is given as

Now, consider any of these circular permutations randomly to calculate its clockwise rank. As shown in the figure 1 below

First of all, arrange the letters B, C, C, D, E, E, E, F, G in linear order as The letter **B** is first & singleton/non-repetitive letter in above linear order hence it’s the **leading element** as **labelled** ([*B]) in the figure 1. Now, write all the letters in the linear fashion starting from first letter ‘B’ up to last one ‘E’ in clockwise sense (as indicated in the figure 1). Thus we get

**Figure 1: Consider all the elements in clockwise sense to get linear permutation to calculate clockwise rank of a circular permutation**

Now, applying **HCR’s Rank Formula** to get the rank of linear permutation BFECDECGE as follows

**It’s clear that the above circular** **permutation will lie at 2717**^**th**^ **position in the arrangement of all 3360 circular permutations according to the clockwise ranks.**

Now, let’s calculate its anti-clockwise rank. The letter **B** is **leading element** in linear alphabetic order as labelled ([*B]) in circular permutation in the figure 2. Now, write all the letters in the linear fashion starting from first letter ‘B’ up to last one ‘F’ in anti-clockwise sense (as indicated in the fig 2), we obtain

N

**Figure 2: Consider all the elements in anti-clockwise sense to get linear permutation to calculate clockwise rank of a circular permutation**
ow, applying **HCR’s Rank Formula** to get rank of the linear permutation BEGCEDCEF as follows

**It’s clear that the above circular permutation will lie at 2371**^**th**^ **position in the arrangement of all 3360 circular permutations according to the anti-clockwise ranks.**

* Example 2*: Consider the following set of letters A, B, B, B, C. The total no. of the circular permutations obtained by permuting all these letters together is given as

All the circular permutations obtained by permuting A, B, B, B, C together can be arranged according to their clockwise & anti-clockwise ranks as shown in the figure 3 below. In all these letters, ‘A’ is the leading element.

In all these letters, **A** is the **leading element** (appearing first & non-repetitive).

Ranks of all the circular permutations can be obtained by finding out the equivalent linear permutation corresponding to each of the circular permutations & applying HCRs Rank Formula

Clockwise ranks are calculated as follows

**Figure 3: Arrangement of all the circular permutations obtained by A, B, B, B, C in clockwise & anticlockwise ranks.**

Similarly, we can find out the anti-clockwise ranks of all the circular permutations & arrange them according to the desired sense of ranks either clockwise or anti-clockwise.

* Example 3*: Let’s consider a clockwise circular permutation as shown in the figure 4. It has 12 letters A, B, B, B, C, C, C, D, E, F, G, H which have the following linear order

Letter A is appearing first & non-repetitive letter hence it’s the **leading element**. Now, arrange all the letters/elements in the linear fashion starting from the leading element ‘A‘ up to last one ‘D’ in clockwise sense to get **equivalent linear permutation** as

T

**Figure 4: Circular permutation indicating clockwise sense of ranking**
he total no. of the circular permutations obtained by permuting all these letters together is given as

p<>{color:#000;}.

Now, applying **HCR’s Rank Formula** to calculate the rank of equivalent linear permutation AHGCFBECBCBD as follows

**It’s clear that the above circular permutation will lie at 1105185**^**th**^ **position in the arrangement of all 1108800 circular permutations according to the clockwise ranks.**

**Conclusion:** *HCR’s Rank Formula* can be easily applied on **all the circular permutations having singleton/non repetitive leading element** to compute their ranks in the desired sense of rotation both in clockwise & anticlockwise senses. The circular permutations having repetitive leading element are not equivalent to linear permutations and hence their ranks can’t be determined using rank formula.

**Note:** This article had been derived & illustrated by **Mr Harish Chandra Rajpoot****(B Tech, ME)****(Graduation from M.M.M. University of Technology, Gorakhpur (UP) India-273010)**

**Email:****[email protected]**

*For detailed explanation of HCR’s Rank or Series Formula, follow the link below*

[+ *http://www.researchpublish.com/journal/IJMPSR/Issue-1-October-2013-March-2014/0*+]

A circular permutation is essentially equivalent to a linear permutation when leading element (of given circular permutation) is singleton or non repetitive & the rank of such a circular permutation in which the first or leading element is singleton/non-repetitive is easily calculated by using HCR's Rank Formula applied on any linear permutation. Thus the rank of a circular permutation having singleton leading element is computed by the rank of equivalent linear permutation. In such cases, HCR's Rank Formula can be easily applied on circular permutations having singleton/non repetitive leading element.

- Author: HARISH CHANDRA RAJPOOT
- Published: 2016-10-22 23:35:10
- Words: 1623