Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Cikličke permutacije - Möbiusova funkcija

[es] :: Matematika :: Cikličke permutacije - Möbiusova funkcija

[ Pregleda: 3698 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Ivan_HR

Član broj: 87291
Poruke: 142
*.cmu.carnet.hr.



Profil

icon Cikličke permutacije - Möbiusova funkcija15.05.2006. u 21:05 - pre 217 meseci
Što je to Möbiusova funkcija gdje na webu mogu pronaći više o tome i dali mi neko može riješiti ovaj zadatak, trebam za seminar!? Hvala

Za k = 3 (najviše tri boje) i n = 5 bisera odrediti broj (različitih ogrlica) cikličkih permutacija!

Evo tu je cijeli seminar ako nekom nije jasno što želim! Trebam samo zadnji primjer riješit!

[Ovu poruku je menjao Ivan_HR dana 15.05.2006. u 22:08 GMT+1]
...trying to do my best...
Prikačeni fajlovi
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: Cikličke permutacije - Möbiusova funkcija17.05.2006. u 22:48 - pre 217 meseci
Möbius-ova funkcija se definiše na skupu na sledeći način:

Neka je faktorizacija broja na proste činioce, onda je


Specijalno, uzima se da je .

Drugim rečima, f-ja je jednaka nuli za one brojeve koji su deljivi kvadratom nekog broja (većeg od 1), a za brojeve koji su jednaki proizvodu recimo različitih prostih brojeva je jednaka ili u zavisnosti od parnosti broja .

Očigledno je da je multiplikativna f-ja jer pored već pomenutog važi i kad god su i uzajamno prosti.

Najčešće korišćena teorema u vezi sa ovom f-jom je tzv. Möbius-ova formula inverzije (koju si ti? i upotrebio kada si računao ).

Dirichlet-ov proizvod dve aritmetičke f-je (to su one čiji je domen a kodomen ) se definiše sa:



Očigledno je da važi .
Lako je pokazati da je ovako definisan proizvod aritmetičkih f-ja asocijativan tj. da za proizvoljne aritm. f-je važi

Pre nego što dođemo do formulacije Möbius-ove formule inverzije i njenog dokaza pogledajmo još dve f-je:





Jasno je da su obe f-je multiplikativne.

Na osnovu definicija odmah sledi da za svaku aritm. f-ju važi:

1.

2.

Lema
Ako je multiplikativna f-ja i ako je faktorizacija broja na proste činioce, onda važi:



Dokaz.

Ako je desna strana se (kao što je za proizvode i uobičajeno) tumači kao 1 pa jednakost važi.

Ako je , na osnovu definicije Möbius-ove f-je, jasno je da će se u sumi efektivno pojavljivati samo članovi kod kojih je tj. članovi oblika pa je suma (uzmemo li u obzir ) upravo jednaka desnoj strani jednakosti zapisanoj u razvijenom obliku.

Specijalno, ako stavimo da je (multiplikativnost je očigledna) dobijamo da je
.

Još jedan važan primer dobijamo ako stavimo .



Dakle, dobili smo da važi .

Najzad:

Teorema (Möbius-ova formula inverzije)

Ako su i aritmetičke f-je, onda važi:

.

Dokaz.

Ako je , onda posle množenja te jednakosti sleva f-jom , dobijamo
.

Obrnuto, ako je , onda posle množenja te jednakosti sleva f-jom , dobijamo


Ako se prisetimo kako je definisana operacija vidimo da se ova teorema može iskazati i ovako:




Ostaje da obrazložimo još jedan argument korišćen u tvom radu:

Budući da važi odmah vidimo (na osnovu onog drugog primera u vezi sa Lemom) da važi i

tj.
međutim, kad god , tada i pa je poslednja suma zapravo jednaka sumi .


Konačno da bi rešio postavljeni zadatak dovoljno je da primeniš MacMahon-ovu formulu




Inače, MacMahon je ovaj zadatak rešio 1892. u radu Application of a theory of permutations in circular procession to the theory of numbers, Proceedings of the London Mathematical Society 23 (1892), 305-313 a jedno od rešenja možeš naći i u knjizi Concrete mathematics, R. Graham, D. Knuth, O. Patashnik.



[Ovu poruku je menjao uranium dana 18.05.2006. u 06:52 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

Ivan_HR

Član broj: 87291
Poruke: 142
*.cmu.carnet.hr.



Profil

icon Re: Cikličke permutacije - Möbiusova funkcija18.05.2006. u 13:02 - pre 217 meseci
E puno hvala na odgovoru, probat ću to sad malo proučit što mi je napisano pa javim ako bude bilo problema! Ali glavno da mi je zadatak riješen! Još jednom puuuno puuuno hvala! Trebalo mi je ovo za ispi!
...trying to do my best...
 
Odgovor na temu

[es] :: Matematika :: Cikličke permutacije - Möbiusova funkcija

[ Pregleda: 3698 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.