Diskretna matematika

pismeni deo ispita

19.10.2004.

1. Zapisane su sve k – varijacije elemenata , gde je . Koliko puta je zapisan element ?
2. Neka je  i . Koliko ima permutacija skupa A, kod kojih za svako  element  ne stoji neposredno iza elementa j?
3. Da li postoje grafovi sa sledećim nizovima stepena čvorova:
1. 1,2,2,2,3,5
2. 1,1,3,3,3,3,5,6,8,9
3. 1,3,3,3,4,4

Obrazložiti odgovore.

4. Neka je G povezan graf koji nije kompletan. Dokazati da u G postoje čvorovi u, v i w, takvi da su uv i vw grane u G, ali uw nije grana u G.
5. Neka je T stablo sa tačno k – 1 čvorova koji nisu listovi, sa po jednim čvorom stepena i za svako . Odrediti broj čvorova stabla T.