Biserna ogrlica - kombinatorika

@igopret Hvala! Linkovi koje si dao mi donekle pomazu.

@zzzz To sam ja naivno verovao da zato sto ogrlica moze i da se prevrne a ne samo rotira da ce zbog toga broj kombinacija da se prepolovi, ali nije tako ako se prevrne u istu kombinaciju samo zarotiranu ta se kombinacija ne oduzima jer je vec eliminisana rotacijama (ako po tom redosledu racunas prvo rotacije pa prevrtanje) a ako se prvrne u onu koja je kao u ogledalu njoj samoj onda se oduzima, pa je moje pitanje koliko ima tih koje su simetricne u odnosu na centar rotacije a koliko koje su na neki nacin orijentisane u smislu kretanja kazaljki na satu i kontra jer. Iz onih linkova koje je dao igopret maltene ispada da moram rucno da ih trazim a za 11 perli to je bas dosta.

@djoka_I Nisam znao za tu konvenciju tj. zanima me ovaj zadatak u smislu kao sto se u kombinatorici razmatra problem narukvice.

Na datom linku - Combinatorial Necklaces and Bracelets (www. jasondavies.com/necklaces)
imas primera kombinacija i za ogrlicu i za narukvicu kao i objasnjenje razlike (ukljucis bracelets za narukvicu a inace je ogrlica)
Necklaces - Ogrlica
Bracelets - Narukvica

Problem ogrlice i narukvice kada su u pitanju razlicite boje bisera je relativno lako resiti i svodi se na problem - na koliko nacina mogu da sednu n coveka oko okruglog stola.
Kada su u pitanju ogrlice sa obojenim kuglicama-biserima kojih ima vise u nizu resenje problema je mnogo kompleksije i slozenije.
Prakticno moraju se prvo naci kombinacije rotacija, i preko osa simetrija kombinacije simetrija, i primeniti Burnside-ovu lemu i to nije bas lak nacin da se odredi za 20-o ugao (barem meni kao neko ko nije profesionalno u ovoj oblasti).

Jedini nacin je da nadjes razradjenu semu za konkreti slucaj tj. resenje.
Na onom linku ima uradjenih promera za 6 kuglica (2 crvene, 2 plave i 2 zelene) AABBCC kombinacija kao i AABB kombinacija i AABBB kombinacija i resenje za 12 kuglica (6 crvene, 2 plave, 2 zelene, 2 zute) - 3530.

Ako problem resavas iz hobija kreni sa laksim primerima (manje kuglica) za koje imas resenje, pa pokusaj sam da resis kompleksnije primere za koje ima samo resenje a ne i postupak, pa onda ako si ukapirao probaj resenje konkretnog primera. Pretrazivanje interneta sa ovim pojmovima uvek moze dati jos neki interesantan primer.
Ako nije samo hobi u pitanju ... uzmi neki privatni cas kod ljudi koji su, barem magistrirali, na oblast kombinatorike, verovatno ce pomoci.

Evo ja napravio programče, i kaže 8398 (ako se ne gleda u ogledalu).

@dusans
Pa mozes onda da dodas i ogledalo? Ja sam krenuo da napravim skript u Python-u ali sam se smorio jer nema ugradjen iterator za ovaj slucaj (permutacije multiseta).

Ostali su vec rekli, evo samo da rezimiram:

ako posmatramo skup svih permutacija u relaciji rotacije, prvo pitanje je da li ima zaista 8398 klasa sa 20 elemenata - sto izgleda da jeste tacno u ovom slucaju; sta ovo znaci? to znaci da za svaku permutaciju vazi da je svih 20 njenih rotacija razlicito i to je onda opravdanje za deljenje ukupnog broja sa 20.

ako se doda i simetrija, da li treba deliti sa 2? ovo je kao da simetriju primenjujemo na prethodno dobijen skup klasa i pitanje je da li simetrija klase Rk daje neku drugu klasu rotacije ili ostaje unutar Rk? ako simetrija daje uvek drugu klasu, treba deliti sa 2, inace ne, i odgovor je veoma komplikovan ako stvar nije crno-bela.

Ovo sve mnogo lici na neke algebarske strukture, kao sto i sama Burnside lema koristi. Teorijski, isti princip bi mogao da se primeni polazeci od skupa klasa rotacije, pa primeniti simetriju.

Sve u svemu, stvar bi bila resena ako bi moglo da se dokaze da za proizvoljnu permutaciju 11+9 elemenata vazi da se njena simetricna slika moze dobiti njenom rotacijom (evo jednog ilustrativnog primera: s(01011011) = 11011010, ali se ova permutacija moze dobiti i rotacijom 01011011 5 puta u desno); ili da se dokaze da se simetrijom uvek dobija nesto sto nije moguce dobiti rotacijom. Sve izmedju je mnogo komplikovanije.

Malo sam mozgao:

Dakle, u postavljenom zadatku imamo neparan broj belih i neparan broj crnih perli. Uz to, ukupan broj perli, broj belih i broj crnih su uzajamno prosti. Još je i broj crnih za dva manji od broja belih. Dakle imamo k crnih, k+2 belih i 2k+2 perli ukupno.

1. Ako uzmemo najprostiji slučaj kada je k=1, da proverimo da li je zaista broj različitih kombinacija
(što je jednako 1)
Zaista, bilo gde da stavimo jedinu crnu kuglicu, to je jedna ista rotacija pa je broj različitih cikličnih permutacija jednak 1

2. Za slučaj k=3 da vidimo da li je refleksija (osna simetrija) moguća, tj. da li se osnom simetrijom dobija ista slika kao da je nad tom permutacijom urađena neka rotacija.

Imamo 8 kuglica, označimo ih sa . Ako se refleksijom dobije ista slika tada imamo komplikaciju. Međutim, kada bi to bio slučaj, tada bi moralo da su parovi iste boje ŠTO NIJE MOGUĆE (jer je neparan broj kuglica, pa bar jedan od ovih parova sadrži kuglice različite boje).

Kada još jednom razmislim i nije neki dokaz

Samo sam dokazao da konfiguracija nije osno simetrična, treba dokazati da se operatorom gde je x broj pomeranja ne dobija slika kao sa S gde je S osna simetrija.
Moram još malo da razmislim...

Evo smislio sam zašto rotacija za x mesta u desno ne može da se poklopi sa simetrijom.

Ako imamo n perli (n=2k+2) sa k crnih i k+2 perli, onda možemo pozicije perli da označimo sa 0,1,...,n-1.
Neka je rotacija za x pozicija u desno operator gde je k indeks perle koji ide od 1 do n-1, a x broj pomeranja u desno koji ide u istom opsegu. Simetrija je takvo preslikavanje koje svaku perlu sa indeksom k pomera na mesto .

Logika je ista kao prethodnom postu. Transformacija Rx pomera svaku perlu tako da se dobiju parovi:


Zbog toga što su n, k, i k+2 uzajamno prosti, uvek je , pa onda, zbog neparnog broja belih i crnih perli, ne može da se desi da se sa transformacijom dobije transformacija

@djoka_I
Pogledaj moj post, tamo ima kontraprimer: 8 elemenata, 5 jedinica i 3 nule...

A taj primer me i naveo da probam da opišem permutacije u kojima je S(p) = Rk(p):
rotaciju možemo da posmatramo kao sečenje špila na dva dela i zamenu mesta tim delovima, npr. presekli smo na k-tom mestu:
, dok simetrija pravi:
pa se lepo vidi da mora biti:
i
odnosno, postoje dva dela permutacije koji su simetrični - kao i u primeru koji sam dao: 010 i 11011.

Evo primera za baš 9 nula i 11 jedinica:
010101010101010 11011
simetrična slika je 11011010101010101010 ali se to dobija i rotacijom za 5 mesta u desno

Dakle, ako je navedena logika dobra, tj. karakteriše svaku permutaciju koja ima tražene osobine, onda se rezultat može dobiti prebrojavanjem permutacija koje imaju osobinu da su sastavljene iz dva simetrična dela i one koje to nisu.

Ode moj dokaz u vodu...
I tako je bila prilično tanka logika.

Broj tih simetričnih se da izračunati.Osa preko te narukvice dijeli je na po 10 perli tako da presjeca jednu crnu i jednu bijelu.Na svakoj strani ostane po 5+4 čitave.Permutiramo li to dobijemo broj simetričnih

Ukupan broj (simetričnih i nesimetričnih) se može izračunati ovako:

Umjesto 126 treba da stoji 252.Bijela i crna na simetrali mogu zamjeniti mjesta,pa je konačni rezultat 4325.

Potpis

________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]

Kao za inat taj link mi ne radi...

Ne bih rekao da je isto kao n ljudi oko stola zato sto bi mi takav zadatak bio lak k nad n (biranje mesta oko stola) puta (n-1)! (rotacije ljudi) ispravi me ako gresim? Fora je u tome sto su svi ljudi uglavnom razliciti pa tako... a perle na ogrlici su identicne ako su iste boje bar se tako smatra...

Iz hobija je ali pasionirano :) samo sto nemam uvek vremena i nekad mi iskrsne ovakav zadatak sa kojim bas nemam pojma sta bi skoro ni da zapocnem

Pa pazi, evo ja nisam napravio programce ali ako upisem u wolfram alfa (20!/(11!*9!))/20 isto ce da mi kaze 8398, ali to mi nije nikakav dokaz da sam ispravno racunao tako da ako moze listing tog programa, ja ne umem da analiziram, ali valjda ce neko drugi osim ako neki bas jednostavan pseudokod ne bi bio u pitanju

Jer ja nisam vise siguran ni u ono /20 tj. /n gde je n broj perli a evo zasto zbog ovakvih primera 9 belih i 6 crnih organizovanih u ogrlicu ovako: 3bele 2crne 3bele... i tako do kraja, ogrlica ce izgledati kao tabla za pikado naizmenicno crno i belo u krug tri puta to jest ta kombinacija ca tri puta da naleti na sebe samu dok se okrene za 15 mesta? I ovde mi mozak vise vec tiltuje vise ne znam da li dodajem kombinacije oduzimam kombinacije ili zanemarujem ili sta?

Da li treba deliti sa 2 zbog simetrije? Ne bih rekao na primer zbog ovakvog primera: http://www.elitesecurity.org/t479873-0#3500321 kad bi 5 (sto je rezutat posle: (u!/(b!*c!))/u bcu: beli, crni, ukupno) podelili sa 2 dobili bi rezultat 2,5 razlicitih ogrlica sto je nemoguce.

"Sve u svemu, stvar bi bila resena ako bi moglo da se dokaze da za proizvoljnu permutaciju 11+9 elemenata vazi da se njena simetricna slika moze dobiti njenom rotacijom (evo jednog ilustrativnog primera: s(01011011) = 11011010, ali se ova permutacija moze dobiti i rotacijom 01011011 5 puta u desno); ili da se dokaze da se simetrijom uvek dobija nesto sto nije moguce dobiti rotacijom. Sve izmedju je mnogo komplikovanije."

Tja, ne svidja ti se moja formulacija: ako je osno simetricna kombinacija ne oduzima se od ukupnog zbira a ako je "orijentisana" u smislu kretanja kazaljke na satu, primer koji si odabrao: ogrlica je osno simetricna iako ovako linearno ispisano ne deluje tako!

Nemam pojma sta dokazujes :) Salim se ono sa neparnim brojem perli je zvucalo dobro samo imam potrbu da naglasim da osa simetrije moze da se postavi kroz 2 bisera, kroz 1 i izmedju, i dva puta izmedju bisera. Mozda zavisi od parnosti/neparnosti ukupnog broja perli?

Ogrlice:
010101010101010 11011
i
1010101010101 0110110
01010101010 101101101 itd... su identicne sve vreme jedna kombinacija, ali se moze naci vise parova od po dve simetricna niza perli, kako ces da razdvojis takve kombinacije i zar nije lakse samo naci da li je uopste simetricna ili orijentisana?

Nije mi bas najjasnija logika kako permutacijom 5 i 4 dobijas broj simetricnih? Tih 5 i 4 se mogu rasporediti kako hoces? Mozda si samo dobio broj mogucih rasporeda bez duplikata?

Sta jos meni nije jasno: ako bih krenuo da pisem sve kombinacije:

00000000000111111111
00000000001011111111
00000000010011111111
00000000100011111111
00000000101011111111 itd... kad dodjem do 010101010101010101010 vise nece moci da se nadje nijedna kombinacija koja nije simetricna nekoj od prethodnih?

Opet /2 jer je 010101... na polovini od svih mogucih nizova?

11B i 9C podijelim na 2 dijela.Dobijem 5.5B i 4.5C sa svake strane simetrale.Simetrala siječe jednu bijelu i jednu crnu.SA savake strane ostane po 5B i 4C.Naravno da trebaju biti jednako poredane.Mjenjam na jednoj strani na sve moguće načine,a to je 126.(Lanac od 9 elemenata od kojih je 5 jednakih jedne vrste i 4 takođe ali druge vrste).Na drugoj strani simetrale kopiram da bi to bilo simetrično.
Ogrlica ovakve vrste,ako se prevrne ostaje iste konfiguracije.Prevrtanjem ne dobijemo ništa.
Prekidanjem svake od ovih ogrlica na različitim mjestima možemo napraviti 20*126 različitih lanaca.(Kada bismo mogli od 11B i 9C napraviti 2,4,5...identična lanca,pa ih spojiti u ogrlicu tada bi umjesto 20 imali 10,5,4....različitih raskidanja.)

Dalje:Od ukupnog broja lanaca koje možemo napraviti oduzmem sve ove koji su nastali iz simetričnih ogrlica.Dobijemo broj onih koje su nastale iz nesimetričnih.A pošto iz svake nesimetrične ogrlice pravimo 40 različitih lanaca lako je izračunati koliko je to različitih ogrlica.Zbrojim simetrične i asimetrične i dobijem ukupan broj ogrlica (4262).Među njma ne postoje dvije koje se mogu poklopiti bilo rotiranjem ili prevrtanjem.

Potpis

________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]

Da je bio neparan ukupan broj perli simetrala bi isla kroz jedan biser i izmedju neka dva druga ali moze da vazi ista logika, za paran ukupan broj ne moze dva puta izmedju perli zbog neparnog broja istobojnih perli ni jedna kombinacija ne bi bila simetricna tako da ok: simetrala prolazi kroz 1 beli biser i deset mesta dalje ili na suprotnom delu ogrlice kroz jedan crni, ako hocu da izracunam broj simetricnih kombinacija i biseri moraju biti rasporedjeni 5 + 4 sa obe strane (samo sto ovde gledajuci na ukupan br kombinacija zanemarujemo 1, 2, 3, 4, 6, 7, 8 i svih 9 belih perli na jednoj strani, sto opet moze posluziti za proveru resenja al ajd...), 5 + 4 bisera se moze rasporediti na 126 nacina na jednoj strani ali i na 126 nacina na drugoj strani, 126 * 126 = 15876 razlicitih ogrlica kod kojih simetrala prolazi kroz 1 beli i 1 crni biser, od tog broja 126 je simetricno tj. samo one kombinacije gde su perle isto rasporedjene na obe strane a takvih ima 126. 15876 - 126 = 15750 razlicitih ogrlica, razlicitih bez obzira na rotiranje ili prevrtanje? Ovo je kao da sam fiksirao 2 perle a onda radio sa preostalima kao sa dva niza? Kod tvog resenja malo mi je nejasno to sa raskidanjem i dalje..., nego:

Prvo sam mislio da fali recnik tj. dobar izbor izraza za resenje a sad mi se cini da sam ja lose postavio zadatak, tj. ako je pitanje koliko razlicitih poruka cura moze da posalje noseci ogrlicu (narukvicu) onda je nebitno prevrtanje jer ako pazi kako je stavlja na sebe moze da koristi i one "orijentisane" kombinacije i time ih ima vise, dakle: Ako neko na raspolaganju ima 11 belih i 9 crnih perli, koliko razlicitih nedvosmislenih poruka moze da posalje na nacin tako sto ce od tih perli sastaviti ogrlicu, tako da iskoristi sve perle za pravljenje ogrlice i ako ogrlica kad se sastavi nema nikakav medaljon ili kopcu izmedju bilo koje dve perle vec ove cine jedan neprekinut niz i ako takva ogrlica treba da putuje preko okeana u kutiji bez neke posebne garancije da ce doputovati u onom polozaju u kom je stavljena u tu kutiju? To bi bila malo preciznija formulacija zadatka cije resenje bi me zanimalo, mada je dosad pretpostavljam bilo jasno iz konteksta al ajd za svaki slucaj.

Ustvari :) :

15750/2 = 7875 (sve razlicite ali kad se pogledaju sa druge strane to su te iste, ali bi pogled sa druge strane odgovarao drugim kombinacijama sa prednje strane)

7875 + 126 = 8001 ??? (plus 126 simetricnih sebi ako se prevrnu(ili pogledaju sa druge strane)) a malopre oduzete od ukupnog zbira jer ne podlezu toj racunici.

Da li je ovo tacno?

Ovo sto sam ja napisao ne radi na primeru sa 8 perli (5+3) ali zato to sto si ti napisao zzzz radi savrseno i daje rezultat 5, moram procitati jos jednom pazljivije i proveriti na jos par primera.