Što se traži u ovom zadatku?

[Gost]

Neka je S n-člani skup. Koliko ima dvočlanih skupova {X, Y} gdje su X, Y podskupovi od S, a presjek X i Y je prazan skup.
-----

recimo da je n=10, a S=(1,2,3,.....,10). Ja sam mislio da je jedno od mogućih rješenja ((3,4),(6,7)). Dakle po meni prebrojim koliko ima dvočlanih podskupova od S (n povrh 2) pa to pomnožim sa (n povrh 2)-1 i sve skupa podjelim s 2 jer nije bitan poredak odabira skupova. Ali rješenje je (3^n - 1)/2 pa moje rješenje nije dobro. Pošto sam prilično siguran da je moje rješenje točno za moje čitanje zadatka može li mi netko molim vas reći što se onda zapravo traži u zadatku od mene

[vsego]

Nigdje ne pise da su X i Y dvoclani!

Ideja: Definiraj funkciju f:S→{0,1,2}:
f(x) = 1 ⇔ x € X
f(x) = 2 ⇔ x € Y
f(x) = 0 ⇔ inace (tj. x nije ni u jednom)

Dakle, pitanje je koliko ima takvih funkcija, uz dodatak da su funkcije f(x) i g(x) "jednake" ako za svaki x vrijedi f(x)=g(x)=0 ili f(x)+g(x)=3 (tj. smijemo zamijeniti jedinice i dvojke, odnosno smijemo zamijeniti mjesta skupovima X i Y jer je {X,Y} skup, a ne uredjeni par).

E sad: funkcija s gornjom definicijom ima 3^n. No, to ukljucuje i funkciju f(x)=0, sto bi za {X,Y} dalo jednoclani skup {0,0} (0="prazan skup"). Zato ih ima 3^n-1, a gornja opaska daje dijeljenje s 2 ima ih (3^n-1)/2

Jasno, to treba malo formalnije zapisati nego sto sam ja tu objasnio...

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.

[Gost]

Znam da gnjavim i da sam trebao ne sjedit na ušima na elementarnoj ali imam još par pitanja

Prvi dio gornjeg zadatka pita koliko ima parova (x,y) disjunktnih podskupova od S? ((x,y podskupovi od S, x presjek y = prazan skup))
tu mi je jasno da trpam elemente iz S u tri kutije - X, Y i smeće. Jedan od slučajeva je da su x i y prazni, a cijeli S je u smeću. Tada dobivam (prazan skup, prazan skup) kao rješenje. Prazan skup je podskup od Sa, prazan skup presjek prazan skup je opet prazan skup pa je sve OK.
ALI u drugom dijelu zadatka više ne govorimo o paru (uređenom skupu X i Ya) već o njihovom skupu (neuređenom paru). Ja bi tada samo podjelio 3^n s 2 ali kao što ste rekli trebam izbacit taj specifičan slučaj {prazan skup, prazan skup}.

Dakle zaključak - kada govorimo o uređenoj k-torci (u našem slučaju 2-torka) onda je OK da bude (X=prazan skup, Y=prazan skup), ali kada se radi o skupu {X, Y} tada njegovi elementi ne smiju biti prazi skupovi, ali samo jedan element može

hvala!

[vsego]

Nisam siguran da sam razumio sto je tu pitanje...

Ako te buni onaj -1... Kad imas situaciju X=Y=0 (prazan skup), tj. cijeli S je "u smecu" (kako si to lijepo i suptilno napisao ), onda je tvoj dvoclani skup {X,Y} jednak {0,0}. No, skupovi ne trpe ponavljanje, pa je {0,0}={0}, dakle jednoclan, pa to ne mozemo brojati. Zato taj slucaj ne racunamo, pa odatle -1.

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.

[Crni]

Možda je bolje reći dvočlanih familija {X,Y} podskupova od S. Nađimo broj takvih familija.
Nađimo prvo broj familija koje sadrže prazan skup. To je očito , jer ovaj drugi član familije može biti bilo koji neprazan skup.
Nađimo sada broj takvih familija koje sadrže samo neprazne podskupove. Neka je i T k-člani podskup od S. Broj particija od T u dva bloka se računa pomoću rekurzije

S(k,2)=S(k-1,1)+2S(k-1,2)

ili jednostavnije zapisano



Rješenje rekurzije je . k-člani skup možemo izabrati na načina, pa je broj takvih familija jednak



Onda je rješenje zadatka



za prirodni n.

[Godot]