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

gLAWA   II.   oSNOWY KOMBINATORIKI

  1.5. sO^ETANIQ.
oPREDELENIE 1. pUSTX n
 k 2 N0 k  n I B = fb1
 b2
 : : :
 bng
                                          ,                                   | n-\LEMENTNOE MNOVESTWO.
wSQKOE k-\LEMENTNOE PODMNOVESTWO B NAZYWAETSQ SO^ETANIEM IZ n \LEMENTOW \TOGO MNO-
VESTWA PO k \LEMENTOW.
   sOWERENNO O^EWIDNO, ^TO KOLI^ESTWO WSEWOZMOVNYH SO^ETANIJ PO k \LEMENTOW MNOVESTWA B
NE ZAWISIT OT PRIRODY \LEMENTOW MNOVESTWA B. w SILU \TOGO, KOLI^ESTWO WSEWOZMOVNYH SO^E-
TANIJ PROIZWOLXNOGO n-\LEMENTNOGO MNOVESTWA PO k \LEMENTOW OBOZNA^IM ^EREZ Cnk .
pRIMER 1. rASSMOTRIM MNOVESTWO B = f1
 2
 3
 4g. wSE SO^ETANIQ \TOGO MNOVESTWA PO 2 \LEMEN-
TA: f1
 2g, f1
 3g, f1
 4g, f2
 3g, f2
 4g, f3
 4g. tAKIM OBRAZOM, C42 = 6.
tEOREMA 1. ~ISLO WSEH k-\LEMENTNYH PODMNOVESTW MNOVESTWA IZ n \LEMENTOW
                                     n  (n ; 1)  : : :  (n ; k + 1)       n!
                              Cnk =           12:::k
                                                                       =
                                                                         k!(n ; k)!
                                                                                    :               (1)
dOKAZATELXSTWO. fORMULA DLQ ^ISLA SO^ETANIJ LEGKO POLU^AETSQ IZ WYWEDENNYH RANNEE FOR-
MUL DLQ ^ISLA RAZME]ENIJ I PERESTANOWOK. w SAMOM DELE, SOSTAWIM WNA^ALE WSE SO^ETANIQ IZ
n \LEMENTOW PO k, A POTOM PERESTAWIM WHODQ]IE W KAVDOE SO^ETANIE \LEMENTY WSEMI WOZMOVNY-
MI SPOSOBAMI. pRI \TOM POLU^ATSQ WSE RAZME]ENIQ IZ n \LEMENTOW PO k, PRI^EM KAVDOE TOLXKO PO
ODNOMU RAZU. nO IZ KAVDOGO k-SO^ETANIQ MOVNO SDELATX Pk PERESTANOWOK, A ^ISLO \TIH SO^ETANIJ
RAWNO Cnk . zNA^IT, SPRAWEDLIWA FORMULA
                                                 Akn = Pk  Cnk :
oTS@DA NAHODIM, ^TO
                                Ak n  (n ; 1)  : : :  (n ; k + 1)           n!
                         Cnk = n =                                       =            :
                                Pk                      k!                 k!(n ; k)!
zADA^A 1. sKOLXKIMI SPOSOBAMI ^ITATELX MOVET WYBRATX 3 KNIVKI IZ 5?
rEENIE. iSKOMOE ^ISLO SPOSOBOW RAWNO ^ISLU 3-\LEMENTNYH PODMNOVESTW 5-\LEMENTNOGO MNO-
VESTWA:
                                                          5!
                                             C53 =             = 10:
                                                       3!  2!
zADA^A 2. sKOLXKIMI SPOSOBAMI IZ 7 ^ELOWEK MOVNO WYBRATX KOMISSI@, SOSTOQ]U@ IZ 3 ^ELO-
WEK?
rEENIE. ~TOBY RASSMOTRETX WSE WOZMOVNYE KOMISSII, NUVNO RASSMOTRETX WSE WOZMOVNYE
3-\LEMENTNYE PODMNOVESTWA MNOVESTWA, SOSTOQ]EGO IZ 7 ^ELOWEK. iSKOMOE ^ISLO SPOSOBOW RAWNO
                                                     765
                                             C73 = 1  2  3 = 35:
zADA^A 3. w TURNIRE PRINIMALI U^ASTIE n AHMATISTOW, I KAVDYE 2 AHMATISTA WSTRETILISX
1 RAZ. sKOLXKO PARTIJ BYLO W TURNIRE?
rEENIE. pARTIJ BYLO SYGRANO STOLXKO, SKOLXKO MOVNO WYDELITX 2-\LEMENTNYH PODMNOVESTW
W MNOVESTWE IZ n \LEMENTOW, TO ESTX
                                                         n(n ; 1)
                                               Cn2 =              :
                                                            12
zADA^A 4. w SKOLXKIH TO^KAH PERESEKA@TSQ DIAGONALI WYPUKLOGO n-UGOLXNIKA, ESLI NIKAKIE 3
IZ NIH NE PERESEKA@TSQ W ODNOJ TO^KE?
                                                  46