.RU

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


^ Правила суммы и произведения

Правило суммы

Если объект a можно выбрать p способами, а объект b – другими q способами, то выбор “либо a, либо b” может быть осуществлен p+q способами. При этом выборы a и b являются взаимно исключающими.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы либо одно яблоко, либо одну грушу (взаимоисключающие события) можно 3+5 = 8 способами.


^ Обобщённое правило суммы

Пусть дано r множеств Ti (i=1,…,r), каждое из которых содержит ni элементов (Ti - ni множество), причём множества взаимно не пересекаются: TiTj= при ij. Тогда объединение этих множеств S=T1 T2…Tr есть (n1+…+nr)-множество. .

Правило произведения

Если объект a можно выбрать p способами, и после каждого из таких выборов объект b можно выбрать q способами, то выбор “a и b” в указанном порядке может быть осуществлен p·q способами. При этом выборы a и b являются независимыми.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы одно яблоко и одну грушу (события происходят совместно) можно 3·5 = 15 способами.


^ Обобщённое правило произведения

Пусть дано r множеств Ti (i=1,…,r), каждое из которых содержит ni элементов (Ti - ni множество), причем неважно, пересекаются ли Ti или нет. Осуществим выбор элементов последовательно из множеств Ti.

Выбирая из Т1, получим множество М1 – множество всех возможных выборок по одному элементу из Т1. (М1 – n1-множество). М1=Т1

Выбирая сначала из Т1, потом из Т2, получаем множество М2 упорядоченных пар элементов из Т1 и Т2 (М2 – n1n2-множество). М2=Т1xТ2=M1xТ2.

Аналогично М3=Т1xТ2xТ3=M2xТ3 – множество упорядоченных троек (n1n2n3-множество); М4=Т1xТ2xТ3xТ4=M3xТ4 – n1n2n3n4-множество; … ; Мr= Mr-1xТr – n1n2…nr-множество. То есть произведение r множеств есть n1n2…nr-множество.

.


^ Лекция 2. Виды выборок

Комбинаторику интересуют результаты отбора (построения выборок) и упорядочения элементов, выраженные в комбинаторных числах. Если после выбора элемент из множества удаляется (его нельзя еще раз выбрать) – это выборка без повторений. Если после выбора элемент из множества не удаляется и его можно выбрать еще раз – это выборка с повторениями. Если в выборках важен порядок элементов – это перестановки. Если же выборки с разным порядком элементов считаются одинаковыми – это сочетания.


С понятием отбора элементов в комбинаторике связано понятие выборки. Выборки могут быть упорядоченными и неупорядоченными, без повторений элементов и с повторениями.

Обозначим знаком отношение упорядоченности. Тогда запись означает, что a предшествует b, а - a предшествует или совпадает с b.















r-перестановка

без повторений

из n-множества



r-перестановка

c повторениями

из n-множества



r-сочетание

без повторений

из n-множества



r-сочетание

с повторениями

из n-множества




Число перестановок обозначается буквой ^ P (permutation), число сочетаний – буквой C (conjunction). Произносится:

- “P из n по r” или “P по r из n”;

- “C из n по r” или “C по r из n”.

Все числа, существующие в комбинаторике, так или иначе, являются комбинациями этих четырех чисел.

^ Формулы основных комбинаторных чисел Теорема 1. Число перестановок без повторений
Число r-перестановок без повторений из элементов n-множества равно

.

# Пусть дано n-множество S и Ti – ni-подмножества множества S, где i=1,2,…,n. Тогда доказательство есть частный случай применения обобщенного правила произведения, где

n1=n, n2=n-1, n3=n-2, …, nr=n-r+1 #


Следствие 1. Число перестановок n предметов равно:

.

Следствие 2. .

Следствие 3. При r>n (в перестановках с повторениями r не может быть больше n, так как мы не можем из n-множества забрать более, чем n элементов).

По определению, (ноль предметов можно выбрать из n предметов единственным способом – ничего не выбирать).

^ Теорема 2. Число перестановок с повторениями
Число r-перестановок с повторениями из n-множества равно .

# Следует из обобщённого правила произведения, где n1=n, n2=n, n3=n, …, nr=n. (Выбираем из исходного множества какой-либо элемент, ставим его на очередное место в перестановке, но из исходного множества не удаляем и его можно будет выбрать ещё раз) #


В перестановках с повторениями r может быть больше n, так как при выборе элемента мы не удаляем его из множества и можем выбрать еще раз.

^ Теорема 3. Число сочетаний без повторений
Число r-сочетаний без повторений из n-множества равно

.

# Число r-перестановок без повторений из n-множества равно , однако порядок элементов в r выборке здесь нас не интересует. Число возможных перестановок элементов в r-выборке равно . Следовательно, число сочетаний без повторений в r! раз меньше числа перестановок без повторений. #


Следствие 1.

Свойство симметричности для числа сочетаний без повторений: .

# #

Следствие 2. , т.к. (Ноль предметов выбрать из n предметов можно единственным способом – ничего не выбирать. Выбрать n предметов из n без учета порядка можно единственным способом – выбрать все n предметов.)

Следствие 3. При r>n (в сочетаниях с повторениями r не может быть больше n, так как мы не можем из n-множества забрать более, чем n элементов).


Числа являются коэффициентами бинома Ньютона (a+b)n:



Например, (a+b)3 = a3 + 3a2b + 3ab2 + b3

.

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

Ещё одно обозначение этих чисел: .


^ Рекуррентная формула для числа сочетаний без повторений. Треугольник Паскаля.

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

Зафиксируем в n множестве некоторый элемент и рассмотрим r сочетания без повторений из этого n множества. Относительно любого сочетания можно сказать, содержит ли оно данный зафиксированный элемент или нет.

Если содержит, то остальные (r-1) элементов сочетания выбираются из (n-1)-множества. Число способов выбрать (r-1) элемент из (n-1)-множества без учета порядка: .

Если не содержит (в сочетании этого элемента нет), то это r сочетания из (n-1)-множества (то есть из множества, в котором удален данный элемент). Число способов выбрать r элементов из (n-1)-множества без учета порядка: .

Эти два случая взаимоисключающие, поэтому по правилу суммы



с начальными условиями

, и при r>n .

Таким образом, числа сочетаний без повторений (биномиальные коэффициенты) можно вычислять не только по прямой формуле, но и рекуррентно. Построим таблицу для биномиальных коэффициентов. Исходя из начальных условий, в столбце 0 и на диагонали находятся единицы, а все клетки, находящиеся выше диагонали, содержат нули. Из рекуррентной формулы следует, что для получения значения в n-й строке r-м столбце (заданная клетка) нужно сложить значение в (n-1) й строке r-м столбце (клетка сверху над заданной) и значение в (n 1) й строке (r-1)-м столбце (клетка сверху слева от заданной).


r

n

0

1

2

3

4

5

6

7

8



Бином



0

1




























(a+b)0 = 1

1=20

1

1

1

























(a+b)1 = 1a+1b

2=21

2

1

2

1






















(a+b)2 = 1a2+2ab+1b2

4=22

3

1

3

3

1



















(a+b)3 = 1a3+3a2b+3ab2+1b3

8=23

4

1

4

6

4

1
















(a+b)4 = 1a4+4a3b+6a2b2+4ab3+1b4

16=24

5

1

5

10

10

5

1















32=25

6

1

6

15

20

15

6

1













64=26

7

1

7

21

35

35

21

7

1










128=27

8

1

8

28

56

70

56

28

8

1







256=28






























Эта таблица называется треугольником Паскаля. Он позволяет быстро находить числа сочетаний без повторений и не требует вычисления факториалов.

Видно, что в каждой строке таблицы сумма чисел равна степени двойки. Это свойство чисел сочетаний без повторений, которое будет доказано ниже.


^ Некоторые комбинаторные соотношения для чисел сочетаний без повторений

(1).

# Следует из того, что – коэффициенты бинома:

.

Подставляя вместо a единицу, вместо b – t, получим формулу (1). #


(2). . # получается из (1) при t =1. #


(3). . # следует из (1) при t = -1. #


(4).

# продифференцируем (1) по t: ,

затем подставим t =1: #

(5).

# продифференцируем (1) по t k раз:

подставляем t = -1:

,

разделим левую и правую часть на k!

#


(6).

# проинтегрируем левую и правую часть (1) от 0 до 1:

,

. #


(7). . # интегрируем (1) от -1 до 0. #


(8). - гармонический ряд


(9).


(10). Если p – простое число, то каждое из чисел делится на p.

# , , , … , . #



pravoslavie-i-religiya-budushego-stranica-9.html
pravoslavie-na-smolenshine.html
pravoslavie-v-karelii-v-hh-v-v-zerkale-statistiki-v-m-pivoev-otv-red-a-m-pashkov-m-v-pulkin.html
pravoslavnaya-cerkov-cheshskih-zemel-i-slovakii.html
pravoslavnaya-enciklopediya-dannaya-rabota-predstavlyaet-soboj-sistematicheskij-obzor-istorii-drevnej-cerkvi-pomestnih.html
pravoslavnaya-kultura-cennosti-klassicheskoj-nauki-obrazovaniya-i-iskusstva.html
  • assessments.bystrickaya.ru/chtenie-osho-mozhet-izmenit-vsyu-tvoyu-zhizn-on-vstryahivaet-tebya-i-zastavlyaet-prosnutsya-moe-poslanie-ne-doktrina-i-ne-filosofiya-moe-poslanie-alhimiya-nauka-stranica-2.html
  • write.bystrickaya.ru/figdor-g-f-49-deti-razvedennih-roditelej-mezhdu-travmoj-i-nadezhdoj-psihoanaliticheskoe-issledovanie-stranica-4.html
  • portfolio.bystrickaya.ru/opticheskie-illyuzii-formi-izdeliya.html
  • literature.bystrickaya.ru/botanika-viberite-pravilnie-otveti-na-voprosi.html
  • write.bystrickaya.ru/glava-15-posleslovie-mir-cherez-kulturu.html
  • student.bystrickaya.ru/1-psihologiya-kak-nauka.html
  • tasks.bystrickaya.ru/13-razrabotka-obshej-konstruktivno-komponovochnoj-shemi-stancii-i-vibor-sostava-modulej.html
  • paragraf.bystrickaya.ru/yubilej-velikogo-novgoroda-polgoda-spustya-opit-analiza-kontenta-novgorodskih-sajtov.html
  • reading.bystrickaya.ru/koksharov-a-belkina-e-novij-glava-fsfr-obojdetsya-bez-bembi-hulhachieva2.html
  • spur.bystrickaya.ru/mergaliev-b-k-e-k-docent.html
  • abstract.bystrickaya.ru/3obem-disciplini-tabl-1-31-obem-disciplini-i-vidi-uchebnoj-raboti.html
  • notebook.bystrickaya.ru/instrukciya-po-deloproizvodstvu-v-administracii-rostovskoj-oblasti-obshie-polozheniya.html
  • zadachi.bystrickaya.ru/proektirovanie-lokalno-vichislitelnoj-seti-chast-10.html
  • notebook.bystrickaya.ru/error404.html
  • laboratornaya.bystrickaya.ru/rabochaya-programma-dlya-studentov-ochnoj-formi-obucheniya-specialnosti-090303-65-informacionnaya-bezopasnost-avtomatizirovannih-sistem.html
  • bukva.bystrickaya.ru/poryadok-ischisleniya-i-uplati-ndfl-po-viigrisham.html
  • kontrolnaya.bystrickaya.ru/programmi-razvitie-melioracii-selskohozyajstvennih-zemel-v-respublike-mordoviya-na-period-do-2020-goda-pravitelstvo-respubliki-mordoviya-postanovlyaet-stranica-18.html
  • predmet.bystrickaya.ru/rezultat-ispolneniya-gosudarstvennoj-funkcii-sbornik-rukovodyashih-dokumentov-gosudarstvennoj-inspekcii-po-malomernim.html
  • teacher.bystrickaya.ru/finansi-v-sisteme-denezhnih-otnoshenij-rinochnogo-hozyajstva-stranica-4.html
  • doklad.bystrickaya.ru/uchebno-metodicheskij-kompleks-disciplina-fizika-tvyordogo-tela-chelyabinsk.html
  • paragraph.bystrickaya.ru/metodicheskie-rekomendacii-k-prakticheskim-zanyatiyam-po-mdk-02-03-teoreticheskie-i-metodicheskie-osnovi-organizacii-produktivnih-vidov-deyatelnosti-detej-doshkolnogo-vozrasta.html
  • university.bystrickaya.ru/glava-19-dmitrij-gluhovskij-metro-2033.html
  • uchitel.bystrickaya.ru/psihologo-pedagogicheskie-usloviya-formirovaniya-konstruktivnogo-roditelskogo-otnosheniya-k-narkozavisimim-yunosham.html
  • holiday.bystrickaya.ru/ocenka-aktivov-i-obyazatelstv-stoimost-kotorih-virazhena-v-inostrannoj-valyute.html
  • urok.bystrickaya.ru/programma-disciplini-obshaya-sociologiya-dlya-napravleniya-080504-65-gosudarstvennoe-i-municipalnoe-upravlenie-podgotovki-specialistov-avtori-e-r-yarskaya-smirnova-d-s-popov-e-mail-elena-iarskaiasocpolicy-ru.html
  • nauka.bystrickaya.ru/uchebno-metodicheskij-kompleks-udk-bbk-a-rekomendovano-k-izdaniyu-uchebno-metodicheskim-sovetom-instituta-socialnih-i-gumanitarnih-znanij.html
  • otsenki.bystrickaya.ru/sovershennaya-konkurenciya-opredelenie-konkurencii-kak-ekonomicheskogo-yavleniya.html
  • institut.bystrickaya.ru/tehnicheskij-reglament-stranica-6.html
  • student.bystrickaya.ru/14-parametrov-kak-nauchno-tehnicheskaya-disciplina-izuchaet-opasnosti-ugrozhayushie-cheloveku-v-srede-obitaniya-zakonomernosti.html
  • composition.bystrickaya.ru/pl-lenina-1-ot-20-marta-2012goda.html
  • klass.bystrickaya.ru/balaaj-balabashasi-tairibi-ata-analarmen-zhrgzletn-zhmis-trler-ata-analarmen-zhrgzletn.html
  • apprentice.bystrickaya.ru/vozrastnaya-periodizaciya-db-elkonina.html
  • uchitel.bystrickaya.ru/programma-povisheniya-kvalifikacii-nauchno-pedagogicheskih-rabotnikov-poprioritetnomu-napravleniyu-problemi-podgotovki-kadrov-po-prioritetnim-napravleniyam-nauki-tehniki-i-kriticheskim-tehnologiyam.html
  • kanikulyi.bystrickaya.ru/zhenski-polovi-organi-za-priemane-na-naredba-za-medicinskata-ekspertiza.html
  • literature.bystrickaya.ru/borba-chelovechestva-prohodit-prezhde-vsego-v-duhovnom-plane-predislovie-perevodchika.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.