Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski 

Matematyka Dyskretna – ćw. 5 

Kombinatoryka 1 

Zasada włączeń i wyłączeń, prawo mnożenia, 

wariacje i kombinacje 

 

Zasada włączeń i wyłączeń dla dwóch skończonych zbiorów: 

                              

Zasada włączeń i wyłączeń dla trzech skończonych zbiorów: 

                                                                          

Prawo mnożenia (dla zbiorów skończonych): 

  

 

   

 

       

 

      

 

      

 

          

 

  

Zad. 1. Ile jest liczb trzycyfrowych podzielnych przez 8 lub 12? 

Zad. 2. Ile jest liczb czterocyfrowych podzielnych przez 3 lub 11 lub 12? 

Zad.  3.  Niech: 

                        ,                   

 

         

 

     ,     

                                          

 

   

 

 . Oblicz liczbę elementów zbioru          . 

Niech dany będzie zbiór 

 

 

 złożony z n elementów. 

k-elementową  (

     )  wariacją  bez  powtórzeń   

 

 

  ze  zbioru 

 

 

  nazywamy  każdy  k-elementowy  ciąg 

utworzony z elementów zbioru 

 

 

 taki, że elementy w tym ciągu nie mogą się powtarzać. 

Liczba wszystkich k-elementowych wariacji bez powtórzeń ze zbioru 

 

 

 wyraża się wzorem: 

  

 

 

   

  

        

                                

Jeśli 

      to wariację bez powtórzeń nazywamy permutacją  

 

 zbioru 

 

 

. Czyli: 

 

 

   

 

 

. 

Liczba wszystkich permutacji zbioru 

 

 

 wyraża się wzorem: 

  

 

      

 

 

   

  

        

 

  
  

     

k-elementową  wariacją  z  powtórzeniami 

 

 

 

  ze  zbioru 

 

 

  nazywamy  każdy  k-elementowy  ciąg  utworzony 

z elementów zbioru 

 

 

 taki, że elementy w tym ciągu mogą się powtarzać. 

Liczba wszystkich k-elementowych wariacji z powtórzeniami ze zbioru 

 

 

 wyraża się wzorem: 

  

 

 

     

 

 

 

Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski 

k-elementową (

     ) kombinacją bez powtórzeń  

 

 

 ze zbioru 

 

 

 nazywamy każdy k-elementowy podzbiór 

utworzony z elementów zbioru 

 

 

. Skoro podzbiór, to elementy nie mogą się powtarzać. 

Liczba wszystkich k-elementowych kombinacji bez powtórzeń ze zbioru 

 

 

 wyraża się wzorem: 

  

 

 

     

 

    

  

           

 

k-elementową  kombinacją  z  powtórzeniami 

 

 

 

  ze  zbioru 

 

 

  nazywamy  każdy  k-elementowy  wielozbiór 

utworzony z elementów zbioru 

 

 

. Skoro wielozbiór, to elementy mogą się powtarzać. 

Liczba wszystkich k-elementowych kombinacji z powtórzeniami ze zbioru 

 

 

 wyraża się wzorem: 

  

 

 

              

 

   

            

           

 

 

Zad. 4. Na ile sposobów można sześć z dziesięciu osób wpisać na numerowaną listę? Na ile 
sposobów można ich wszystkich wpisać na numerowaną listę? 

Zad. 5. Ile zostanie rozegranych meczów w turnieju szachowym dziesięciu zawodników gdzie 
każdy grał z każdym dokładnie jeden raz? 

Zad.  6.  Ile  symboli  można  zakodować  w  alfabecie 

            używając  co  najwyżej  6 

znaków tego alfabetu? 

Zad.  7.  Na  ile  sposobów  można  pomalować  czterema  kolorami  sześć  nierozróżnialnych 
przedmiotów? 

Zad. 8. Ile jest dziewięciocyfrowych numerów rozpoczynających się od „609” zawierających 
dokładnie raz sekwencję „609”? 

Zad. 9. Ile jest pięciocyfrowych liczb parzystych, które mają dokładnie dwie cyfry parzyste? 

Zad.  10.  Ile  jest  sześciocyfrowych  liczb  nieparzystych  o  różnych  cyfrach,  które  mają 
dokładnie trzy cyfry parzyste? 

Czy liczy się 

kolejność? 

Nie 

Kombinacje 

Czy są 

powtórzenia? 

Nie 

Kombinacje 

bez powtórzeń 

Tak 

Kombinacje 

z powtórzeniami 

Tak 

Wariacje 

Czy są 

powtórzenia? 

Nie 

Wariacje 

bez powtórzeń 

Tak 

Wariacje 

z powtórzeniami