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

   x   2.   rAZME]ENIQ, PERESTANOWKI I SO^ETANIQ S POWTORENIQMI. bINOM
            nX@TONA I POLINOMIALXNAQ FORMULA
       rAZME]ENIQ S POWTORENIQMI Akn pERESTANOWKI S POWTORENIQMI pOLINOMIALXNYE
                                          .                                    .KO\FFICI                 -

       ENTY sO^ETANIQ S POWTORENIQMI fnk fORMULY DLQ WY^ISLENIQ Akn POLINOMIALXNYH KO\F
            .                                     .                                ,                     -

       FICIENTOW I fnk bINOM nX@TONA tREUGOLXNIK pASKALQ pOLINOMIALXNAQ TEOREMA
                       .                      .                        .                       .




  2.1. rAZME]ENIQ S POWTORENIQMI.
oPREDELENIE 1. pUSTX n
 k 2 N0 I B = fb1
 b2
 : : :
 bng rAZME]ENIEM S POWTORENIQMI IZ n
                                                                           .
\LEMENTOW MNOVESTWA B PO k \LEMENTOW NAZYWAETSQ WSQKAQ POSLEDOWATELXNOSTX DLINY k,
SOSTAWLENNAQ IZ \LEMENTOW \TOGO MNOVESTWA (W POSLEDOWATELXNOSTI WOZMOVNY POWTORQ@-
]IESQ \LEMENTY).
    o^EWIDNO, ^TO KOLI^ESTWO WSEWOZMOVNYH RAZME]ENIJ S POWTORENIQMI IZ \LEMENTOW MNOVES-
TWA B PO k \LEMENTOW NE ZAWISIT OT PRIRODY \LEMENTOW MNOVESTWA B. pO \TOJ PRI^INE ^EREZ Akn
OBOZNA^IM KOLI^ESTWO WSEWOZMOVNYH RAZME]ENIJ S POWTORENIQMI n-\LEMENTNOGO MNOVESTWA PO k
\LEMENTOW.
pRIMER 1. pUSTX C = fa
 b
 cg. wSE RAZME]ENIQ S POWTORENIQMI PO 2 \TOGO MNOVESTWA: (a
 a),
(a
 b), (a
 c), (b
 a), (b
 b), (b
 c), (c
 a), (c
 b), (c
 c).
    tAKIM OBRAZOM, A23 = 9.
tEOREMA 1. ~ISLO RAZME]ENIJ S POWTORENIQMI
                                                      Akn = nk :
dOKAZATELXSTWO. 1-YM \LEMENTOM POSLEDOWATELXNOSTI MOVET BYTX L@BOJ IZ n \LEMENTOW MNO-
VESTWA, 2-YM | TAKVE L@BOJ IZ n \LEMENTOW I T. D., DO k-GO \LEMENTA POSLEDOWATELXNOSTI.
oTS@DA, PO PRAWILU UMNOVENIQ, Akn = n|  n {z
                                            : : :  n} = nk.
                                                      k
zADA^A 1. dLQ ZAPIRANIQ SEJFOW I AWTOMATI^ESKIH KAMER HRANENIQ PRIMENQ@T SEKRETNYE ZAM-
KI, KOTORYE OTKRYWA@TSQ LIX TOGDA, KOGDA NABRANO NEKOTOROE \TAJNOE SLOWO". |TO SLOWO NABI-
RA@T S POMO]X@ ODNOGO ILI NESKOLXKIH DISKOW, NA KOTORYH NANESENY BUKWY (ILI CIFRY). pUSTX
NA DISK NANESENY 12 BUKW, A SEKRETNOE SLOWO SOSTOIT IZ 5 BUKW. sKOLXKO NEUDA^NYH POPYTOK
MOVET BYTX SDELANO ^ELOWEKOM NE ZNA@]IM SEKRETNOGO SLOWA?
rEENIE. oB]EE ^ISLO KOMBINACIJ RAWNO
                                  A512 = 125 = 248832:
zNA^IT, NEUDA^NYH POPYTOK MOVET BYTX 248831. wPRO^EM, OBY^NO SEJFY DELA@T TAK, ^TO POSLE
PERWOJ VE NEUDA^NOJ POPYTKI OTKRYTX IH RAZDAETSQ SIGNAL TREWOGI.
  2.2. pERESTANOWKI S POWTORENIQMI.
oPREDELENIE 1. pUSTX n 2 N0 B = fb1
 b2
 : : :
 bng pERESTANOWKOJ POWTORENIQMI IZ \LE
                                      ,                            .                   c                       -
MENTOW MNOVESTWA B NAZYWAETSQ WSQKOE RAZME]ENIE S POWTORENIQMI DLINY n.
    pUSTX k1
 k2
 : : :
 km | CELYE NEOTRICATELXNYE ^ISLA, PRI^EM k1 + k2 + : : : + km = n. ~ISLO
PERESTANOWOK S POWTORENIQMI, W KOTORYH m RAZLI^NYH \LEMENTOW MNOVESTWA B I ki \LEMENTOW
i-GO WIDA (i = 1
 2
 : : :
 m) NE ZAWISIT OT PRIRODY \LEMENTOW MNOVESTWA B. pO\TOMU ^ISLO TAKIH
PERESTANOWOK BUDEM OBOZNA^ATX ^EREZ Cn(k1
 k2
 : : :
 km). ~ISLA Cn(k1
 k2
 : : :
 km) NAZYWA@TSQ PO-
LINOMIALXNYMI KO\FFICIENTAMI.
pRIMER 1. pUSTX A = fa
 b
 c
 dg. tOGDA SOOTWETSTWU@]IE PERESTANOWKI S POWTORENIQMI W KO-
TORYH 1 \LEMENT a I 3 \LEMENTA b (m = 2, k1 = 1, k2 = 3): (a
 b
 b
 b), (b
 a
 b
 b), (b
 b
 a
 b), (b
 b
 b
 a).
    tO ESTX C4(1
 3) = 4.
                                                          50