Zadatak iz kombinatorike - vezano uz sumu?

[Ančica]

[Blatko]

[goc]

mislim da stize jos jedan bolesni post
ok, rjesenje je ovo(nadam se da je sve dobro zapisano, ideja je dobra)
gdje je broj nacina na koji mozemo izabrati ljudi iz -clanog skupa koji zadovoljavaju trazene kriterije...
e sad, zasto ovo valja...
ocito je zato sto prvog covjeka odaberemo nasumce na a drugog mozemo na nacina a posto tako svaki par brojimo dvaput na kraju dijelimo s 2.
dalje je zato sto prvog covjeka biramo na nacina. ostala su nam mjesta za koristenje a moramo birati dva covjeka pa to mozemo napraviti na nacina ALI moramo dodati jos 1 jer se moze dogoditi da preostala dva budu tocno za dva lijevo i dva desno od naseg pocetnog covjeka. ovaj slucaj funkcija ne broji jer kad maknete tri covjeka koja vise ne smijete koristiti onda bi ispalo da su ta dva mjesta susjedna iako u stvarnosti nisu pa taj 1 dodamo rucno dijelimo na kraju sve s 3 jer smo svaki slucaj brojali 3 puta(onoliko puta koliko ljudi uzimamo u podskup jer svaki put pocnemo s jednim fiksnim clanom podskupa)
dalje je jer koristimo istu ideju ko i prije samo ovdje rucno dodajemo jer ako se desi da smo odabrali lljude za dva lijevo i dva desno od pocetnog onda ne smijemo koristiti tocno 7 mjesta a moramo odabrati jos jednog covjeka a to ocito mozemo na nacina. dijelimo s 4
dalje je jer ako se sad desi posebni slucaj onda moramo odabrati 2 covjeka od mogucih uz dodatak da mozemo i tu imati novi posebni slucaj(ako odaberemo one koji su za 4 lijevo i 4 desno od pocetnog pa zato jos dodajemo 1) i na kraju naravno dijelimo s 5.

ovako se moze u konacno mnogo koraka izracunati za bilo koji unaprijed zadan al ne vidim nacin za neku opcu formulu...
na komentarima i ispravcima unaprijed zahvaljujem...uzivajte

[Blatko]

amo odrediti gocov f(n, k).

pomoćni rezultat:

k- članih podskupova od [n]:={1, ..., n} koji ne sadrže dva uzastopna broja ima točno (n - k + 1) povrh k. (svakom takvom podskupu K={x1 < ... < xk} bijektivno pridružimo podskup R = {y1<...<yk} od [n - k + 1], gdje je yi = xi - i + 1, i = 1,..., k.)

A = A1 u A2 = {K podskup od [n]: K zadovoljava uvjete zadatka}, gdje je
A1={K iz A: n nije u K} i A2= A\A1. tada je očito:

A1={K podskup od [n - 1] : |K| = k i K ne sadrži dva uzastopna broja}, dok je A2 bijektivan sa skupom S={G podskup {2, ..., n - 2}: |G| = k - 1, G ne sadrži dva uzastopna broja} ( ta bijekcija je G ↔ G u {n}).

zato je f(n, k) = |A| = |A1| + |A2| = ((n - k) povrh k) + ((n - 2 - k) povrh(k - 1)).

@Ančica: uvrstiš n = 20, k = 5 ...




edit:
@goc: mea culpa

[goc]

bomba ti je bijekcija i cijelo rjesenje
al kako da ti

[j.b.i.n.s.h.]

samo da se uključim jer mi je bio zanimljiv zadatak
malo mi se, moram priznati, vrtilo u glavi od okruglog stola

uglavnom,

- znači da osobu nećemo odabrati
o znači da hoćemo
prvi znak stavimo na prvu osobu itd
ono što moramo imati je o-o-o-o-o tj, 5 odabranih i 4 graničara
još jedna osoba mora sjediti između prve i posljednje odabrane, ali otom potom
na ovo smo "potrošili" 9 ljudi, ostalo nam ih je 11
možemo ih ubaciti na 6 mjesta (prije prvoga, između bilo koja 2 i nakon zadnjega) pa je to skoro broj rješenja jednadžbe
x1+...+x6=11, xi>=0
ali x1 i x6 ne smiju biti istovremeno 0

pa su to tri slučaja:
kada je x1=0, a x6>=1 i to 2 puta jer je isto kako i kad je x6=0, a x1>=1
i zadnji kad su i x1 i x6 strogo veći od nule
ostaje zbrojiti ova dva (tri) slučaja

nisam baš 100% sigurna da je to to, ali primjedbe su dobro došle

i svaka čast kolegama gore...
tako nešto mi ipak ne bi palo na pamet ni u snu

_________________
...joined because i needed some help...

[ivancica]

ljudi trebam pomoc... jel moze netko napisat svojim rjecima algoritam za obrnuti leksikografski poredak (radeno na predavanjima - "generiranje kombinatornih objekata"). imali smo primjer:

{1,3,5} -> {2,3,5} -> {1,4,5} -> {2,4,5} -> {3,4,5} -> {2,3,4} -> {1,2,5}

kako smo dosli do toga?

[desire]

[ivanzub]

nije mi jasan algoritam, kojeg imam zapisano. i nisam bas sigurna da li sam dobro prepisala rjesenje ovog primjera.

[Ančica]

[desire]

[ivanzub]

puno hvala. skuzila sam!! jeeej!

jel mozes na isti nacin objasnit i permutacije u lek.poretku? pliz..

[Fisher]

e jel može neko objasnit algoritam za generiranje permutacija u OBRNUTOM leksikografskom poretku? to nismo radili na predavanjima..

može li se to gledati ovako:
perm. u leks poretku -> 123, 132, 213, 231, 312, 321
perm. u OBRNUTOM leks. poretku -> 321, 312, 231, 213, 132, 123?

može li se to uopće ovako gledati ili je drukčiji zapis u obrnutom leks. poretku?

_________________
.. sve bi seke ljubile mornare, ali mame, mame brane to ..

[desire]

[ivanzub]

hvala puno desire (karma++ opet )..idem sad to probat prokuzit pa se javim ak cu imat jos pitanja.

[desire]

Evo mene opet. Dakle ovak, molim da se javi netko od prof Nogo sa primjerom te permutacije. Jer gledajuci sada pozornije algoritam ona permutacija bi isla malo drugacije. Ako slijedimo primjer sa predavanja ide kako sam napisala, no ako pogledamo onaj mali primjercic (4,3,6,5,2,1) koji prelazi u (4,5,1,2,3,6) onda bi stvar isla malo drugacije od napisanoga ovdje i u biljeznici pa bi bilo dobro rijesiti tu dilemu da svi skupa ne napisemo krivo na kolokviju... Mislila sam prvo da sam ja krivo prepisala, ali imam kopije i od jedne cure koja ima zapisano isto...
Uglavnom, nek netko napise kako njemu u biljeznici pise onaj primjer za n=10, za svaki slucaj, iako ja mislim da se prof zabunila na tom primjeru...

_________________

[ma]

krivo si čitala algoritam.
ideš zdesna dok ne naiđeš na element () koji je manji od svog desnog susjeda (). e, ti si tu uvijek mijenjala ta dva, a treba zamijeniti i najmanji veći od , uz uvjet . znači, ne mijenjaš ga s njegovim susjedom, nego ideš do kraja i uzmeš najmanji veći od njega. zamijeniš ih, i obrneš poredak od svih desno nakon zamjene.

mislim da su svi primjeri s predavanja točni.

u ovom primjeru za n=10 smo krenuli od loše permutacije, jer dugo mijenjamo upravo dva susjedna elementa, pa može zbuniti.

ajde ovaj drugi:
(4 3 6 5 2 1) 3<6, pa ću 3 zamijenit s 5 (najmanjim desnim od 3, većim od njega)
(4 5 1 2 3 6) mijenjam 6 i 3
(4 5 1 2 6 3) mijenjam 2 i 3
(4 5 1 3 2 6) sad mijenjamo 6 i 2
itd itd

jasno?

_________________
ima let u finish

[desire]

Imas pravo... tnx

_________________

[betty]

jel netko rijesio taj s permutacijama iz proslogodisnjeg kolokvija? ono sa sljedece 3 perm. ako sam imamo abedc?

[desire]