Дискретная математика. Кулабухов С.Ю. - 47 стр.

                     x 1. oSNOWNOJ PRINCIP KOMBINATORIKI. pERESTANOWKI, RAZME]ENIQ I SO^ETANIQ

rEENIE. kAVDOJ TO^KE PERESE^ENIQ DWUH DIAGONALEJ SOOTWETSTWUET 4 WERINY n-UGOLXNIKA, A
KAVDYM 4 WERINAM n-UGOLXNIKA SOOTWETSTWUET 1 TO^KA PERESE^ENIQ (TO^KA PERESE^ENIQ DIAGO-
NALEJ ^ETYREHUGOLXNIKA S WERINAMI W DANNYH 4 TO^KAH). pO\TOMU ^ISLO WSEH TO^EK PERESE^ENIQ
RAWNO ^ISLU SPOSOBOW, KOTORYMI SREDI n WERIN MOVNO WYBRATX 4 WERINY:
                           n(n ; 1)(n ; 2)(n ; 3) n(n ; 1)(n ; 2)(n ; 3)
                   Cn4 =                         =                       :
                                 1234                    24

  1.6. nEKOTORYE SWOJSTWA SO^ETANIJ.
tEOREMA 1. iMEET MESTO RAWENSTWO
                                       Cnk = Cnk;1 + Cnk;;11:
   w SPRAWEDLIWOSTI \TOGO RAWENSTWA MOVNO UBEDITXSQ ISPOLXZUQ FORMULU
                                                    n!
                                        Cnk =              :
                                                k!(n ; k)!
   sOWETUEM ^ITATEL@ PROWESTI \TO SAMOSTOQTELXNO. pRIWEDEM DRUGOE
dOKAZATELXSTWO. rASSMOTRIM NEKOTORYJ \LEMENT a MNOVESTWAkA, SOSTOQ]EGO IZ n \LEMENTOW, I
WSE k-\LEMENTNYE PODMNOVESTWA MNOVESTWA A (^ISLO IH RAWNO Cn ). wSE k-\LEMENTNYE PODMNOVES-
TWA RAZDELIM NA 2 GRUPPY: PODMNOVESTWA, W SOSTAW KOTORYH WHODIT a, I PODMNOVESTWA, W SOSTAW
KOTORYH a NE WHODIT. ~ISLO PODMNOVESTW W PERWOJ GRUPPE RAWNO Cnk;;11, TAK KAK KAVDOE TAKOE POD-
MNOVESTWO POLU^AETSQ PRISOEDINENIEM K a NEKOTOROGO (k ; 1)-\LEMENTNOGO PODMNOVESTWA MNOVES-
TWA Anfag. ~ISLO PODMNOVESTW WO WTOROJ GRUPPE RAWNO Cnk;1, TAK KAK KAVDOE TAKOE PODMNOVESTWO
ESTX k-\LEMENTNOE PODMNOVESTWO MNOVESTWA A n fag. sLEDOWATELXNO, Cnk = Cnk;1 + Cnk;;11.
tEOREMA 2. iMEET MESTO RAWENSTWO
                                           Cnk = Cnn;k :
dOKAZATELXSTWO. iMEEM:
                                        n!                 n!
                      Cnn;k = (n ; k)!(n ; (n ; k))! = (n ; k)!k! = Cnk :

tEOREMA 3. iMEET MESTO RAWENSTWO
                                         Cnn+m = Cnm+m :
   dOKAZATELXSTWO PROWODITSQ NEPOSREDSTWENNOJ PROWERKOJ S POMO]X@ FORMULY (1).
tEOREMA 4. iMEET MESTO RAWENSTWO
                                          n
                                          X
                                                Cnk = 2n:
                                          k=0
dOKAZATELXSTWO. w SAMOM DELE, POSKOLXKU Cnk | ^ISLO k-\LEMENTNYH PODMNOVESTW n-\LEMENT-
NOGO MNOVESTWA, TO SUMMA W LEWOJ ^ASTI RAWENSTWA ESTX ^ISLO WSEH PODMNOVESTW, KOTOROE RAW-
NO 2n .

   1.7. nOWYE TERMINY. pRAWILO UMNOVENIQ (OSNOWNOE PRAWILO KOMBINATORIKI). pRAWILO
SLOVENIQ. rAZME]ENIQ. pERESTANOWKI. sO^ETANIQ.
                                                 47