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

gLAWA       II
oSNOWY KOMBINATORIKI


   x   1.   oSNOWNOJ PRINCIP KOMBINATORIKI. pERESTANOWKI, RAZME]ENIQ
            I SO^ETANIQ
       oSNOWNOJ PRINCIP KOMBINATORIKI kOLI^ESTWO PODMNOVESTW DANNOGO MNOVESTWA rAZME]E
                                           .                                       .   -

       NIQ I PERESTANOWKI Akn Pn fORMULY DLQ WY^ISLENIQ Akn Pn sO^ETANIQ Cnk fORMULY DLQ
                         :   ,    .                        ,   .               .

       WY^ISLENIQ Cnk nEKOTORYE SWOJSTWA SO^ETANIJ
                     .                                .




   1.1. oSNOWNOJ PRINCIP KOMBINATORIKI. uSTANOWIM SNA^ALA O^ENX WAVNOE PRAWILO,
KOTOROE ^ASTO PRIMENQETSQ PRI KOMBINATORNYH RAS^ETAH. nA^NEM S TAKOJ ZADA^I.
zADA^A 1. iZ rOSTOWA-NA-dONU DO mOSKWY MOVNO DOBRATXSQ PAROHODOM, POEZDOM, AWTOBUSOM I
SAMOLETOM. iZ mOSKWY DO sANKT-pETERBURGA | POEZDOM, AWTOBUSOM I SAMOLETOM. sKOLXKIMI
SPOSOBAMI MOVNO OSU]ESTWITX PUTEESTWIE PO MARRUTU rOSTOW-NA-dONU | mOSKWA | sANKT-
pETERBURG?
rEENIE. o^EWIDNO, ^TO ^ISLO RAZLI^NYH PUTEJ IZ rOSTOWA-NA-dONU DO sANKT-pETERBURGA RAW-
NO 4  3 = 12, TAK KAK, WYBRAW ODIN IZ ^ETYREH WOZMOVNYH SPOSOBOW PUTEESTWIQ OT rOSTOWA-NA-
dONU DO mOSKWY, IMEEM TRI WOZMOVNYH SPOSOBA PUTEESTWIQ OT mOSKWY DO sANKT-pETERBURGA



                     w                            w                            w
(RIS. 1).
                 rOSTOW-NA-dONU                mOSKWA               sANKT-pETERBURG
                              PAROHOD                      POEZD
                                               z                          z
                                  POEZD        *7        AWTOBUS         *7
                                 AWTOBUS                  SAMOLET

                                 SAMOLET
 rIS. 1: sPOSOBY PUTEESTWIQ PO MARRUTU rOSTOW-NA-dONU | mOSKWA | sANKT-pETERBURG.
   sOOBRAVENIQ, KOTORYE BYLI PRIWEDENY PRI REENII ZADA^I 1, POZWOLQ@T SFORMULIROWATX
SLEDU@]EE PROSTOE UTWERVDENIE, KOTOROE BUDEM NAZYWATX OSNOWNYM PRAWILOM KOMBINATORIKI.
   eSLI NEKOTORYJ WYBOR A MOVNO OSU]ESTWITX m RAZLI^NYMI SPOSOBAMI, A DLQ KAVDOGO IZ
\TIH SPOSOBOW NEKOTORYJ DRUGOJ WYBOR B MOVNO OSU]ESTWITX n SPOSOBAMI, TO WYBOR A I B (W
UKAZANNOM PORQDKE) MOVNO OSU]ESTWITX m  n SPOSOBAMI.
   iNA^E GOWORQ, ESLI NEKOTOROE DEJSTWIE (NAPRIMER, WYBOR PUTI IZ rOSTOWA-NA-dONU DO mOS-
KWY) MOVNO OSU]ESTWITX m RAZLI^NYMI SPOSOBAMI, POSLE ^EGO DRUGOE DEJSTWIE (WYBOR PUTI OT
mOSKWY DO sANKT-pETERBURGA) MOVNO OSU]ESTWITX n SPOSOBAMI, TO DWA DEJSTWIQ WMESTE (WYBOR
PUTI OT rOSTOWA-NA-dONU DO mOSKWY, ZATEM WYBOR PUTI OT mOSKWY DO sANKT-pETERBURGA) MOVNO
OSU]ESTWITX m  n SPOSOBAMI.
                                                 42