Kombinatorika zatak.

[ Viktor84 @ 24.06.2013. 23:15 ] @

Nepismeni poshtar treba isporuciti 7 gradjanina po jedno pismo.

a) Na koliko nacina moze se isporuciti poshta ,ali tako da nijedan ne dobije svoju?
b)Na koliko nacina moze se isporuciti poshta , tako da barem jedna osoba dobije svoju poshtu?
c) Na koliko nacina moze se isporuciti poshta , tako da tacno jedno lice dobije svoju poshtu?
d) Na koliko nacina moze se isporuciti poshta , tako da tacno edno lice ne dobije svoju poshtu?

Ja ovako mislim :
a) 7*6*5*4*3*2*1 = 5040 je svih permutacije od 7
1 je nacin na koj moze poshtar da isporuci pisma ispravno
pa dakle 5040 - 1 = 5039

b) ne znam

c)ako jedna osoba dobije pismo ostaju ostalih 6 koji ne dobiju

P6 = 6*5*4*3*2*1= 720

d)ne znam

Pod a i pod c mislim da su tacni odgovori ali bod b i pod d ne znam.Ako mozete da mi kazete dali su i odgovori pod a i pod c ispravni i pomognete oko b i d.

Pozdrav.

[ darkosos @ 25.06.2013. 10:17 ] @

Nije dobro pod a), ima mnogo pogresnih dostava u kojima je recimo prvi dobio dobro. I slucajevi pod a) i b) su komplementarni, odnosno suprotni i njihov zbir je 7!

Pod a) mozda moze ovako: za prvog izaberes pogresno pismo, dakle 6 mogucnosti; onda biras za onog cije pismo nije vec uzeto i postoji 5 izbora, itd. Ovo moze dok ne predjes pola od ukupnog broja pisama (u ovom slucaju do 4) jer onda ostala pisma mozes proizvoljno rasporediti zato sto si potrosio sva odgovarajuca pisma. Resenje bi bilo

sto bi moglo da se napise i kao

[ Nedeljko @ 25.06.2013. 12:17 ] @

Preispitaj ti to. Tačan rezultat pod a) je 1845, a pod b) 3195 i može se dobiti formulom uključivanja isključivanja.

Ako je

, onda je

odgovor pod b).

[ darkosos @ 25.06.2013. 12:25 ] @

Znam da moze tako kako si napisao, ali iako je lako odrediti S-ove i broj clanova, problem je sto imaju preseke, nisam ni pokusao da idem tim putem... Jesi li ovo dobio programski?

[ Nedeljko @ 25.06.2013. 12:52 ] @

Citat:

darkosos: Znam da moze tako kako si napisao, ali iako je lako odrediti S-ove i broj clanova, problem je sto imaju preseke, nisam ni pokusao da idem tim putem...

Upravo tome služi formula uključivanja isključivanja.

[ darkosos @ 25.06.2013. 13:01 ] @

Ko bi rekao, ima cak i http://en.wikipedia.org/wiki/Derangement

Nisam siguran zasto ovo moje nije tacno, ali odgovor na a) postoji u tablici na strani koju sam naveo :)

[ Viktor84 @ 25.06.2013. 13:16 ] @

pod a) ja mislim da je formula za dearanzmanom.
t.j.

D7=7!*(1-1/1!+1/2!-1/3!+1/4!-1/5!+1/6!-1/7!) =1854

c) mislim da je dearanzman od 6
D6= 6!*(1-1/1!+1/2!-1/3!+1/4!-1/5!+1/6!)= 264

a kako mogu naci pod b i pod d

[ djoka_l @ 25.06.2013. 13:32 ] @

Evo malo pomoći:

Code (cpp):

#include <iostream>     // std::cout

#include <algorithm>    // std::next_permutation

int main () {

  int myints[] = {0,1,2,3,4,5,6};

  int hits[8] = {0,0,0,0,0,0,0,0};

  int s;

  do {

    s=0;

    for( int i=0; i<7; i++)

        if( myints[i] == i ) s++;

    hits[s]++;      

  } while ( std::next_permutation(myints,myints+7) );

  for( int i=0; i<8; i++ ) std::cout << i << " hits: " << hits[i] << '\n';

  return 0;

}

rezultat:

Code:

$ ./perm
0 hits: 1854
1 hits: 1855
2 hits: 924
3 hits: 315
4 hits: 70
5 hits: 21
6 hits: 0
7 hits: 1
$

a) 1854
b) 5040-1854
c) 1855
d) 0

[ Nedeljko @ 25.06.2013. 13:37 ] @

Da, to je to, samo sam ja loše prepisao.

a) 1854,
b) 3196 = 5040-1854,
c) 6*265 = 1590,
d) 0.

[ Viktor84 @ 25.06.2013. 13:44 ] @

Hvala na resenja ,mogao sam napraviti program ali bitno mi je bilo matematicki postupak.
Ipak imam ispit od Diskretne strukture :)