Burnsiden lemma

Seuraa 
Viestejä2350
Liittynyt27.12.2008

Burnsiden lemma.
Törmäsin seuraavaan tehtävään.
Kuinka monta erilaista helminauhaa voit valmistaa, jos jokaiseen helminauhaan käytät 5 sinistä 3 punaista ja 3 keltaista helmeä. Helminauhojen pitää siis olla erilaisia vaikka niitä kuinka kääntelisi ja pyörittelisi.
Kovalla työllä sain tuloksen aikaiseksi. Muut viisaammat pääsivät helpommalla, he käyttivät Burnsiden lemmaa apunaan. (tosin heidän tuloksensa oli väärä, luullakseni)
Itsekin innostuin katsomaan tätä lemmaa, lähinnä Wikin sivuilta. http://en.wikipedia.org/wiki/Burnside's_lemma
En käsitä edes tätä yksinkertaista esimerkkitapausta kolmivärisestä kuutiosta.
"six 90-degree face rotations, each of which leaves 33 of the elements of X unchanged"
Mitä tällä "leaves 33 of the elements of X unchanged" oikein tarkoitetaan ja mistä se tulee. Sama tietenkin kolmessa muussa tapauksessa. Ensimmäinen kolmonen lie värien lukumäärä, mutta exponentti, mistä se tempaistaan?

Sivut

Kommentit (38)

visti
Seuraa 
Viestejä6331
Liittynyt16.11.2009
Jorma
Burnsiden lemma.
Törmäsin seuraavaan tehtävään.
Kuinka monta erilaista helminauhaa voit valmistaa, jos jokaiseen helminauhaan käytät 5 sinistä 3 punaista ja 3 keltaista helmeä. Helminauhojen pitää siis olla erilaisia vaikka niitä kuinka kääntelisi ja pyörittelisi.
Kovalla työllä sain tuloksen aikaiseksi. Muut viisaammat pääsivät helpommalla, he käyttivät Burnsiden lemmaa apunaan. (tosin heidän tuloksensa oli väärä, luullakseni)
Itsekin innostuin katsomaan tätä lemmaa, lähinnä Wikin sivuilta. http://en.wikipedia.org/wiki/Burnside's_lemma
En käsitä edes tätä yksinkertaista esimerkkitapausta kolmivärisestä kuutiosta.
"six 90-degree face rotations, each of which leaves 33 of the elements of X unchanged"
Mitä tällä "leaves 33 of the elements of X unchanged" oikein tarkoitetaan ja mistä se tulee. Sama tietenkin kolmessa muussa tapauksessa. Ensimmäinen kolmonen lie värien lukumäärä, mutta exponentti, mistä se tempaistaan?



Olisi helkutin mielenkiintoinen juttu, mutta v*** ei pysty ainakaan kylmiltään. Olisi mukava, jos joku pystyisi antamaan lemman käytöstä pari alkeellista esimerkkiä.

Vierailija

Burnsiden lemman soveltamiseen tarvitsee laskea jokaiselle permutaatiolle fiksattu joukko, eli se operoitavien alkioiden joukko, joka on kuvautuu permutaatiolla itselleen (tarkkaan ottaen vielä sen tarkasteltavan symmetrian asettaman ekvivalenssirelaation suhteen).

Jos ajatellaan 90 asteen kääntöä myötäpäivään vaikkapa ylä- ja alatahkon keskipisteet symmetria-akselina, niin kääntöhän säilyttää ylä- ja alatahkon paikoillaan. Toisaaltaan etu- ja takatahkot ja sivutahkot vaihtavat paikkaa keskenään. Jotta tämä permutaatio kuvaisi kuution itselleen (symmetrian suhteen), niin täytyy etu-, taka- ja sivutahkot olla yhtä ja samaa väriä. Siis värivalinnat voidaan tehdä 3 eri tavalla ja silti saada tämän permutaation samana säilyttämiä kuutioita. Siis fiksatussa joukossa on 3^3 alkiota.

Jos taas ajatellaan 180 asteen kääntöä myötäpäivään vaikkapa ylä- ja alatahkon keskipisteet symmetria-akselina, niin kääntöhän säilyttää ylä- ja alatahkon paikoillaan. Toisaalta etu- ja sivutahkot vaihtavat keskenään paikkaa ja sivutahkot vaihtavat keskenään paikkaa. Siis värivalinnat voidaan tehdä 4 eri tavalla ja saada tämän permutaation suhteen sama kuutio. Siis fiksatussa joukossa on 3^4 alkiota.

Jorma
Seuraa 
Viestejä2350
Liittynyt27.12.2008
starless
Burnsiden lemman soveltamiseen tarvitsee laskea jokaiselle permutaatiolle fiksattu joukko, eli se operoitavien alkioiden joukko, joka on kuvautuu permutaatiolla itselleen (tarkkaan ottaen vielä sen tarkasteltavan symmetrian asettaman ekvivalenssirelaation suhteen).

Jos ajatellaan 90 asteen kääntöä myötäpäivään vaikkapa ylä- ja alatahkon keskipisteet symmetria-akselina, niin kääntöhän säilyttää ylä- ja alatahkon paikoillaan. Toisaaltaan etu- ja takatahkot ja sivutahkot vaihtavat paikkaa keskenään. Jotta tämä permutaatio kuvaisi kuution itselleen (symmetrian suhteen), niin täytyy etu-, taka- ja sivutahkot olla yhtä ja samaa väriä. Siis värivalinnat voidaan tehdä 3 eri tavalla ja silti saada tämän permutaation samana säilyttämiä kuutioita. Siis fiksatussa joukossa on 3^3 alkiota.

Jos taas ajatellaan 180 asteen kääntöä myötäpäivään vaikkapa ylä- ja alatahkon keskipisteet symmetria-akselina, niin kääntöhän säilyttää ylä- ja alatahkon paikoillaan. Toisaalta etu- ja sivutahkot vaihtavat keskenään paikkaa ja sivutahkot vaihtavat keskenään paikkaa. Siis värivalinnat voidaan tehdä 4 eri tavalla ja saada tämän permutaation suhteen sama kuutio. Siis fiksatussa joukossa on 3^4 alkiota.


Ei selvinnyt.
Ensimmäinen osa 90 asteen kääntöineen vaikutti jo siltä kuin alkaisin ymmärtää, sitten tämä 180 asteen kääntyminen. Eikös siinä pitäisi olla 9 erilaista tapaa värjätä tahkot.
3 kertaa kaikki samaa väriä ja 6 kertaa vastakkaiset samaa väriä?

Vierailija

Jos kuution tahkoja merkitään luvuilla seuraavasti:

1 = ylätahko
2 = alatahko
3 = etutahko
4 = oikea sivutahko
5 = takatahko
6 = vasen sivutahko

niin tuo 90 asteen käännös vastapäivään ylä- ja alatahkon keskipisteet akselinaan on permutaatio f, joka kuvaa:
f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 5
f(5) = 6
f(6) = 3
tai permutaatiomuodossa (1)(2)(3456). Nyt jokaiselle erilliselle syklille (1), (2) tai (3456) voidaan valita oma värinsä ja silti kuutio pysyy oleellisesti samana vaikka sitä kerran käännettäisiin tuolla permutaatiolla. Koska meillä on käytössä 3 eri väriä, niin mahdollisia värityksiä on 3^3.

Huomaa, että 180 asteen käännös vastaa permutaatiota (1)(2)(35)(46). Nyt erillisiä syklejä on neljä kappaletta, ja väritykset voidaan siis valita 3^4 eri tavalla ja silti saatava kuution väritys säilyy oleellisesti samana permutaatiossa.

Jorma
Seuraa 
Viestejä2350
Liittynyt27.12.2008
Puuhikki
Mä opettelin aikoinaan (ei-)Burnsiden lemman tästä monisteesta sivuilta 37–41.

Kiitokset teille kummallekin.
Ottaa aikansa, ennenkuin näen, pystynkö ymmärtämään mitään koko jutusta. Ilmeisesti pitää lukea monisteesta vähän enemmän kuin pelkästään juuri kyseinen asia.

jepajee
Seuraa 
Viestejä22001
Liittynyt29.12.2009

Siinä oli linkki tarkempaan selitykseen.
http://en.wikipedia.org/wiki/Cycle_inde ... _of_a_cube

Sit löysin tällasen:
http://en.wikipedia.org/wiki/Symmetric_group

Ja taisin hiffata jotain jollain tasolla kun ihmettelin tota kakkosta multiplication-kohdassa.
Vannomatta paras.

Räppärit menee perse edellä puuhun.
- Paleface

E: Ai kato vastaus oli naaman edessä:

..Joo'o
http://en.wikiversity.org/wiki/Symmetric_group_S4

Eusa
Seuraa 
Viestejä13403
Liittynyt16.2.2011

Symmetriset ryhmät ovat teoreettisen fysiikan tutkimuksessa paljon käytettyjä apuneuvoja. Oma mielenkiintoni on kohdistunut symmetrisiin ryhmiin, joissa on "symmetriasolmu" lisävapausasteeseen liittyen spindualismiin. Sellaisella esityksellä mm. onnistuu rakentamaan protonin mallin ilman kvarkkeja, myoneista.

Hienorakennevakio suoraan vapausasteista: 1 / (1^0+2^1+3^2+5^3+1^0/2^1*3^2/5^3) = 1 / 137,036

Vierailija

Olen näkevinäni tässä lemmassa yhtenevyyttä Rubikin 3*3*3 kuutioon. Varsinkin tuo jeesin linkittämä kaavio vahventaa näkemystäni. Olenko ihan metsässä?

pöhl
Seuraa 
Viestejä875
Liittynyt19.3.2005

Erilainen todistus Burnsiden lemmalle löytyy osoittesta http://involution.wordpress.com/ .

Phony
Olen näkevinäni tässä lemmassa yhtenevyyttä Rubikin 3*3*3 kuutioon. Olenko ihan metsässä?

Et. Rubikin kuutiota voidaan ajatella äärellisenä automaattina, jossa on 901,083,404,981,813,616 eri tilaa. Tämän osoitti Turner ja Gold vuonna 1985 Burnsiden lemman avulla. http://fab.cba.mit.edu/classes/MIT/864. ... a/project/

xork
Seuraa 
Viestejä383
Liittynyt6.11.2010

Käsitinkö oikein, että tarkoitus on löytää niiden vaihtoehtojen määrä, jotka saadaan kun värejä vaihdetaan mielivaltaisesti, ja ongelmana on, että jotkut ratkaisut vastaavat toisiaan, kun vaihtoehtoa tarkastellaan eri positioista?

Miksi ei ensin tehdä laskentaa ensimmäiselle positiolle, jolloin näitä yhteneviä ratkaisuja tulee, ja tämän jälkeen jaeta tulos tutkittavan kappaleen vapausasteilla, eli kuution tapauksessa 4*6=24:llä?

pöhl
Seuraa 
Viestejä875
Liittynyt19.3.2005

Näköjään tuo helminauhatapaus on lähes laskettu täällä sivulla 46. Tuossa kuitenkin helminauhat ovat samoja jos ne saadaan kuvattua toisilleen kiertämällä. Koska sinun tapauksessa helminauhat ovat samoja jos toinen voidaan kääntää toiseksi, tulee tuota kaavaa muokata siten, että 1/n:n paikalle tulee 1/(2n).

Jorma
Seuraa 
Viestejä2350
Liittynyt27.12.2008
xork
Käsitinkö oikein, että tarkoitus on löytää niiden vaihtoehtojen määrä, jotka saadaan kun värejä vaihdetaan mielivaltaisesti, ja ongelmana on, että jotkut ratkaisut vastaavat toisiaan, kun vaihtoehtoa tarkastellaan eri positioista?

Miksi ei ensin tehdä laskentaa ensimmäiselle positiolle, jolloin näitä yhteneviä ratkaisuja tulee, ja tämän jälkeen jaeta tulos tutkittavan kappaleen vapausasteilla, eli kuution tapauksessa 4*6=24:llä?


Kyllähän sitä aina joku yrittää, laske sinäkin kuution ja kolmen värin tapaus, Huomaat tuloksen olevan väärä (ei edes tasaluku).

Ketjussa mainitut tehtävät ovat yksinkertaisia laskea ilman mitään erikoisempia menetelmiä. Mahdollisesti jopa yhtä nopeita. Vasta vaikeammissa tehtävissä näkee "burnsiden" lemmasta saatavan hyödyn. Burnsiden lemmassa on myös vaara, että soveltaa sitä vaikka ei osaa.
Ensimmäisessä viestissä mainitusta tehtävästä saivat lemman käyttäjät 60 erilaista ketjua, itse sain ilman lemmaa 310 erilaista ketjua. Molemmat tulokset eivät voi olla oikein, Väärin ne taas voivat hyvinkin olla molemmat.
(lisätty loppuosa)

PPo
Seuraa 
Viestejä11613
Liittynyt10.12.2008
Jorma
xork
Käsitinkö oikein, että tarkoitus on löytää niiden vaihtoehtojen määrä, jotka saadaan kun värejä vaihdetaan mielivaltaisesti, ja ongelmana on, että jotkut ratkaisut vastaavat toisiaan, kun vaihtoehtoa tarkastellaan eri positioista?

Miksi ei ensin tehdä laskentaa ensimmäiselle positiolle, jolloin näitä yhteneviä ratkaisuja tulee, ja tämän jälkeen jaeta tulos tutkittavan kappaleen vapausasteilla, eli kuution tapauksessa 4*6=24:llä?


Kyllähän sitä aina joku yrittää, laske sinäkin kuution ja kolmen värin tapaus, Huomaat tuloksen olevan väärä (ei edes tasaluku).

Ketjussa mainitut tehtävät ovat yksinkertaisia laskea ilman mitään erikoisempia menetelmiä. Mahdollisesti jopa yhtä nopeita. Vasta vaikeammissa tehtävissä näkee "burnsiden" lemmasta saatavan hyödyn. Burnsiden lemmassa on myös vaara, että soveltaa sitä vaikka ei osaa.
Ensimmäisessä viestissä mainitusta tehtävästä saivat lemman käyttäjät 60 erilaista ketjua, itse sain ilman lemmaa 310 erilaista ketjua. Molemmat tulokset eivät voi olla oikein, Väärin ne taas voivat hyvinkin olla molemmat.
(lisätty loppuosa)


Pohdiskelin aikani antamaasi helmiongelmaa. Alussa se vaikutti kohtuullisen yksinkertaiselta kombinatooriselta ongelmalta mutta ennen pitkää havaitsin, että rengasrakenne ja symmetria sotkevat pahan kerran yksinkertaiset päätelmäni. Palaan asiaan mikäli on jotain järkevää tarjottavana....

Jorma
Seuraa 
Viestejä2350
Liittynyt27.12.2008
Jorma

Ensimmäisessä viestissä mainitusta tehtävästä saivat lemman käyttäjät 60 erilaista ketjua, itse sain ilman lemmaa 310 erilaista ketjua. Molemmat tulokset eivät voi olla oikein, Väärin ne taas voivat hyvinkin olla molemmat.

Voivatpa hyvinkin olla väärin molemmat, etenkin kun kirjoitin oman ratkaisuni muistihäiriön vallassa 320 olisi oikea luku. En saanut sitä varsinaisesti laskemalla vaan piirtämällä kaikki vaihtoehdot.
Ensin viidelle. Niitä löysin 21 kappaletta joista 10 symmetrisiä. jokaiseen symmetriseen voi lisätä kaksi muuta väriä kymmenellä erilaisella tavalla ja epäsymmetrisiin kahdellakymmenellä erilaisella tavalla.
Yhteensä siitä tulee 320. Varsinaiset laskuyritykset ovat toistaiseksi arvailemista.
http://www.luontonetti.com/jorma/JJJ/helmet.png

Sivut

Uusimmat

Suosituimmat