Ekhm, nije Vam zanimljivo?

Bilo ko, bilo sta?

Da li ti to znaš, pa testiraš ostale, ili ne znaš, pa hoćeš da ti neko reši?

Da nisi slučajno naleteo na Poljinu teoremu, koja je generalizacija Bernsajdove leme?

Ne znajem, treba mi neko da resi, kakvo te testiranje spopalo, kad krenem da resavam pokipi mi mozak. Ogrlica sa 21 perlom ima 1 osu simetrije?

Od 20 mesta treba izabrati 9 na kojima će biti bele kuglice. 20 nad 9.

Ako sam dobro razumeo, primalac poruke ne zna gde je kopča - odakle počinje i gde se završava poruka.
Tako da sam odabir rasporeda belih kuglica na 20 mesta (20*19*18*17*16*15*14*13*12)/9! pravi duplikate pošto je poruka ciklična.
Na primer, ako imamo 2 bele i 2 crne kuglice, onda su ove kombinacije iste:



Tako da mislim da je rešenje:


_{[Ovu poruku je menjao dusans dana 26.10.2014. u 10:35 GMT+1]}

Dvije bijele i dvije crvene prave 6 permutacija.Od toga 4 čine identičan prsten kao što je prikazano gore,a dvije C-B-C-B i B-C-B-C čine novi identičan prsten.Dakle 6/3 a ne 6/4.
/20 u rjšenju treba dokazati ako je uopšte tačno.

@djoka_I Hvala za linkove, ali su mi malo suvoparni ne mogu bas lepo da povezem one jednacine sa ovim zadatkom.

Meni je ovde zbunjujuce ako brojim kombinacije dok su perle nanizane na niti na primer svih 9 crnih perli jedna do druge mi je jedna kombinacija, a na primer gledajuci tako linearno dok su jos na niti tri crne pa sve bele pa sest crnih ni bili razlicita kombinacija medjutim kada se ogrlica zatvori opet se dobija svih 9 crnih jedna do druge, kako da eliminisem te kombinacije i koliko ih je? A ako se to eliminise tako sto biram "fiksnu tacku" 1 biser da je fiksiran pa u odnosu na njega ostali kako mogu da se rasporede i taj biser jedan fiksiran mora biti neke boje crne ili bele pa mi preostaje ili 10 belih i 9 crnih (ciji zbir nije 20) ili 11 belih i 8 crnih za rasporedjivanje na 19 preostalih mesta? A i ogrlica moze da se rotira 19 puta ako bi 20 vratili bi se na pocetnu kombinaciju? Tako da treba broj kombinacija/19?

@Nedeljko Verovatno nije bitno za ovaj deo zadatka ali ima 11 belih i 9 crnih kuglica, a ne 9 belih.
@zzzz Isto verovatno nije bitno ali kuglice su bele i crne, a ne bele i crvene.

A i ja sam dobar: ogrlica od 21 perle? 11 + 9 = 21 normalno :)

_{[Ovu poruku je menjao MajorFatal dana 27.10.2014. u 08:28 GMT+1]}

Pogledaj http://www.elitesecurity.org/t457869-Ajmo-malo-da-bojimo, slicno je...

@darkosos Hvala za link ali i dalje mi ne pomaze

Ja najpametnije sto sam smislio je ono sto je napisao dusans samo jos /2 zato sto ogrlica moze i da se prevrne a ne samo rotira, ama opet mi se nesto ne slaze

Za 7 perli, 4 bele i 3 crne rezultat je 4: 7 nad 3 je 35 i /7 je 5 (rotacije) i kad se ogrlica okrene na drugu stranu eliminise se jos jedna kombinacija ona koja je na neki nacin bila orijentisana u smislu kretanja kazaljki na satu i kontra smeru, kako da znam za neki broj perli recimo 11 i 9 kao u zadatku koliko ima "orijentisanih" kombinacija a koliko simetricnih?

Za 7 perli, 4 bele i 3 crne rezultat je 4: 7 nad 3 je 35 i /7 je 5 (rotacije) i kad se ogrlica okrene na drugu stranu eliminise se jos jedna kombinacija ona koja je na neki nacin bila orijentisana u smislu kretanja kazaljki na satu i kontra smeru, kako da znam za neki broj perli recimo 11 i 9 kao u zadatku koliko ima "orijentisanih" kombinacija a koliko simetricnih?

Ja mislim da je prava metoda računanja neka vrsta rekurzije.Postaviću sliku gdje je prikazan razmještaj 6 crnih i 4 bijele perle na sve moguće načine.

Ideja se odmah vidi.U prvom redu su samo one ogrlice u kojima je max 2 crne jedna do druge.U drugom redu su one koje imaju 3 crne susjedne itd.

Ta grupa zaokružena na crtežu je reper za slaganje preostalih bisera.
(Dakle ako znamo broj različitih ogrlica za neke manje brojeve,mogli bi na osnovu toga ,nekom vrstom zbrajanja, naći i za sledeće veće .

Kasnije ću probati napraviti neku rekurzivnu formulu.Ili neko drugi ako uoči ideju.

_{[Ovu poruku je menjao zzzz dana 29.10.2014. u 17:17 GMT+1]}

Našao sam na Youtube jedan fini primer. U pitanju je broj različitih mogućnosti da se potpuno ispuni tabla za iks-oks (puta nula)

Najbolje je krenuti od uopstenijih problema:

Pa onda, moze pomoci sledece:
How many necklace of 12 beads each can be made from 18 beads of different colours?
Ans:
Hence total number of circular–permutations: 18P12/2x12 = 18!/(6 x 24)
(http://tutors4you.com/circularpermutations.htm)
.
.
.
http://www.totalgadha.com/mod/...ss.php?d=3537&parent=81160

Given 10 beads on a necklace, 6 white and 4 red, how many
http://gmatclub.com/forum/give...e-and-4-red-how-many-3352.html

Permutations in a Necklace
http://mathforum.org/library/drmath/view/56198.html

Necklace
http://mathworld.wolfram.com/Necklace.html

Valjda ce sve ovo nesto pomoci...

_{[Ovu poruku je menjao igorpet dana 29.10.2014. u 19:55 GMT+1]}

E ovo je dobro za analizu i vezbanje, vizuelizacija ume da bude smorna kad je puno kombinacija u pitanju
http://www.jasondavies.com/necklaces/

Izgleda da u ovom zadatku nema "trika" i da je rešenje:



Problem bi bio ako 20, 11 i 9 nisu uzajamno prosti. Na primer, kod 20, 10, 10 konfiguracija u kojoj idu naizmenično crna pa bela perla ne bi imao orbitu 20 nego samo 2.

@djoka_l i predloženo rješenje (8398) sa datim obrazloženjem me podsjeti na jedan stari problem:
"Na koliko se načina može postaviti 8 dama na šahovsku tablu a da se ni jedna ne napada sa nekom drugom?" Nađeno je da je to 92 načina.Ali zapravo ih je samo 12 osnovnih koji se mogu rotacijom i zrcalnim preslikavanjem poklopiti sa nekim od onih ostalih.
Pa ako rotacijom množimo sa 4, a u ogledalu udvostručimo,to znači da od svake osnovne pravimo 8.Zašto onda nema 96 već 92 načina?Zato što jedno od rješenja ima zrcalnu sliku identičnu onoj dvaput zarotiranoj.Dakle jedno od osnovnih rješenja može dati samo 4 pa je 11*8+1*4=92.

U ovom rješenju što je dao @djoka_l fali još ono ogledalo (2) i ubjedljivije objašnjenje da se ni u jednom slučaju ne može rotacijom postići zrcalna slika.
(ja navijam za 4199)

U kombinatorici postoji problem OGRLICE i problem NARUKVICE. Uzima se da za ogrlicu važi da se razmatra jedino problem rotacije, dok se za narukvicu uzima i simetrija.
To je čista konvencija, ne kažem da je logično, ali je tako.

@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...

_{[Ovu poruku je menjao djoka_l dana 31.10.2014. u 14:15 GMT+1]}

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

_{[Ovu poruku je menjao djoka_l dana 31.10.2014. u 20:09 GMT+1]}

@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.


_{[Ovu poruku je menjao zzzz dana 01.11.2014. u 18:30 GMT+1]}

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.

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.

Našao sam ovo:
http://mathworld.wolfram.com/Necklace.html
i ovo:
http://oeis.org/A000029
Nešto se ne poklapa sa ovim što je ovde računato ali ne znam da li je postavka ista u svim detaljima.

Postavka nije ista.
Rešenje na wolframu podrazumeva ogrlicu dužine n, sa a boja. Ovde je fiksirano da, osim što ima samo 2 boje, broj belih i broj crnih je fiksan.

Da... teško je naći baš ovakvu postavku, ali možda ovo pomogne: http://mathforum.org/library/drmath/view/56198.html

Problem je daleko od jednostavnog. Pošto sam u gužvi, sada ću napisati samo opštu formulu i rezultat za konkretan slučaj, a vidim da na temi ima dosta ljudi voljnih da razrađuju detalje.

Ukoliko se narukvica pravi od bisera među kojima ima crnih i belih, tada ukupan broj različitih narukvica iznosi ako je parno i neparno, a u preostalim slučajevima. Dakle, za i odgovor je (upravo kao što je zzzz dobio).

U j... :) ako ono što je zzzz uradio zamenjuje ovo čudilo, treba mu dati medalju! Ja bih samo istražio da li je to zato što je ovo neki specifičan slučaj i ako jeste šta je to specifično. I na kraju bih toj formuli dao ime Kecmanova formula za slučaj taj i taj :)

Ne zamenjuje sasvim. U konkretnom postavljenom slučaju brojevi i su uzajamno prosti, a to umnogome olakšava stvari i formula koju sam naveo zapravo u tom slučaju ispada ista kao ona do koje je došao zzzz (konkretno, ona desna komplikovana suma svodi se samo na jedan sabirak, i to baš ). Ali ako i nisu uzajamno prosti, onda se štošta komplikuje; šta da radimo, tako je kako je.

Nego, sad tek vidim da je zzzz u jednom momentu došao do tačnog rešenja, ali se onda predomislio i zaključio da treba još ponešto dodati na taj rezultat — ipak ne treba, tj. ono prvo što je rekao je tačno.

Ako broj crnih i bijelih bisera nema zajednički faktor tada izračunavanje broja različitih ogrlica nije složeno :
-ogrlice su različite ako se ne mogu kombinacijom i prevrtanjem međusobno poklopiti.

-Ukupan broj bisera je zbroj bijelih i crnih (b i c relativno prosti).

-Broj permutacija ovih n bisera je:

-Ogrlice možemo podjeliti na simetrične i one koje to nisu.

-Simetrične ogrlice se mogu raskopčati na načina.

-Nesimetrične raskopčavanjem mogu dati: ;različitih permutacija.



-Broj simetričnik ogrlica možemo izračunati (simetrala sječe jednu ili 2 perle) :

..(Int je oznaka za cijeli dio,naprimjer Int(2.5)=2)

-Iz ovog možemo izračunati ukupan broj narukvica:



Naprimjer neka je c=4 , b=5

(6 simetričnih i 4 nesimetrične)

Ako c i b nisu relativno prosti tada su neke permutacije sastavljene od nekoliko jednakih djelova.Takođe i simetrične ogrlice mogu imati više od jedne ose simetrije.
Račun je znatno složeniji.

U formuli:


je Ojlerova funkcija?

Mene zabole glava i od konkretnog primera, a kamo li od opšteg slučaja.

Ako Kecmanu damo medalju, Bojanu treba dati orden.

Kecmanu medalja, Bojanu orden, a meni ako moze samarcina kad sledeci put pokusam da resavam ovakvo nesto, samo mi nije jasno odakle ih izvlacim, i prethodni put je od necega sto je trebalo biti malo zahtevniji zadatak iz kombinatorike ispala neka Particiona formula. Ovakvi zadaci su toliko izvan mojih mogucnosti, ne razumem resenje, ne znam koje su sve oznake u resenju i ne bih mogao cak ni da primenim formulu da bih dobio tacan rezultat.

@darkosos 2 od 3 linka koja si dao je vec postavljao igopret
@zzzz samo jos sad i obecavam da te vise necu gnjaviti, posto je tvoje resenje ipak malo blize necemu sto bih ja mogao da razumem: I simetricne i nesimetricne se mogu raskopcati na tacno n mesta, sa svake druge pozicije osim tamo gde prolazi simetrala i simetricne ogrlice daju n razlicitih kombinacija? Zasto se simetricne mogu raskopcati na Rs * n nacina a nesimetricne na Rn * 2n?

Zasto se simetricne mogu raskopcati na Rs * n nacina a nesimetricne na Rn * 2n?

Skopčaj 110100 u prsten.Primjeti da taj prsten nema simetralu.Raskopčaj to na 6 načina.Prevrni prsten ili ga pogledaj u ogledalu pa opet raskopčaj na 6 načina.


Imamo 12 permutacija.Sad to isto uradi sa 111000 pa ćeš dobiti samo 6 različitih.

Tja, dok sam ne resis...

I dalje mi nije jasno, ako simetricnih ima n raskopcavanja, a nesimetricnih 2n, zar ne bi trebalo da jedanput delis sa n, i jos jedanput sa 2n u cilju eliminisanja duplikata, a ti deo jednacine mnozis sa n a onda delis sa 2n?

@Bojan Basic Hvala za formule, jel moze bolo kakvo objasnjenje kad izadjes iz guzve?

Prije Bojanovog objašnjenja trebao bi napraviti male pripreme,a to je proučiti kako se izračunava Ojlerova funkcija.
To je objašnjeno ovdje

Hvala zzzz. Ojlerova funkcija: Auffff :)