Zadaci iz diskretne matematike

Odgovori Nova tema

1 odgovor
5.625 pregleda

Zadaci iz diskretne matematike 04.07.2005. u 13:56 · pre 259 meseci #1

Spremajući ispit iz diskretne matematike naišo sam na zadatak za cije rjesavanje mi je potrebna pomoc. Zadatak glasi:

Koliko se tajnih kodiranja može napraviti tako da svakom slovu abecede pridružimo (jedinstveno) neko drugo slovo. (Abeceda ima 30 slova)

Ja sam pokusao da radim na sledeci nacin ali ne znam da li je i koliko ovo ispravno.
Pođimo od slova A. Prilikom njegovog kodiranja mozemo da ga zamjenimo sa 29 slova. Uzmimo sada slovo B. Njega mozemo zamjeniti sa 28 jer smo jedno slovo uzeli za kodiranje slova A. C - 27, D - 26,... Pa po mome ispada da je riješenje svega ovoga:
Riješenje: 29!=884176199373970194543616000000

Potpis

Centrometal CM 20-35kW

Re: Zadaci iz diskretne matematike 04.07.2005. u 15:31 · pre 259 meseci #2

Nije baš tako - šta ako si slovo A zamenio sa B? Onda za B i dalje imaš $29$ mogućnosti. Ovo je problem koji se jednostavno rešava principum uključenja-isključenja.

Treba naći broj permutacija $30$ elemenata bez ijedne fiksne tačke. Uzmimo neki podskup azbuke koji ima $k$ slova. Takav podskup možemo odabrati na ${30\choose k}$ načina. Za svaki takav podskup postoji $(30-k)!$ permutacija takvih da su sve njegove tačke fiksne. Sledi da imamo ukupno ${30\choose k}(30-k)!=\frac{30!}{k!}$ permutacija sa $k$ poznatih fiksnih tačaka. Odgovor na pitanje iz zadatka sada dobijamo jednostavnom primenom formule uključenja-isključenja:
$P=\sum_{k=0}^{30}(-1)^k\frac{30!}{k!}=30!\sum_{k=0}^{30}\frac{(-1)^k}{k!}$

Potpis

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

Prijavite se da biste odgovorili u ovoj temi.Prijava Registracija

Forum kao aplikacija na telefonu

Srodne teme