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

                         x 1. oSNOWNOJ PRINCIP KOMBINATORIKI. pERESTANOWKI, RAZME]ENIQ I SO^ETANIQ

  1.4. pERESTANOWKI.
oPREDELENIE 1. pUSTX n 2 N0 B = fb1
 b2
 : : :
 bng pERESTANOWKOJ IZ \LEMENTOW MNOVEST
                                     ,                       .                                               -
WA B NAZYWAETSQ WSQKOE RAZME]ENIE \TOGO MNOVESTWA PO n \LEMENTOW.
    o^EWIDNO, ^TO KOLI^ESTWO WSEWOZMOVNYH PERESTANOWOK MNOVESTWA B NE ZAWISIT OT PRIRODY
\LEMENTOW MNOVESTWA B. pO\TOMU KOLI^ESTWO PERESTANOWOK PROIZWOLXNOGO n-\LEMENTNOGO MNO-
VESTWA OBOZNA^IM ^EREZ Pn.
pRIMER 1. rASSMOTRIM TREH\LEMENTNOE MNOVESTWO B = f1
 2
 3g. wSE PERESTANOWKI \TOGO MNO-
VESTWA: (1
 2
 3), (1
 3
 2), (2
 1
 3), (2
 3
 1), (3
 1
 2), (3
 2
 1). tAKIM OBRAZOM, P3 = 6.
    bUDEM OBOZNA^ATX SIMWOLOM n! (^ITAETSQ \\N FAKTORIAL") PROIZWEDENIE WSEH NATURALXNYH
^ISEL OT 1 DO n WKL@^ITELXNO: n! = 1  : : :  n. uDOBNO S^ITATX. ^TO 0! = 1.
tEOREMA 1. Pn = n!.
dOKAZATELXSTWO. sOGLASNO OPREDELENI@ PERESTANOWKI
                                     Pn = Ann = n  (n ; 1)  : : :  1 = n!:
zADA^A 1. sKOLXKIMI SPOSOBAMI MOVNO RAZMESTITX 5 KNIG NA POLKE?
rEENIE. ~ISLO SPOSOBOW RASSTANOWKI KNIG RAWNO ^ISLU SPOSOBOW UPORQDO^ENIQ MNOVESTWA,
SOSTOQ]EGO IZ 5 \LEMENTOW, TO ESTX
                                           P5 = 1  2  3  4  5 = 120:
zADA^A 2. sKOLXKIMI SPOSOBAMI MOVNO UPORQDO^ITX MNOVESTWO
                                                     f1
 2
 : : :
 2ng
TAK, ^TOBY KAVDOE ^ETNOE ^ISLO IMELO ^ETNYJ NOMER?
rEENIE. ~ETNYE ^ISLA MOVNO RASSTAWITX NA MESTAH S ^ETNYMI NOMERAMI (TAKIH MEST n) n!
SPOSOBAMI KAVDOMU SPOSOBU RAZME]ENIQ ^ETNYH ^ISEL NA MESTAH S ^ETNYMI NOMERAMI SOOTWET-
STWUET n! SPOSOBOW RAZME]ENIQ NE^ETNYH ^ISEL NA MESTAH S NE^ETNYMI NOMERAMI. pO\TOMU OB]EE
^ISLO PERESTANOWOK UKAZANNOGO TIPA PO PRAWILU UMNOVENIQ RAWNO n!  n! = (n!)2.
zADA^A 3. sKOLXKO MOVNO SOSTAWITX PERESTANOWOK IZ n \LEMENTOW, W KOTORYH DANNYE DWA \LE-
MENTA NE STOQT RQDOM?
rEENIE. oPREDELIM ^ISLO PERESTANOWOK, W KOTORYH DANNYE DWA \LEMENTA a I b STOQT RQDOM.
mOGUT BYTX SLEDU@]IE SLU^AI: a STOIT NA PERWOM MESTE, a STOIT NA WTOROM MESTE, : : : , a STOIT
NA (n ; 1)-M MESTE, A b STOIT PRAWEE a ^ISLO TAKIH SLU^AEW RAWNO n ; 1. kROME TOGO, a I b MOVNO
POMENQTX MESTAMI, I, SLEDOWATELXNO, SU]ESTWUET 2(n ; 1) SPOSOBOW RAZME]ENIQ a I b RQDOM.
kAVDOMU IZ \TIH SPOSOBOW SOOTWETSTWUET (n ; 2)! PERESTANOWOK DRUGIH \LEMENTOW. sLEDOWATELXNO,
^ISLO PERESTANOWOK, W KOTORYH a I b STOQT RQDOM, RAWNO 2  (n ; 1)  (n ; 2)! = 2  (n ; 1)!. pO\TOMU
ISKOMOE ^ISLO PERESTANOWOK RAWNO n! ; 2  (n ; 1)! = (n ; 1)!  (n ; 2).
zADA^A 4. sKOLXKIMI SPOSOBAMI MOVNO RASPOLOVITX NA AHMATNOJ DOSKE 8 LADEJ TAK, ^TOBY
ONI NE MOGLI BITX DRUG DRUGA?
rEENIE. pRI UKAZANNOM RASPOLOVENII LADEJ NA KAVDOJ WERTIKALI I KAVDOJ GORIZONTALI STO-
IT LIX ODNA LADXQ. rASSMOTRIM ODNO IZ TAKIH RASPOLOVENIJ LADEJ. pUSTX a1 | NOMER WERTIKA-
LI, W KOTOROJ STOIT LADXQ IZ PERWOJ GORIZONTALI, a2 | NOMER WERTIKALI, W KOTOROJ STOIT LADXQ
IZ WTOROJ GORIZONTALI, : : :, a8 | NOMER WERTIKALI, W KOTOROJ STOIT LADXQ IZ WOSXMOJ GORIZONTA-
LI, tOGDA (a1 
 a2
 : : :
 a8) ESTX NEKOTORAQ PERESTANOWKA ^ISEL 1
 2
 : : :
 8. sREDI ^ISEL a1 
 a2
 : : :
 a8
NET NI ODNOJ PARY RAWNYH, INA^E DWE LADXI POPALI BY NA ODNU WERTIKALX. sLEDOWATELXNO, KAV-
DOMU RASPOLOVENI@ LADEJ SOOTWETSTWUET OPREDELENNAQ PERESTANOWKA ^ISEL 1
 2
 : : :
 8. nAOBOROT,
KAVDOJ PERESTANOWKE ^ISEL 1
 2
 : : :
 8 SOOTWETSTWUET TAKOE RASPOLOVENIE LADEJ, PRI KOTOROM ONI
NE BX@T DRUG DRUGA. sLEDOWATELXNO, ^ISLO ISKOMYH RASPOLOVENIJ LADEJ RAWNO P8 = 8! = 40 320.
                                                      45