Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Propriedades Combinatórias de Permutações e Inversões

0 votos
17 visitas
perguntada Out 9 em Economia por CICERO FILHO (26 pontos)  
editado Out 9 por CICERO FILHO

Quando m é relativamente primo para n, sabemos que a sequência \((m\ mod\ n) (2m\mod n)… ((n - 1) m\ mod\ m)\) é uma permutação de \(\left\{1,2,...,n-1\right\}\). Mostre que o número de inversões desta permutação pode ser expresso em termos de somas de Dedekind.

Referência: Questão19 da seção 5.1.1 do cpítulo 5, página 19, do livro " The Art of Computer Programming" 2ed. Volume 3. Autor: Donald E. Knuth.

Referência adicional consultada:

Hadeed, I. S., & Salman, S. A. (2020). An algorithm for a modified computation of Dedekind sums. Journal of Al-Qadisiyah for computer science and mathematics, 12(1), Page-49.

Compartilhe

1 Resposta

0 votos
respondida Out 9 por CICERO FILHO (26 pontos)  
editado 4 dias atrás por CICERO FILHO

Em Dedekind sums, \(∀ a,b\) com \(b\geq1\):

\[s\left(a,b\right)=\sum_{kmodb}\left(\left(\frac{k}{b}\right)\right)\left(\left(\frac{ak}{b}\right)\right)\]

Onde \(∀ x∊R\) a função "dente de serra":

\[x=\begin{cases} x=0 x∊Z \\ x-x-\frac{-1}{2}\ de\ outra\ forma \\ \end{cases}\]

Assim, mostramos bijeção entre \(Z_{mm}^\ast\ \) e \(\ \ S-Z_m^\ast\ast Z_n^\ast\)

Então o teorema segue:
\[\emptyset\left(mn\right)=\left|Z_{mn}^\ast\right|=\left|s\right|\]

\[\left|Z_m^\ast\right|\left|Z_n^\ast\right|=Ø(m)Ø(n)\]

A objeção \( Ø: S→Z_{mn}^\ast\) é dada.

\[Ø: (a, b) →b_m+a_n\ mod\ mn\]

Precisamos provar que Ø é bijeção.

i) Mapa bem definido

Se \(a\in Z_m^\ast\ \ \) e\( \ \ b\in Z_n^\ast\), então, \(b_m+a_n\) em \(Z_{mn}^\ast\)

O resultado de \(b_m\) é um coprimo para \(n: b_m+a_n =\)coprimo para n

\(\approx b_m+a_n=\) coprimo para m então \(b_m+a_n=\)coprimo para \(mn\)

ii) Mapa one-one

Se \(b_m+a_n=b_m^\prime+a_n^\prime mod\ mn\) →\(\left(b-b^\prime\right)m+\left(a-a^\prime\right)n=c\ mod\ mn\).

Usando a coprimalidade temos que \(\frac{n}{b-b^\prime}\) e \(\frac{m}{a-a^\prime}\)

Então\(\left(a,b\right)=\left(a^\prime,b^\prime\right)\) em \(S\)

iii) O mapa onto

Considerando \(t\in Z_{mn}^\ast\), será calculado \(k=tm^{-1}mod\ n\)

\[\left(k\in Z_n^\ast\right)\]

Desde que \(k=k_m\mod\ n\), é possível escrever, \(t=k_m+l_n\).

Ao reduzir \(l\) para \(l’ mod\ m\), isso implica em \(t=k_m+l_n^\prime\ mod\ mn\) e \( l’∈Z_m^*\)

Portanto, \(Ø\) é um mapa bijetor e \(\emptyset\left(m\ast n\right)=\emptyset\left(m\right)\ast\emptyset\left(n\right)\).

Resolução em Python v1:

# usando a função da biblioteca itertools

from itertools import permutations
# Obtem todas as permutações de [1, 2, 3,.....,n-1]  
from math import inf 

perm = permutations([1, 2, 3, inf])

# Imprime as permutações

for i in list(perm):
    print(i)

    import math
    # Função para verificar se um número é primo ou não

def isPrime(n):
    if n <= 1:
        return False
    # Loop para verificar se esse número é divisível por qualquer outro número ou não, exceto 1
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    else:
        return True

    # Função para encontrar as permutações

def findPermutations(n):
    prime = 0
#Loop to find the 
    # number of prime numbers
    for j in range (1, n + 1):
        if isPrime(j):
            prime+= 1

Solução:

(1, 2, 3, inf)
(1, 2, inf, 3)
(1, 3, 2, inf)
(1, 3, inf, 2)
(1, inf, 2, 3)
(1, inf, 3, 2)
(2, 1, 3, inf)
(2, 1, inf, 3)
(2, 3, 1, inf)
(2, 3, inf, 1)
(2, inf, 1, 3)
(2, inf, 3, 1)
(3, 1, 2, inf)
(3, 1, inf, 2)
(3, 2, 1, inf)
(3, 2, inf, 1)
(3, inf, 1, 2)
(3, inf, 2, 1)
(inf, 1, 2, 3)
(inf, 1, 3, 2)
(inf, 2, 1, 3)
(inf, 2, 3, 1)
(inf, 3, 1, 2)
(inf, 3, 2, 1)
...