11. Комбинаторика. Правила комбинаторики. Соединения без повторения

Комбинаторика изучает способы подсчета элементов, разложенных конечных множеств.

Существуют 2 основные правила комбинаторики:

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

Пасть элемент х можно выбрать m способами, а элемент y – n способами, причем любой способ выбора y отличается от способа выбора х. тогда х или y можно выбрать (m+n) способами.

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

Будем рассматривать строки длины n (х₁, х₂…х_n). Среди элементов могут быть и повторяющиеся. Пусть х₁ можно выбрать k₁ способами. . после выбора k_1, х₂ можно выбрать k₂ способами и т.д. элемент х_n можно выбрать k_n способами. Тогда строку х₁,х₂…х_n можно выбрать (k₁*k₂…*k_n) числом способов.

Соединения без повторения

Соединения – различные группы, составленные из каких-либо предметов, отличающихся друг от друга порядком предметов или самими предметами.

Выделяют размещения, сочетания и перестановки.

Перестановка из n элементов – упорядоченное множество состоящее из этих nэлементов. Количество перестановок обозначается Р _n.

Общая формула: Р _k=1*2*3… k= k! (k!-факториал)

Размещение из n элементов по m – упорядоченное подмножество, содержащее m элементов из данных n (m≤ n). Количество размещений обозначается А ^m .

Общая формула: А =

Сочетание из n по m – всевозможные подмножества, содержащие m элементов из данных n. Обозначается С _n

С =

Что бы образовать упорядоченное подмножество, содержащее m элементов из n, нужно:

1. Выбрать mэлементов (С способами)

2. Упорядочить эти m элементов (Р_m способами)

12. Треугольник Паскаля. Бином Ньютона

Треугольник Паскаля — арифметический треугольник, образованный биномиальными коэффициентами. Назван в честьБлеза Паскаля. Если очертить треугольник Паскаля, то получится равнобедренный треугольник. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Продолжать треугольник можно бесконечно. Строки треугольника симметричны относительно вертикальной оси. Имеет применение в теории вероятностей и обладает занимательными свойствами.

0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

5 1 5 10 10 5 1

6 1 6 15 20 15 6 1

7 1 7 21 35 35 21 7 1

Бино́м Нью́то́на — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид

(a+b)ⁿ= aⁿb⁰⁺ a^n-1b¹⁺… a^n-mb^m+ a⁰bⁿ

(a+b)¹= a+b

(a+b)² = a²+ab+b²

(a=b)³ =a³+3a²b+3b²a+b³

13. Комбинаторика с повторениями

Пусть задано множество 

Сочетаниями из m элементов множества A по n элементов с повторениями называются соединения, содержащие n элементов, причем среди них могут быть одинаковые, а отличаются они хотя бы одним элементом, но не порядком.

Т еорема. Если обозначить через   число всех сочетаний с повторением, то

Рассмотрим выборку с повторениями

 

Пусть имеется выборка из   элементов, причем   элементов из них - одинаковые.

 

1.      Число различных перестановок на элементах такой выборки равно:

- число перестановок с   повторениями на множестве из   элементов

2.      Сочетание с повторениями из   элементов по    - неупорядоченная выборка   элементов с возвращением из множества, содержащего   элементов:

 - число различных сочетаний  с повторениями из    элементов по 

3.      Размещения с повторениями из   элементов по   - расположение   различных шаров по   различным ячейкам

   - число различных размещений с повторениями