18. Комбинаторика без повторений элементов. Размещения, перестановки и сочетания без повторений (л).

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

В комбинаторике часто используют произведение натуральных чисел от единицы до n. Кратко обозначают n!=1*2*…*n

Размещениями из n элементов по m называются комбинации длины m (mn), отличающиеся друг от друга порядком или составом элементов.

(обозначение А^m_n - А из n по m).

формула: А^m_n =

Пример: Сколькими способами можно составить комбинацию из трех букв слова камзол?

Решение: А³₆=6*5*4=120

Перестановками из n элементов P_n называют размещения из n элементов по n, т.е. P_n = A^m_n = n!

Пример: Сколькими способами можно переставить буквы в слове столица?

Решение: P₇ = 7! = 1*2*3*4*5*6*7 = …

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

(обозначение С^m_n – C из n по m).

формула: A^m_n = P_mC^m_n

C^m_n =

Пример: сколькими способами можно выбрать две буквы из букв слова родина?

Решение: C^m_n =

18. Комбинаторика с повторениями элементов. Размещения, перестановки и сочетания с повторениями.

Комбинаторика с повторениями элементов. Элементы комбинации в этих задачах могут повторяться. Исходный набор не конкретные объекты, а типы элементов и количество одинаковых элементов (типов) в комбинациях определяется только условиями задачи.

Размещение с повторениями A^m_n из n типов элементов по m элементов называются комбинации, отличающиеся друг от друга или типом элементов или их порядком в комбинации.

Формула А^m_n = n^m

Пример: сколькими различными способами можно составить комбинаций длины 8 из двух различных типов чисел «0» и «1»?

Решение: Число типов элементов равно 2 (n=2), а длина m составляемых комбинаций – 8 (м=8) , следовательно, А⁸₂ = 2⁸=256

Перестановки с повторениями обозначаются P(3,2,2).

Например, при рассмотрении слова колокол необходимо указать , что буква «о» встречается 3 раза, буква «к» - 2 раза, буква «л» - 2 раза. Общее количество букв в перестановках не изменяется и равно сумме всех букв в слове: 7=3+2+2

Формула: P(k₁,k₂,…,k_m) =

«колокол» = P(3,2,2,) =

Сочетания с повторениями называют комбинации из m предметов n типов, отличающихся составом предметов (обозначаются С^m_n). Комбинации должны отличаться друг от друга хотя бы одним предметов.

Способ подсчета общего количества С^m_n таких комбинаций основан на специальном кодировании каждой комбинации двоичным кодом. Кодировать будем следующим образом: каждому типу припишем такое количество единиц, сколько предметов данного типа входит в комбинацию, а предметы различного типа отделим друг от друга нулями. (см. Тетрадь). При этом общее количество единиц в коде соответствует количеству m предметов в комбинации, а число разделяющих нулей равно числу необъодимых границ (n-1). Т.об. образуется взаимно однозначное соответствие между сочетаниями с повторениями элементов и комбинациями в виде двоичных кодов и, следовательно, их общее количество одинаково. Количество различных двоичных кодов с фиксированным числом единиц (m – штук) и нулей ((n-1) штук) подсчитывается по формуле перестановок с повторениями P(n-1,m). Таким образом, общее число C^m_n =

Пример: Сколько различных комбинаций можно составить из 5 букв типа а б в, отличающихся друг от друга только составом?

Решение: 5⁵₃ = P(3-1,5) =

20. Свойства сочетаний. Бином Ньютона. (Л).

Сочетаниями из n по m называют комбинации длины m(m<=n), отличающиеся друг от друга только составом элементов. Обозначаются сочетания C^m_n (читаются C из n по m)

Свойства сочетаний:

1. C^k_n = C^n-k_n Чтобы выбрать  k  элементов из множества в  n  элементов, можно указать те из них, которые останутся, не будут выбраны. Если мы выбираем  k  элементов, то остается     Поэтому число выборок по  k  элементов (из  n ) равно числу выборок по     элементов.

2. C^k_n = C^k-1_n-1 + C^k_n-1 Подсчитаем двумя способами общее возможное число выборок из множества, содержащего  n  элементов (число всех подмножеств  n -элементного множества). С одной стороны это число равно     – для каждого элемента есть две возможности: попасть или не попасть в выбираемое подмножество, причем для каждого элемента эти возможности выбираются независимо друг от друга. Это же число можно получить иначе – сначала зафиксировать число  k  элементов в подмножестве. Получим число     а затем сложим по всем  k,  чтобы найти общее число вариантов.

3. C⁰_n + C¹_n +… + Cⁿ_n = 2ⁿ Представим себе, что к  n  элементам данного множества мы добавили еще один, и из полученного множества хотим выбрать подмножество из    элемента. По определению это число равно     Все эти выборки мы разобьем на два сорта – те, которые содержат один добавленный элемент, и те, которые его не содержат. Первых будет     штук (один элемент уже взят, а из остальных надо взять еще  k ), а вторых –    (все     элементов берутся из исходного множества). Тем самым   Это равенство лежит в основе построения так называемого треугольника Паскаля, позволяющего быстро вычислять числа сочетаний     для небольших значений  n.

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

(x+a)n = C⁰_nxⁿ + C¹_nx^n-1a + C²_nx^n-2a² +…+Cⁿ_naⁿ - это из его лекций