Основные формулы комбинаторики



Download 0,49 Mb.
Pdf ko'rish
Sana13.04.2020
Hajmi0,49 Mb.
#44356
Bog'liq
formuly kombinatoriki


Практические задачи с решениями можно найти на странице 

http://mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html

 

© 

http://mathprofi.ru



, Емелин А., Высшая математика – просто и доступно! 

Основные формулы комбинаторики 

 

 



1)

 

Факториал

 (произведение всех натуральных чисел от 1 до 

 включительно) 

 

...



)

1

(



)

1

)(



2

(

...



5

4

3



2

1

)!



1

(

)



1

)(

2



(

...


5

4

3



2

1

!



)

1

)(



2

(

...



5

4

3



2

1

)!



1

(

...



5040

7

6



5

4

3



2

1

!



7

720


6

5

4



3

2

1



!

6

120



5

4

3



2

1

!



5

24

4



3

2

1



!

4

6



3

2

1



!

3

2



2

1

!



2

1

!



1













































n



n

n

n

n

n

n

n

n

n

n

n

 

Кроме того: 



1

!

0   



 

 

2)

 

Перестановки, сочетания и размещения без повторений

 

 



Участники действий: множество, состоящее из   различных объектов (либо объектов, 

считающихся в контексте той или иной задачи различными) 

 

Формула количества перестановок

!

n

P

n

 



Типичная смысловая нагрузка

: «Сколькими способами можно переставить  n  объектов?» 

Формула количества сочетаний

!

)!



(

!

m



m

n

n

С

m

n



 

Типичная смысловая нагрузка



: «Сколькими способами можно выбрать  m  объектов из  n ?».  

Поскольку выборка проводится из множества, состоящего  из  n  объектов, то справедливо 

неравенство 

n

0



 

Формула количества размещений

n

n

m

n

A

m

n

)

1



(

...


)

1

(







 

Типичная смысловая нагрузка

: «сколькими способами можно выбрать  m  объектов (из  n  

объектов) и в каждой выборке переставить их местами (либо распределить между ними  

какие-нибудь уникальные атрибуты)» 

Исходя из вышесказанного, справедлива следующая формула: 



m

n

m

m

n

A

P

С



 

И в самом деле: 



m

n

m

m

n

A

n

n

m

n

m

n

n

n

m

n

m

n

m

n

n

m

m

m

n

n

P

С





















)

1



(

...


)

1

(



)

(

...



3

2

1



)

1

(



...

)

1



)(

(

...



3

2

1



)!

(

!



!

!

)!



(

!

 

 


Практические задачи с решениями можно найти на странице 

http://mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html

 

© 

http://mathprofi.ru



, Емелин А., Высшая математика – просто и доступно! 

3) Бином Ньютона и треугольник Паскаля

 

 

Под биномом Ньютона чаще всего подразумевают формулу возведения двучлена 



)

(

b



 в целую 

неотрицательную степень  

...


...

)

(



...

)

(



)

(

)



(

)

(



)

(

)



(

1

1



1

2

2



2

3

3



3

2

2



2

1

1



1

0

5



5

5

4



1

4

5



3

2

3



5

2

3



2

5

1



4

1

5



5

0

5



5

4

4



4

3

1



3

4

2



2

2

4



1

3

1



4

4

0



4

4

3



3

3

2



1

2

3



1

2

1



3

3

0



3

3

2



2

2

1



1

1

2



2

0

2



2

1

1



0

1

1



0













































n



n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

b

C

b

a

C

b

a

C

b

a

C

b

a

C

b

a

C

a

C

b

a

b

C

b

a

C

b

a

C

b

a

C

b

a

C

a

C

b

a

b

C

b

a

C

b

a

C

b

a

C

a

C

b

a

b

C

b

a

C

b

a

C

a

C

b

a

b

C

b

a

C

a

C

b

a

b

C

a

C

b

a

b

a

5

4

3

2

2

3

4

5

4

3

2

2

3

4

3

2

2

3

2

2

b

5ab

b

10a

b

10a

b

5a

a

b

4ab

b

6a

b

4a

a

b

3ab

b

3a

a

b

2ab

a

b

a

1

 

Биномиальные коэффициенты 



m

n

C

 можно рассчитать по стандартной формуле (см. пункт 2), но 

удобнее воспользоваться так называемым треугольником Паскаля, который представляет собой 

бесконечную таблицу биномиальных коэффициентов. По бокам этого треугольника расположены 

единицы, а каждое внутреннее число равно сумме двух ближайших верхних чисел (красные 

метки):  

 

Так, например, для возведения двучлена в 6-ю степень следует руководствоваться общей 



формулой бинома, после чего сразу записать числа из строки № 6 треугольника Паскаля: 

 

6



5

4

2

3

3

2

4

5

6

b

6ab

b

15a

b

20a

b

15a

b

6a

a











6



6

6

5



1

5

6



4

2

4



6

3

3



3

6

2



4

2

6



1

5

1



6

6

0



6

6

)



(

b

C

b

a

C

b

a

C

b

a

C

b

a

C

b

a

C

a

C

b

a

 

 



Кроме того, данная таблица позволяет быстро находить отдельно взятые биномиальные 

коэффициенты (например, в целях проверки вычислений по формуле 

!

)!

(



!

m

m

n

n

С

m

n



): 


 

2

6



C

 – находим строку № 6 и (внимание!) 2 + 1 = 3-й элемент слева (зелёный кружок):  

15

2

6





C

5



9

C

 – находим строку № 9 и выбираем 5 + 1 = 6-й элемент слева (малиновый кружок):  

126

5

9





C

3



10

C

 – находим строку № 10 и выбираем 3 + 1 = 4-й элемент слева (коричневый кружок):  

120

3

10





C



Практические задачи с решениями можно найти на странице 

http://mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html

 

© 

http://mathprofi.ru



, Емелин А., Высшая математика – просто и доступно! 

4)

 

Комбинаторное правило суммы и комбинаторное правило произведения

 

 

Если объект 



A

 можно выбрать из некоторого множества объектов 



 способами, а другой объект 

B

  – 


 способами,  то выбор объекта 

A

 или объекта 



B

 (без разницы какого) возможен 



n

  

способами. 

 

Если объект 



A

 можно выбрать из некоторого множества объектов 



 способами и после каждого 

такого выбора объект 



B

 можно выбрать 



 способами,  то упорядоченная пара объектов 

)

;



(

B

A

 

может быть выбрана  mn  способами. 



 

Данные принципы справедливы и для бОльшего количества объектов.   

 

Важная содержательная часть правил состоит в том, знак «плюс» понимается и читается как союз 



ИЛИ, а знак «умножить» – как союз И.   

 

 



5)

 

Перестановки, сочетания и размещения с повторениями

 

 

Участники действий: множество, состоящее из объектов, среди которых есть одинаковые 



(либо считающиеся таковыми по смыслу задачи) 

 

Формула количества перестановок с повторениями

!

...


!

!

!



!

3

2



1

)

(



k

повт

n

n

n

n

n

n

P





,  

где 


n

n

n

n

n

k





...

3

2



1

 

Типичная смысловая нагрузка



: «Количество способов, которыми можно  переставить  

n  объектов, среди которых 1-й объект повторяется 

1

n  раз, 2-й объект повторяется 

2

n  раз,  

3-й объект – 

3

n  раз,…,  k -й объект – 



k

n  раз» 

Следует отметить, что в подавляющем большинстве задач в совокупности есть и уникальные  

(не повторяющиеся) объекты, в этом случае соответствующие значения 

i

 равны единице,  

и в практических расчётах их можно не записывать в знаменатель. 



Формула количества сочетаний с повторениями

!

)!



1

(

!



)

1

(



1

)

(



m

n

m

n

С

С

m

m

n

m

повт

n







 

Типичная смысловая нагрузка

: «Для выбора предложено 

n  множеств, каждое из которых 

состоит из одинаковых объектов. Сколькими способами можно выбрать  m  объектов?» 

То есть, здесь в выборке могут оказаться одинаковые объекты, и если 



n

 , то совпадения точно 

будут. По умолчанию предполагается, что исходная совокупность содержит не менее   объектов 



каждого вида, и поэтому выборка может полностью состоять из одинаковых объектов.  

Формула количества размещений с повторениями

m

m

повт

n

n

A

)



(

 

Типичная смысловая нагрузка



: «Дано множество, состоящее из 

n  объектов, при этом любой 

объект можно выбирать неоднократно. Сколькими способами можно выбрать  m  объектов, 

если важен порядок их расположения в выборке? » 

Для бОльшей ясности здесь удобно представить, что объекты извлекаются последовательно (хотя 

это вовсе не  обязательное условие). В частности, возможен случай, когда из   имеющихся 

объектов   раз будет выбран какой-то один объект. 



Download 0,49 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish