Novo

Forum kao aplikacija na telefonu

Dodajte forum na početni ekran i koristite ga kao aplikaciju, sa menijem na dnu ekrana.

Kombinatorika - prakticna pitanja

Kombinatorika - prakticna pitanja 11.03.2005. u 13:59 · pre 264 meseca #1
Imamo sledeći skup elemenata - A, B, C, D, E, F

Kada tražimo broj kombinacija za sistem 2 od 6, računamo po formuli:


C_{k}^n = {{k!}\over{n!(k-n)!}}

iz čega sledi:

C_{6}^2 = {{6!}\over{2!(6-2)!}} = {15}

To nije sporno, međutim šta se dešava kada umesto elementa A dodamo neke elemente tako da dobijemo podskup elemenata X,Y, ili samo Z unutar već postojećeg skupa. Kako bi onda to računali?

Znači onda bi imali nesto poput ovoga:


Elementi = {\left[\matrix{%
A&X&Y\cr
B&Z\cr
C\cr
D\cr
E\cr
F\cr}\right]}

Ja ovo izračunam putem FOR petlje ručno, tako što raspisujem kombinacije po elementima, poništim one koje se ponavljaju i na taj način dobijem broj kombinacija.

Međutim, da li postoji način da se ovo računanje izvede na jednostavnije putem neke matematičke formule?
Re: Kombinatorika - prakticna pitanja 11.03.2005. u 17:48 · pre 264 meseca #2
Meni nije bas jasno sta se trazzi iako po malo znam i matis i programiranje
Da li si mislio da umesto A ide X ili Y
Ako je tako onda bi bilo 2 puta

C_{k}^n = {{6!}\over{2!(6-2)!}}

jednom za X a drugi put za Y
???
Potpis
tisuću lijepih žena posve nagih
Re: Kombinatorika - prakticna pitanja 12.03.2005. u 21:34 · pre 264 meseca #3
Da, jeste tako, uzimamo jedno po jednu i racunamo kroz for petlju pa od skupa kombinacija imamo podskupove sa kombinacijama...

Ja to vec racunam kroz program, to nije problem, ali mene zanima da li za to postoji neko elegantnije matematicko resenje?
Re: Kombinatorika - prakticna pitanja 19.03.2005. u 00:07 · pre 263 meseca #4
Hm, ako sam te dobro razumeo, tvoj problem je da izracunas broj kombinacija ako se recimo A ponavlja $k_1$ puta,..., F ponavlja $k_6$ puta. Cini mi se (na prvi pogled) da nema elegantnog izraza za to, ali mozes da napises rekurentnu flu:

$$N(n,m;k_1,\ldots,k_n)=k_1 N(n-1,m-1;k_2,\ldots,k_n)+N(n-1,m;k_2,\ldots,k_n)$$

gde je  N(n,m;k_1,\ldots,k_n) broj kombinacija od n elemenata m-te klase gde svaki moze da se ponavlja  k_i puta. Formula se dobija jednostavno, razmatras slucajeve kad prvi element jeste i nije izabran. Ako je k_i=1, formula se svodi na onu poznatu relaciju za Pascalov trougao. Ovakvo racunanje je sigurno brze od brute-forcea.
Potpis
DeXteR[ity]!!!!
Prijavite se da biste odgovorili u ovoj temi.PrijavaRegistracija

Premeštanje teme