Viii-боб. Комбинаторика. Э тимоллар назарияси элементлари

m uaoi 6-


1k;


-1 oa u бё1 ёайдёбё0)
Барча элементлар m та бу икдан уар бир уринлаштиришдан бир
элементдан олсак m -1 та 2 т ан уринлаштириш уосил булади, ва 2 тадан
уринлаштиришнинг умумий с и (m -1)m булади. Булардан бошка 2 тадан
ик куриниб турибди. Демак:
= m( m — 1)
аштиришлар тузиш учун, уозиргина тузилган 2
дан уар бирини олиб, унинг ёнига колган барча m--2
дан куйиб чикамиз. У уолда куйидаги 3 тадан
ни топамиз:
abc, abd,..., abk, abl; (m — 2 да u бё( ёа0 дёбё0)
acb, acd,..., ack, acl; (m — 2 да u бё( ёа 0дёбё0)


la, lb, 1c


тадан уринлашт
та элементни \
уринлаштир


uadi 6


^ 1ka, 1kb, .., (m- 2 da u dei ёаеоёбее)


(


2 тадан уринлаштиришларнинг уаммаси m(m--1) га тенг ва уар биридан (m -2) та 3 тадан уринлаштириш олингани учун, бундай уринлаштиришларнинг уаммаси куйидагича булади:
(m-2)[m(m-1)]=m(m-1)(m-2).
Шундай килиб:
А^ = m( m —1)( m — 2).


@MATEMATIKA_VARIANT




@matematika_variant


Шунга ухшаш:


А4 = m( m -1)( m - 2)( m - 3).
A_m = m( m —1)( m — 2)( m — 3)( m — 4).


ва умуман:
A_m = m( m —1)( m — 2)...[m — (n — 1)].
Уринлаштиришлар сонининг формуласи ана шундай; уни суз билан


цуйидагича айтиш мумкин:
m та элементдан n тадан олиб тузиш мумкин булган барча
уринлаштиришларнинг сони, энг каттаси m булган n та кетма- бутун
сонлар купайтмасига тенг.
Шундай цилиб:
А₄² = 4 - 3 = 12; A3 = 4 - 3 - 2 = 24; А4 = 8 - 7 - 6 -
ва шунга ухшаш.
Масалалар. 1) Синфда 10 фан уцилади ва кар ку
Кунлик дарс неча турли усул билан тацсимлаб цуйил
Дарсларнинг барча мумкин булган кунлик тацс
тадан олиб тузиш мумкин булган барча уринлаштиришларга жуда ухшаш
эканлиги равшан; шунинг учун тацсимот усулларининг каммаси цуйидагидан
иборат булиши керак:


л дарс утилади.
мкин?
оти ун элементдан 5

2. 
   Бутун сонларнинг кар бири
   

ифода цилинадиган булса. цанча б;
Изланган сон 9 га цийм;

уринлаштириш сонидан иборат;

2. 
   Хар бири учта т
   

бутун сон тузиш мум
10 та ракам:
уринлаштириш тузи
тадан уринлаштири
сони 9 га к
булса, ш


- 6


30240.
а кар хил цийматли рацам билан
он тузиш мумкин?
атли рацамдан 3 тадан олиб тузилган
мак, у 9- 8 • 7=504.
и рацам билан ифода цилинадиган булса, цанча


9 ни учтадан жойлаштириб 10-9-8=720
умкин, лекин бу сондан 0 раками билан бошланган 3
иарни чицариб ташлаш керак. Бундай уринлаштириш
ли ракамни 2 тадан канча уринлаштириш тузиш мумкин
i тенг, яони 9-8=72; демак, изланган сон 720-72=648.
алмаштиришлар. Агар уринлаштиришлар m та элементдан n
нган булса (яони фацат элементларининг тартиби билан фарц
ундай уринлаштиришлар урин алмаштиришлар деб аталади.
Ман, икки элемент а ва b дан урин алмаштириш 2 ни 2 тадан
уринлаштириш булади, яони ab ва ba : уч элементдан шрин алмаштириш 2
ни 3 тадан уринлаштириш булади, яони abc, acb, bac, bca, cab, cba ва шулар
каби m та элементдан мумкин булган барча урин алмаштиришлар сони Pm
билан белгиланади (бунда Р французча "permutation" сузининг бош карфи,
унинг маоноси, "урин алмаштириш" демакдир).
m та элементдан урин алмаштиришлар m ни m тадан уринлаштириш деган суз булгани учун, урин алмаштиришлар формуласи цуйидагича булади:


та


@MATEMATIKA_VARIANT




@matematika_variant


P_m = Am = m(m-1)(m- 2)...3- 2-1 = 1-2- 3-...(m- 1)m
m та элементдан мумкин булган барча урин алмаштиришларнинг сони
1 дан m гача натурал сонларнинг купайтмасига тенг.

1. 
   Туккизта кар хил кийматли ракам билан нечта туккиз хонали сон
   ёзиш мумкин?
   

Изланган сон:
Р9 = 1-2-3-4-5-6-7-8-9=362880

2. 
   12 кишилик овкат козирланган столга 12 кишини неча турли
   

утказиш мумкин?
Утказиш турларининг сони куйидагига тенг:
1-2-3 ... 12 = 479001600
Эслатма. 1 дан m гача натурал сонларнинг купайтмаси (
белгиланади: m! )m нинг ортиб бориши билан жуда тез усади:
булганда у 479001600, m=100 булганда у шундай
килинадики, уни тасвирлаш учун 158 ракам ёзиш керак
3. Группалаш. Агар m та элементдан n тада ш мумкин булган
барча уринлаштиришларни бир-бирларидан, энг ка а бир элемент билан
фарк киладиганларини танлаб олсак, у колда группалар деб айтилган
бирлашмаларни косил киламиз.
Масалан, турт элемент a,b,c ва d
бундай булади:
abc, abd, acd, b
Агар бу группаларнинг дкар рида мумкин булган барча урин
алмаштиришларни килсак, турт элементдан 3 талаб мумкин булган барча уринлаштиришларни косил киламиз:


он


бундай
нончи, m=12
илан ифода


a


abc


a


acd
adc


a


bcd bdc


ан олиб тузилган группалар


bca cad cba


bad bda dab dba


cad cda dac dca


cbd cdb dbc dcb


^ндай уринлаштиришларнинг сони 6- 4=24 булади.
ундай килиб m та элементдан n тадан олиб тузилган барча
уринлаштиришлар сони, m та элементдан n тадан олиб тузилган барча
группалар сони билан n та элементдан тузиш мумкин булган барча урин
алмаштиришлар сонининг купайтмасига тенг, яони:
Aⁿ = CⁿP ,
m m n
бунда Cⁿ_m ифода m та элементдан n тадан олиб тузилган барча группалар сонини белгилайди (С — французча "combinaison" сузининг бош карфи, унинг маоноси "группалаш" демакдир).


@MATEMATIKA_VARIANT




@matematika_variant


Бундан группаларнинг куйидаги формуласини чикарамиз:
₌Ai₌ m(^т -1)(^т - 2)...[m - (n -1)]
^m P 1-2 - 3...n ’
n
Масалан:


C =


4 - 3 ₃_4 - 3 - 2
1-2 ^{, 4} 1-2 - 3


ва шунга ухшаш.

1. 
   Бир вазифага курсатилган 10 номзоддан уч киши сайланиши керак.
   

Сайловдаги турли имкониятлар канча булиши мумкин?
Изланган сон ун элементни 3 тадан жойлаштириб тузил
булган барча группалар сонини ташкил килади, яони
C ₌ 10-9-8₌120.
¹⁰ 1-2 - 3

2. 
   52 хил картадан иборат дастадан 13 картани неча хил килиб олиш
   

мумкин?
Изланган сон, 52 та картадан 13
сонидан иборат, яони:


мкин





тузилган группалар


_и _ 52-51-50...40
⁵² “ 1-2...13
4. Группалар сони формула
формуласининг сурат ва ма
купайтириб, уни бошкача шаклг
1)...[m-(n-1)] -1-2-3 ... (m-n) куп
урнини алиштириб шундай ёз
1-2-3... (m
Демак:


тад


3559600


ошкача шакли. Группалар сони
ушбу 1-2-3...(m-n) купайтмага
тириш мумкин; у уолда суратда m(m-
гайтма чикади, бундан купайтувчиларнинг
булади:
-1)] ... m


шуни


1 - 2 - 3...( m - 1)m


P
m


1-2-3-...n-1-2-3...(m-n) P -P
n m- n
шнинг хоссаси. Бу формула n ни m-n билан алмаштириб,
ламиз:
_Cm- „ ₌ 1-2 - 3...( m-1)m ₌ Pm
^m 1-2-3-...(m-n) 1-2-3...n P -P_m__n ’
у формулани утган формула билан солиштириб, шуни топамиз:


Cⁿ
m


^m- n


Куйидаги оддий мууокама уам шу хулосага келтиради: агар m та элементдан, бир группа тузиш учун кандай булмасин n та элементни танлаб олсак, колган элементларнинг уаммаси m-n та элементдан бир группа ташкил килади. Шундай килиб, n та элементдан тузилган уар бир группага m-n та элементдан тузилган бир группа туьри келади, ва аксинча; демак:


Cⁿ
m


m-n


@MATEMATIKA_VARIANT




@matematika_variant


Бу муносабат, агар n > — m булса, m та элементдан n тадан олиб
2
сонини топиши соддалаштиришга имкон беради.


тузилган группалар Масалан:


97 _ ^3
100 100


100-99-98
- - = 161700
1-2 - 3