Biserna ogrlica - kombinatorika

Re: Biserna ogrlica - kombinatorika 05.11.2014. u 12:54 · pre 146 meseci #41

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.

Re: Biserna ogrlica - kombinatorika 05.11.2014. u 12:59 · pre 146 meseci #42

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.

Re: Biserna ogrlica - kombinatorika 05.11.2014. u 13:36 · pre 146 meseci #43

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

Re: Biserna ogrlica - kombinatorika 05.11.2014. u 14:50 · pre 146 meseci #44

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 $n$ bisera među kojima ima $k$ crnih i $n-k$ belih, tada ukupan broj različitih narukvica iznosi $\frac 1{2n}\left(n{{\frac n 2-1}\choose {\frac{k-1}2}}+\sum_{d\mid n,d\mid k}\varphi(d){{\frac n d\choose{\frac k d}}\right)$ ako je $n$ parno i $k$ neparno, a $\frac 1{2n}\left(n{{\big\lfloor\frac n 2\big\rfloor}\choose {\big\lfloor\frac{k}2\big\rfloor}}+\sum_{d\mid n,d\mid k}\varphi(d){{\frac n d\choose{\frac k d}}\right)$ u preostalim slučajevima. Dakle, za $n=20$ i $k=9$ odgovor je $4262$ (upravo kao što je zzzz dobio).

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Biserna ogrlica - kombinatorika 05.11.2014. u 16:01 · pre 146 meseci #45

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 :)

Re: Biserna ogrlica - kombinatorika 05.11.2014. u 16:05 · pre 146 meseci #46

Ne zamenjuje sasvim. U konkretnom postavljenom slučaju brojevi $n$ i $k$ 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š $n\choose k$ ). Ali ako $n$ i $k$ 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.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Biserna ogrlica - kombinatorika 06.11.2014. u 18:52 · pre 145 meseci #47

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). $n=b+c$

-Broj permutacija ovih n bisera je: $p=\frac{n!}{b!c!}$

-Ogrlice možemo podjeliti na simetrične i one koje to nisu. $R=R_s+R_n$

-Simetrične ogrlice se mogu raskopčati na $p_s=R_s\cdot{n}$ načina.

-Nesimetrične raskopčavanjem mogu dati: $p_n=R_n\cdot{2n}$ ;različitih permutacija.

$p=p_s+p_n$

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

$R_s={\frac{(Int(\frac{b}{2})+Int(\frac{c}{2}))! }{(Int(\frac{b}{2}))! (Int(\frac{c}{2}))!}}$ ..(Int je oznaka za cijeli dio,naprimjer Int(2.5)=2)

-Iz ovog možemo izračunati ukupan broj narukvica: $R=R_s+\frac{p{}-{}{p_s}}{2n}$

$R={\frac{(Int(\frac{b}{2})+Int(\frac{c}{2}))! }{(Int(\frac{b}{2}))! (Int(\frac{c}{2}))!}}+\frac{\frac{n!}{b!c!}{}-{}{ \frac{(Int(\frac{b}{2})+Int(\frac{c}{2}))! }{(Int(\frac{b}{2}))! (Int(\frac{c}{2}))!}}\cdot{n}}{2n}$

Naprimjer neka je c=4 , b=5

$R={\frac{(2+2)!}{2!2!}+\frac{\frac{9!}{4!5!}-\frac{(2+2)!}{2!2!}\cdot9}{2\cdot9}=6+\frac{126-6\cdot9}{18}=10$ (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.

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]

Re: Biserna ogrlica - kombinatorika 06.11.2014. u 20:27 · pre 145 meseci #48

U formuli:
$\frac 1{2n}\left(n{{\frac n 2-1}\choose {\frac{k-1}2}}+\sum_{d\mid n,d\mid k}\varphi(d){{\frac n d\choose{\frac k d}}\right)$

$\varphi(d)$ 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.

Re: Biserna ogrlica - kombinatorika 08.11.2014. u 00:48 · pre 145 meseci #49

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?

Re: Biserna ogrlica - kombinatorika 08.11.2014. u 18:27 · pre 145 meseci #50

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.

Code:

110100    001011
101001    100101
010011    110010
100110    011001
001101    101100
011010    010110

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

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]

Re: Biserna ogrlica - kombinatorika 10.11.2014. u 22:19 · pre 145 meseci #51

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?

Re: Biserna ogrlica - kombinatorika 14.11.2014. u 01:43 · pre 145 meseci #52

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

Re: Biserna ogrlica - kombinatorika 15.11.2014. u 13:23 · pre 145 meseci #53

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

$\frac 1{2n}\left(n{{\big\lfloor\frac n 2\big\rfloor}\choose {\big\lfloor\frac{k}2\big\rfloor}}+\sum_{d\mid n,d\mid k}\varphi(d){{\frac n d\choose{\frac k d}}\right)$

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]

Re: Biserna ogrlica - kombinatorika 16.11.2014. u 05:12 · pre 145 meseci #54

Hvala zzzz. Ojlerova funkcija: Auffff :)

Forum kao aplikacija na telefonu

Srodne teme