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

gLAWA   II.   oSNOWY KOMBINATORIKI

   1.2. kOLI^ESTWO PODMNOVESTW DANNOGO MNOVESTWA. wYQSNIM TEPERX, SKOLXKO WSEGO
PODMNOVESTW IMEET MNOVESTWO, SOSTOQ]EE IZ n \LEMENTOW (PUSTOE MNOVESTWO TAKVE QWLQETSQ
PODMNOVESTWOM DANNOGO MNOVESTWA).
tEOREMA 1. ~ISLO WSEH PODMNOVESTW MNOVESTWA IZ n \LEMENTOW RAWNO 2n             .


dOKAZATELXSTWO. pERENUMERUEM \LEMENTY DANNOGO MNOVESTWA. dLQ KAVDOGO PODMNOVESTWA PO-
STROIM POSLEDOWATELXNOSTX DLINY n IZ NULEJ I EDINIC PO SLEDU@]EMU PRAWILU: NA k-M MESTE
PIEM 1, ESLI \LEMENT S NOMEROM k WHODIT W PODMNOVESTWO, I 0, ESLI \LEMENT S NOMEROM k NE WHO-
DIT W PODMNOVESTWO. iTAK, KAVDOMU PODMNOVESTWU SOOTWETSTWUET SWOQ POSLEDOWATELXNOSTX NU-
LEJ I EDINIC. nAPRIMER, PUSTOMU MNOVESTWU SOOTWETSTWUET POSLEDOWATELXNOSTX IZ ODNIH NULEJ.
~ISLO WSEH WOZMOVNYH POSLEDOWATELXNOSTEJ DLINY n, SOSTAWLENNYH IZ NULEJ I EDINIC, SOGLASNO
OSNOWNOMU PRAWILU KOMBINATORIKI, 2|  2 {z: : :  2} = 2n. sLEDOWATELXNO, I ^ISLO WSEH PODMNOVESTW
                                         n
DANNOGO MNOVESTWA RAWNO 2n.
  1.3. rAZME]ENIQ. oBOZNA^IM N0 = f0
 1
 2
 :: :g.
oPREDELENIE 1. pUSTX n
 k 2 N0 k  n I B = fb1
 b2
 : : :
 bng rAZME]ENIEM IZ n \LEMENTOW
                                        ,                                   .
MNOVESTWA B PO k \LEMENTOW NAZYWAETSQ WSQKAQ POSLEDOWATELXNOSTX DLINY k, SOSTAWLENNAQ
IZ NEPOWTORQ@]IHSQ \LEMENTOW \TOGO MNOVESTWA.
   o^EWIDNO, ^TO KOLI^ESTWO WSEWOZMOVNYH RAZME]ENIJ IZ \LEMENTOW MNOVESTWA B PO k \LE-
MENTOW NE ZAWISIT OT PRIRODY \LEMENTOW MNOVESTWA B. pO \TOJ PRI^INE ^EREZ Akn OBOZNA^IM
KOLI^ESTWO WSEWOZMOVNYH RAZME]ENIJ PO k \LEMENTOW n-\LEMENTNOGO MNOVESTWA.
pRIMER 1. rASSMOTRIM MNOVESTWO B = f1
 2
 3
 4g. nIVE PRIWEDENY WSE RAZME]ENIQ \TOGO MNO-
VESTWA PO 2 \LEMENTA:
                               (1
 2) (1
 3) (1
 4) (2
 1) (2
 3) (2
 4)
                               (3
 1) (3
 2) (3
 4) (4
 1) (4
 2) (4
 3)
   tO ESTX A24 = 12.
tEOREMA 1. ~ISLO RAZME]ENIJ IZ n \LEMENTOW PO k RAWNO
                                     Akn = n  (n ; 1)  : : :  (n ; k + 1):
dOKAZATELXSTWO. pODS^ITAEM KOLI^ESTWO WSEH POSLEDOWATELXNOSTEJ DLINY k, SOSTAWLENNYH IZ
NEPOWTORQ@]IHSQ \LEMENTOW n-\LEMENTNOGO MNOVESTWA. nA PERWOM MESTE W POSLEDOWATELXNOSTI
MOVET STOQTX L@BOJ IZ n \LEMENTOW, NA WTOROM MESTE | L@BOJ IZ OSTAWIHSQ n ; 1 \LEMENTOW,
I TAK DALEE DO k-GO MESTA NA KOTOROM MOVNO POMESTITX L@BOJ IZ n ; (k ; 1) \LEMENTOW. oTS@DA,
PO PRAWILU UMNOVENIQ, SLEDUET ISKOMAQ FORMULA.
zADA^A 1. sKOLXKIMI SPOSOBAMI MOVNO RASSADITX 4 U^A]IHSQ NA 25 MESTAH?
rEENIE. iSKOMOE ^ISLO SPOSOBOW RAWNO ^ISLU RAZME]ENIJ IZ 25 PO 4:
                                     A425 = 25  24  23  22 = 303 600:
zADA^A 2. u^A]EMUSQ NEOBHODIMO SDATX 4 \KZAMENA NA PROTQVENII 8 DNEJ. sKOLXKIMI SPOSO-
BAMI \TO MOVNO SDELATX?
rEENIE. iSKOMOE ^ISLO SPOSOBOW RAWNO ^ISLU4 4-\LEMENTNYH POSLEDOWATELXNOSTEJ (DNI SDA^I
\KZAMENOW) MNOVESTWA IZ 8 \LEMENTOW, TO ESTX A8 = 8765 = 1680 SPOSOBOW. eSLI IZWESTNO, ^TO PO-
SLEDNIJ \KZAMEN BUDET SDAWATXSQ NA WOSXMOJ DENX, TO ^ISLO SPOSOBOW RAWNO 4A37 = 7654 = 840.
                                                       44