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

x 2. rAZME]ENIQ, PERESTANOWKI I SO^ETANIQ S POWTORENIQMI. bINOM nX@TONA I POLINOMIALXNAQ FORMULA

tEOREMA 1. pUSTX k1
 k2
 : : :
 km CELYE NEOTRICATELXNYE ^ISLA PRI^EM k1 +k2+: : :+km = n
                                     |                                                   ,         .
~ISLO RAZLI^NYH PERESTANOWOK, KOTORYE MOVNO SOSTAWITX IZ n \LEMENTOW, SREDI KOTORYH
IMEETSQ k1 \LEMENTOW PERWOGO TIPA, k2 \LEMENTOW WTOROGO TIPA, : : : , km \LEMENTOW m-GO
TIPA (POLINOMIALXNYJ KO\FFICIENT) RAWNO
                                                                     n!
                               Cn (k1
 k2
 : : :
 km ) =                             :
                                                            k1!  k2!  : : :  km !
dOKAZATELXSTWO. rASSMOTRIM ODNU PERESTANOWKU I ZAMENIM W NEJ WSE ODINAKOWYE \LEMENTY
RAZNYMI. tOGDA ^ISLO RAZLI^NYH PERESTANOWOK, KOTORYE MOVNO SOSTAWITX IZ RASSMATRIWAEMOJ
PERESTANOWKI, RAWNO k1!  k2!  : : :  km !. pRODELAW \TO DLQ KAVDOJ PERESTANOWKI, POLU^IM n! PERE-
STANOWOK. sLEDOWATELXNO,
                             Cn(k1 
 k2
 : : :
 km )  k1!  k2!  : : :  km ! = n!

^TO I DOKAZYWAET UTWERVDENIE TEOREMY.
   pOLINOMIALXNYE KO\FFICIENTY IME@T E]E ODNU O^ENX WAVNU@ KOMBINATORNU@ INTERPRETA-
CI@. pUSTX IMEETSQ n BUKW: k1 BUKW a1 , k2 BUKW a2 , : : :, km BUKW am (k1 +k2 +: : :+km = n). ~ISLO
RAZLI^NYH SLOW, KOTORYE MOVNO SOSTAWITX IZ \TIH BUKW, O^EWIDNO, RAWNO
                                                                  n!
                               Cn (k1
 k2
 : : :
 km ) = k !  k !  : : :  k ! :
                                                          1     2             m
zADA^A 1. sKOLXKO RAZLI^NYH SLOW MOVNO SOSTAWITX, PERESTAWLQQ BUKWY SLOWA \MATEMATIKA"?
rEENIE. ~ISLO RAZLI^NYH SLOW RAWNO
                                                            10!
                             C10(2
 2
 3
 1
1
 1) =                  = 151200:
                                                        2!  2!  3!
zADA^A 2. sKOLXKIMI SPOSOBAMI MOVNO RAZDELITX m +n+s PREDMETOW NA 3 GRUPPY TAK, ^TOBY
W PERWOJ GRUPPE BYLO m PREDMETOW, WO WTOROJ | n PREDMETOW, W TRETXEJ | s PREDMETOW?
rEENIE. iSKOMOE ^ISLO SPOSOBOW RAWNO
                                                   (m + n + s)!
                                 Cm+n+s (m
 n
 s) = m!  n!  s! :

  2.3. sO^ETANIQ S POWTORENIQMI.
oPREDELENIE 1. pUSTX k 2 N0 n 2 N sO^ETANIEM IZ n \LEMENTOW PO k \LEMENTOW S PO
                                    ,          .                                                   -
WTORENIQMI NAZYWAETSQ SOWOKUPNOSTX, SODERVA]AQ k \LEMENTOW, PRI^EM KAVDYJ \LEMENT
PRINADLEVIT K ODNOMU IZ n TIPOW.
   ~ISLO SO^ETANIJ IZ n \LEMENTOW PO k \LEMENTOW S POWTORENIQMI OBOZNA^AETSQ fnk .
pRIMER 1. iZ TREH BUKW a, b, c MOVNO SOSTAWITX TAKIE SO^ETANIQ PO DWA S POWTORENIQMI: aa,
bb, cc, ac, bc, ab. tAKIM OBRAZOM, f3 = 6.
                               2


tEOREMA 1. ~ISLO RAZLI^NYH SO^ETANIJ IZ n \LEMENTOW PO k \LEMENTOW S POWTORENIQMI RAW              -
NO
                                         fnk = Cnn+;k1;1 = Cnk+k;1:
dOKAZATELXSTWO. kAVDOE SO^ETANIE POLNOSTX@ OPREDELQETSQ, ESLI UKAZATX, SKOLXKO \LEMENTOW
KAVDOGO IZ n TIPOW W NEGO WHODIT. pOSTAWIM W SOOTWETSTWIE KAVDOMU SO^ETANI@ POSLEDOWA-
TELXNOSTX NULEJ I EDINIC, SOSTAWLENNU@ PO TAKOMU PRAWILU: NAPIEM PODRQD STOLXKO EDINIC,
SKOLXKO \LEMENTOW PERWOGO TIPA WHODIT W SO^ETANIE, DALEE POSTAWIM NULX I POSLE NEGO NAPIEM
                                                       51