The Statistic Pinv For Number System

The Statistic Pinv For Number System

Fanomezantsoa Patrick Rabarison

, Hery Randriamaro

Received 19 April 2019

Abstract

The number of inversions is a statistic on permutation groups measuring the degree to which the entries of a permutation are out of order. We provide a generalization of that statistic by introducing the statistic number of pseudoinversions on the colored permutation groups. The main motivation for studying that statistic is the possibility to use it to de…ne a number system and a numeral system on the colored permutation groups. By means of the statistic number ofi-pseudoinversions, we construct our number system, and a bijection between the set of positive integers and the colored permutation groups.

1 Introduction

A statistic over a group is a function from that group to the set of nonnegative integers. One of the most studied statistics is the number of inversions, de…ned by inv := # (i; j) 2 [n]² j i < j; (i) > (j) , on the symmetric groupS_n over[n]. A well-known result is the equidistribution ofinvwith the statistic major index proved by Foata [3]. Besides, the Lehmer code is based on that statistic. It is a particular way to encode each permutation of n numbers, and an instance of a scheme for numbering permutations.

Remark that Vajnovszki provided several permutation codes directly related to the Lehmer code [5]. In this article, we give a generalization of the statistic inv on the colored permutation group in order to create a more general code. The colored permutation group of m colors and n elements is the wreath product UmoS_nof the groupUmof allm^throots of unity by the symmetric groupS_n on[n]. We represent a colored permutation 2UmoS_n by

= 1 2 : : : n

k1 (1) _k2 (2) : : : _kn (n) with 2Sn and _kj =e^{2 ikjm}: Fori; j2Zsuch thati < j, let[i; j] :=fi; i+ 1; : : : ; jg.

De…nition 1 The number ofi-pseudoinversionsof 2UmoS_n is

pinv_i :=ki(n i+ 1) + j2[i+ 1; n] (i)> (j) : And the number of pseudoinversionsof 2UmoS_n is

pinv :=

Xn

i=1

pinv_i :

Example 1 Consider the element = 1 2 3 4

2 ₁1 ₄4 3 2U5oS₄. We havepinv₁ = 1,pinv₂ = 3, pinv₃ = 9,pinv₄ = 0, andpinv = 13.

The interest for investigating statistics onUmoS_n recently arised. Bagno et al., for example, introduced the statistics(c; d)-descents and computed their distributions [1, Proposition 1.1.]. We construct a number system by means of the cardinalityjUmoS_nj, and the statisticpinv_i.

Mathematics Sub ject Classi…cations: 05A19.

yDépartement de Mathématiques et Informatique, Université d’Antananarivo, 101 Antananarivo, Madagascar

zDépartement de Mathématiques et Informatique, Université d’Antananarivo, 101 Antananarivo, Madagascar

230

De…nition 2 LetA= (A_i)_i2N,a= (a_i)_i2Nbe two sequences of positive integers. The pair(A;a)is a number system if, for every integer n 2 N, there exists k 2 N such that n =

Xk

i=0

iAi with i 2 [0;ai], and this representation in terms ofAi’s and i’s is unique.

Using formal power series, Cantor provided a condition for a pair of positive integer sequences to be a number system [2, §.2.]. We provide a more suitable condition for this work.

Proposition 1 Let A= (A_i)i2N and a= (a_i)i2N be two sequences of strictly positive integers. The pair of sequences (A;a) is a number system if and only if

A₀= 1 and A_k =

kY1

i=0

(1 +a_i)for each k2N :

We prove Proposition 1in Section2.

Corollary 1 Let m2N . The pair of sequences(G;g) = (Gi)i2N;(gi)i2N de…ned by Gi=mⁱi! and gi=m(i+ 1) 1

is a number system.

Proof. We obtain the equality in Proposition1for number system from

kY1

i=0

(1 +g_i) =

kY1

i=0

m(i+ 1) =m^kk! =G_k:

We particularly use the number system(G;g)in this article. The numberGiis the cardinality ofUmoSi, and gi is the maximal value of pinv₁ relating to UmoSi+1. The factorial number system introduced by Laisant [4] corresponds to the casem = 1 of (G;g). We also construct a numeral system by means of the groupsUmoS_n and the statisticpinv_i.

De…nition 3 A numeral system is a notation for representing integers.

There exist several types of numeral systems depending on the historical context and the geographical location. We develop a numeral system based on the colored permutation groups. Write _{k k 1 1 0} for the integerPk

i=0 iGi, andhG;gi^k for the integer set

hG;gi^k := _{k k 1 1 0 i}2[0;gi] :

Our numeral system stems from the following bijection.

Theorem 1 Let n 1. The following map is bijective

g: UmoS_n ! hG;gi^{n 1}

7! pinv₁( ) pinv₂( ) pinv_n( ) : We prove Theorem 1in Section3. The Lehmer code is built from the casem= 1.

Example 2 From Example 1, we have = 1 2 3 4

2 ₁1 ₄4 3 = 1 3 9 0 which, is equal to 945 in decimal system.

Furthermore, we obtain the generating function of the statistic number of pseudoinversions. Denote the q-analog of the number iby[i]q := 1 +q+ +q^{i 1}.

Corollary 2 The generating function of the statistic pinvon UmoS_n is X

2U^moSn

q^pinv = Yn

i=1

[mi]_q:

Proof. The bijection of Theorem 1 implies that every element ofUmoS_n has a unique representation in hG;gin 1. Then, we have

X

2U^moSn

q^pinv = [maxpinv_n+ 1]q: : :[maxpinv₂+ 1]q[maxpinv₁+ 1]q= Yn

i=1

[mi]q:

2 Proof of Proposition 1

We provide a condition for a pair of integer sequences(A;a)to be a number system.

Lemma 1 Take a number system(A;a), and letn= k 1 0 be a nonnegative integer. Then,

kA_k n <( _k+ 1)A_k:

Proof. It is clear that _kA_k n. Suppose thatn ( _k+ 1)A_k which means

k 1

X

i=0

iA_i A_k. Then, there

exist _i’s,i2[0; k 1], such that 0 _{i i} and _{k 1 1 0}= 1

k tim es

z }| {

0 0 0. That contradicts the uniqueness of the representation.

Lemma 2 Let A = (A_i)i2N, a = (a_i)i2N be two sequences of positive integers. Then, the pair (A;a) is a number system if and only if

A0= 1 and Ak =

k 1

X

i=0

aiAi+ 1 for each k2N :

Proof. Suppose that(A;a)is a number system. It is obvious that we must haveA₀= 1. Letn=a_k a₁ a₀. From the second inequality of Lemma1, we get

Xk

i=0

aiAi=n <(ak+ 1)Ak. Then,

Xk

i=0

a_iA_i+ 1 (a_k+ 1)A_k i.e.

kX1

i=0

a_iA_i+ 1 A_k:

As

k 1

X

i=0

aiAi+ 12 h= A;ai^{k 1}, the only possibility is

kX1

i=0

aiAi+ 1 =Ak.

Now, suppose that A₀= 1 and A_k =

kX1

i=0

a_iA_i+ 1for eachk 2N . Let n2N , and assume that every

integer m n 1 has a unique representation _{k k 1 1 0} with _i 2[0;a_i]. Ifn 1 = Xk

i=0 iA_i,

letj= max l2[0; k] 8i2[0; l] : _i=a_i . Then,

n=A_j+1+ Xk

i=j+1 iA_i:

About the uniqueness, suppose thatnhas two di¤erent representations Xk

i=0

iAi and

k⁰

X

i=0 0iAi:

Ifk⁰> k, then

k⁰

X

i=0

0iA_i ⁰_k0A_k0 = ( ⁰_k0 1)A_k0+

kX⁰ 1

i=0

a_iA_i+ 1>

Xk

i=0 iA_i. Otherwise, let l= max i2[0; k] i6= ⁰_i , and assume that ⁰_l> l. We have

Xk

i=0 0iA_i=

l 1

X

i=0

0iA_i+ ⁰_lA_l+ Xk

i=l+1 0iA_i

Xk

i=l+1

0iA_i+ ⁰_lA_l

= Xk

i=l+1

iA_i+ ( ⁰_l 1)A_l+

l 1

X

i=0

a_iA_i+ 1

>

Xk

i=0 iA_i:

As that result is absurd, it is therefore impossible to have two di¤erent representions ofn.

We can now proceed to the proof of Proposition 1: From Lemma2, we deduce that(A;a)is a number system if and only ifA₀= 1and

Ak=

kX1

i=0

aiAi+ 1 =ak 1Ak 1+

k 2

X

i=0

aiAi+ 1 =ak 1Ak 1+Ak 1

=(a_{k 1}+ 1)A_{k 1}= (a_{k 1}+ 1)(a_{k 2}+ 1): : :(a₀+ 1) =

kY1

i=0

(1 +a_i):

3 Proof of Theorem 1

We …nally prove that there is a one-to-one correspondence betweenthe permutations

= 1 2 : : : n

k1 (1) _k2 (2) : : : _kn (n)

and the numbers _{n 1 n 2 1 0}by means ofpinv₁( ) pinv₂( ) pinv_n( ) = _{n 1 n 2 1 0}. Consider the function g : UmoSn !N de…ned by g( ) := pinv₁( ) pinv₂( ) pinv_n( ). Since ming= minhG;gi^{n 1}= 0andmaxg= maxhG;gi^{n 1}=Gn 1, theng(UmoSn) hG;gi^{n 1}. The surjectivity proof remains.

Consider the number _{n 1 n 2 1 0}2 hG;gi^{n 1}. Fori2[0; n 1], let hi be the integer in[0; m 1]such that _i2 hi(i+ 1); hi(i+ 1) +i ,

s_{n i} be the integer _i h_i(i+ 1)2[0; i].

We form a permutation 2S_n such that, for i2[n],si= j2[i+ 1; n] (i)> (j) .

Example 3 We compute the colored permutation inU4oS5corresponding to the number7 11 0 5 22 hG;gi⁴ forGi= 4ⁱi! andgi= 4i+ 3.

With slight calculations, we obtainh0= 2,h1= 2,h2= 0,h3= 2, andh4= 1.

Then, s₅= 0,s₄= 1,s₃= 0,s₂= 3, ands₁= 2.

Forx₅, we getx₁> x₂> x₃> x₄> (5).

Forx₄, we getx₁> x₂> x₃> (4)> (5).

Forx₃, we getx₁> x₂> (4)> (5)> (3).

Forx₂, we getx₁> (2)> (4)> (5)> (3).

Forx₁, we get (2)> (4)> (1)> (5)> (3).

Hence, = 1 2 3 4 5

3 5 1 4 2 , and the aimed colored permutation is 1 2 3 4 5

13 ₂5 ₀1 ₁4 ₂2 .

4 A Simple Example of Application

Here is an example of cryptosystem based on Theorem 1. Suppose that we want to encrypt a message of c characters using an alphabet of l symbols. Consider the colored permutation group UloS_c and its corresponding number systemhG;gic 1. The message can be considered as the elementx= _{c 1 1 0} of hG;gic 1, where _{c i} is the symbol order of the i^th character. Choose a key 2 UloS_c. De…ne the encrypting functione:hG;gi^{c 1}! hG;gi^{c 1} by the function composition

e: hG;gi^{c 1} ! UloSc ! UloSc ! hG;gi^{c 1}

x 7! g ¹(x) 7! g ¹(x) 7! g g ¹(x) :

The encrypted message isy=e(x). The decrypting function d:hG;gic 1! hG;gic 1 is de…ned by d: hG;gic 1 ! UloS_c ! UloS_c ! hG;gic 1

y 7! g ¹(y) 7! g ¹(y) ¹ 7! g g ¹(y) ¹ :

Example 4 We use the 26 letters of the English alphabet E as symbols. The message is written with the number system(G;g)as follows: a wordwnwn 1: : : w1 written with E is represented by _{n 1 n 2 0} where, if wi is the j^th letter of the alphabet, then _{i 1} = j 1. The message “pinv" is represented by 15 8 13 21corresponding to 1 2 3 4

34 ₂3 ₆2 ₂₁1 . Let us agree that, if the message is composed by n letters, then the key is the …rst n letters of a secret text. In our case, if that text is the abstract of this article, then the key is “then". Its representation is19 7 4 13corresponding to 1 2 3 4

44 ₂2 ₂1 ₁₃3 . Hence, the encrypted message is 1 2 3 4

251 ₄3 ₅4 ₁₉2 corresponding to100 13 11 19.

Acknowledgment. The authors are thankful to the International Centre for Theoretical Physics for having hosted them at the beginning of their research.

References

[1] E. Bagno, D. Garber and T. Mansour, Counting descent pairs with prescribed colors in the colored permutation groups, Sém. Lothar. Combin., 60(2009), Art. B60e, 12 pp.

[2] G. Cantor, Ueber die einfachen zahlensysteme, Z. Math. Phys., 14(1869), 121–128.

[3] D. Foata, On the netto inversion number of a sequence, Proc. Amer. Math. Soc., 19(1968), 236–240.

[4] C.-A. Laisant, Sur la numération factorielle, Application aux Permutations, Bull. Soc. Math. France, 16(1888), 176–183.

[5] V. Vajnovszki, Lehmer code transforms and mahonian statistics on permutations, Discrete Math., 313(2013), 581–589.