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

gLAWA   II.   oSNOWY KOMBINATORIKI

STOLXKO EDINIC, SKOLXKO \LEMENTOW WTOROGO TIPA WHODIT W SO^ETANIE I T. D. nAPRIMER, NAPISAN-
NYM WYE SO^ETANIQM IZ TREH BUKW PO DWE BUDUT SOOTWETSTWOWATX TAKIE POSLEDOWATELXNOSTI:
                                      1100
 0110
 0011
 1001
 0101
 1010:
   tAKIM OBRAZOM, KAVDOMU SO^ETANI@ IZ n \LEMENTOW PO k \LEMENTOW S POWTORENIQMI SOOTWET-
STWUET POSLEDOWATELXNOSTX IZ k EDINIC I n ; 1 NULEJ, I NAOBOROT, PO KAVDOJ TAKOJ POSLEDOWA-
TELXNOSTI ODNOZNA^NO WOSSTANAWLIWAETSQ TAKOE SO^ETANIE. pO\TOMU ^ISLO SO^ETANIJ IZ n PO k S
POWTORENIQMI RAWNO ^ISLU POSLEDOWATELXNOSTEJ IZ k EDINIC I n ; 1 NULEJ.
   rASSMOTRIM MNOVESTWO A POSLEDOWATELXNOSTEJ (x1 
 x2
 : : :
 xk+n;1), GDE ^ISLA xi PRINIMA@T
TOLXKO ZNA^ENIQ 0 ILI 1 I SREDI NIH ROWNO k EDINIC. ~TOBY WY^ISLITX ^ISLO \LEMENTOW MNO-
VESTWA A, OBRATIM WNIMANIE, ^TO ONO RAWNOMO]NO MNOVESTWU WSEH k-\LEMENTNYH PODMNOVESTW
MNOVESTWA f1
 2
 : : :
 k +n ; 1g: PODMNOVESTWO ^ISEL fi1 
 : : :
 ik g SOOTWETSTWUET TOJ POSLEDOWATELX-
NOSTI (x1 
 : : :
 xk+n;1), U KOTOROJ xi1 = 1, : : :, xik = 1. sLEDOWATELXNO, jAj = Ckk+n;1.
pRIMER 2. kOSTI DOMINO MOVNO RASSMATRIWATX KAK SO^ETANIQ S POWTORENIQMI IZ SEMI CIFR 0,
1, 2, 3, 4, 5, 6 PO DWE. ~ISLO WSEH TAKIH SO^ETANIJ RAWNO
                                                           87
                                             f72 = C82 =       = 28:
                                                            2
zADA^A 1. sKOLXKO CELYH NEOTRICATELXNYH REENIJ IMEET URAWNENIE
                                            x1 + x2 + : : : + xn = k?
rEENIE. eSLI IMEEM CELYE NEOTRICATELXNYE ^ISLA x1
 : : :
 xn TAKIE, ^TO x1 + : : : + xn = k, TO
MOVEM SOSTAWITX SO^ETANIE IZ n \LEMENTOW PO k S POWTORENIQMI WZQW x1 \LEMENTOW PERWOGO TIPA,
x2 | WTOROGO TIPA, : : :, xn | n-GO TIPA. nAOBOROT, IMEQ SO^ETANIE IZ n \LEMENTOW PO k, POLU^IM
REENIE URAWNENIQ x1 +: : :+xn = k (x1 \LEMENTOW PERWOGO TIPA, x2 | WTOROGO TIPA, : : :, xn | n-GO
TIPA) W CELYH NEOTRICATELXNYH ^ISLAH. sLEDOWATELXNO, SU]ESTWUET BIEKCIQ MEVDU MNOVESTWOM
WSEH SO^ETANIJ IZ n \LEMENTOW PO k S POWTORENIQMI I MNOVESTWOM WSEH CELYH NEOTRICATELXNYH
REENIJ URAWNENIQ x1 + : : : + xn = k. pO\TOMU ^ISLO REENIJ RAWNO fnk = Cnn+;k1;1 = Cnk+k;1.
   2.4. bINOM nX@TONA. iZWESTNO, ^TO
                                       (a + b)2 = a2 + 2ab + b2 

                                       (a + b)3 = a3 + 3a2b + 3ab2 + b3:
   kAK RASKRYWATX SKOBKI PRI WY^ISLENII WYRAVENIQ (a + b)n? oTWET NA \TOT WOPROS DAET
SLEDU@]AQ
tEOREMA 1. iMEET MESTO RAWENSTWO
                     (a + b)n = Cn0 anb0 + Cn1 an;1b1 + : : : + Cnk an;k bk + : : : + Cnna0 bn
     (1)

GDE Cnk = k!(nn!; k)! .
   fORMULU (1) MOVNO ZAPISATX W WIDE
                                                        n
                                                        X
                                           (a + b)n =         Cnk an;k bk :
                                                        k=0
dOKAZATELXSTWO. pEREMNOVIM POSLEDOWATELXNO (a + b) n RAZ. tOGDA POLU^IM SUMMU 2n SLAGA-
EMYH WIDA d1 : : :dn , GDE di (i = 1
 : : :
 n) RAWNO LIBO a, LIBO b. rAZOBXEM WSE SLAGAEMYE NA n + 1
GRUPPU B0 
 : : :
 Bn, OTNESQ K Bk WSE TE PROIZWEDENIQ, W KOTORYH b WSTRE^AETSQ MNOVITELEM k RAZ,
                                                        52