Loading...
Menu

H. Rajpoot's formula to compute the rank of circular permutations

H. Rajpoot’s formula to compute the rank of linear permutation

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+]


H. Rajpoot's formula to compute the rank of circular permutations

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
H. Rajpoot's formula to compute the rank of circular permutations H. Rajpoot's formula to compute the rank of circular permutations