Вычислить кол-во k-элементных подмножеств данного множества

Число |Bk(A)| всех k-элементных подмножеств n-элементного множества A зависит только от (n, k) и называется числом сочетаний. Обозначение: |Bk(A)|=Cnk (читается " из n по k").

Зафиксируем некоторый элемент a1∈ A. Рассматриваемое подмножество может либо содержать этот элемент, либо не содержать. Имеется Cn-1k-1 подмножеств, содержащих a1 и Cn-1k подмножеств, не содержащих a1. Поэтому

Cnk=Cn-1k-1+Cn-1k.

Теорема

Пусть |A|=n. Тогда

|Bk(A)|=Cnk=n(n-1)…(n-(k-1))k! =n! k! (n-k)!.

Доказательство   Показать

Пример

Пусть A — русский алфавит. Сколько имеется 3-элементных подмножеств множества A?

Требуется вычислить C333. Вычисляем:

C333=33⋅ 32⋅ 313! =327366=5456

Пример

Выведем формулу бинома Ньютона.

(1+x)n=(1+x)(1+x)…(1+x)12…n

Пронумеруем множители (1+x). Чтобы получить xk надо в k скобках взять слагаемое x, а в остальных (n-k) скобках — слагаемое 1. Каждый способ выбрать k скобок есть некоторое k-элементное подмножество множества номеров {1, 2, …, n}. Поэтому коэффициент при xk есть число всех k-элементных подмножеств множества {1, 2, …, n}, т.е. Cnk. Следовательно,

(1+x)n=Cn0+Cn1x+Cn2x2+…+Cnn-1xn-1+Cnnxn

— искомая формула.

Объяснить, что такое треугольник Паскаля (см. Википедию или в моих лекциях: Теория вероятностей - Случайные события - Основные понятия - Комбинаторика)

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

• Числа треугольника симметричны(равны) относительно вертикальной оси.
• В строке с номером n:
• первое и последнее числа равны 1.
• второе и предпоследнее числа равны n.
• третье число равно треугольному числу , что также равно сумме номеров предшествующих строк^[3].
• четвёртое число является тетраэдрическим^[3].
• m -е число равно биномиальному коэффициенту .
• Сумма чисел восходящей диагонали, начинающейся с первого элемента (n -1)-й строки, есть n -е число Фибоначчи: ^[3]

• Если вычесть из центрального числа в строке с чётным номером соседнее число из той же строки, то получится число Каталана.^[3]
• Сумма чисел n -й строки треугольника Паскаля равна ^[3].
• Простые делители чисел треугольника Паскаля образуют симметричные самоподобные структуры.
• Если в треугольнике Паскаля все нечётные числа окрасить в чёрный цвет, а чётные — в белый, то образуется треугольник Серпинского.
• Все числа в n -й строке, кроме единиц, делятся на число n, если и только если n является простым числом^[4] (следствие теоремы Люка).
• Если в строке с нечётным номером сложить все числа с порядковыми номерами вида 3 n, 3 n +1, 3 n +2, то первые две суммы будут равны, а третья на 1 меньше.
• Каждое число в треугольнике равно количеству способов добраться до него из вершины, перемещаясь либо вправо-вниз, либо влево-вниз.

Сочетанием из n элементов по k называется любой способ выбрать из n-элементного множества k элементов без учета порядка. Или, другими словами, выбрать из n-элементного множества k-элементное подмножество.

Например, перечислим все сочетания множества {A, B, C} по 2 элемента:

AB, AC, BC.

Обратим внимание, что AB и BA — различные размещения, но одно и то же сочетание. С целью дальнейшего обощения можно заметить, что каждому сочетанию из 3 по 2 будет соответствовать 2! размещений из 3 по 2. Поэтому число сочетаний из 3 по 2 окажется в 2! раз меньше числа размещений из 3 по 2. Аналогичное рассуждение мы проводим ниже при выводе общей формулы для числа сочетаний.

Докажем, что число сочетаний из n по k вычисляется по формуле:

Cnk=Ankk! =n(n-1)…(n-k+1)k! =n! k! (n-k)!.

Рассмотрим некоторое n-элементное множество и зафиксируем некоторое число k⩽ n. Подсчитаем сначала сколько имеется размещений из n по k, отличающихся только порядком следования элементов. Каждый определенный порядок следования k элементов есть перестановка из k элементов. Число всех таких перестановок равно k!. Теперь заметим, что всем таким размещениям соответствует единственное сочетание. Поэтому размещений из n по k будет в k! раз больше, чем сочетаний из n по k. Что и требовалось доказать.

Теорема   (Свойства числа сочетаний)

1. Cnk=Cnn-k

2. Cnk=Cn-1k-1+Cn-1k

3. Cn0+Cn1+…+Cnn-1+Cnn=2n

4. Треугольник Паскаля

Каждое число, расположенное внутри треугольника (не лежащее на его боковой стороне), можно найти как сумму двух чисел, расположенных над ним слева и справа. На боковых сторонах треугольника лежат числа Cn0=Cnn=1.

Найти все отображения одного множества в другое

1. Отображением f множества A в множество B называется правило, по которому каждому элементу a∈ A соответствует некоторый элемент b=f(a)∈ B.

Запись f: A→ B означает, что f является отображением множества A в множество B. При этом множество A называется областью определения отображения f.

Запись f: a↦ b означает, что f отображает элемент a в элемент b, т.е. что b=f(a). При этом b называется образом элемента a, а a — прообразом элемента b.

Множество всех a∈ A, для которых f(a)=b∈ B — фиксированный элемент, называется полным прообразом элемента b при отображении f и обозначается f-1(b)

f-1(b)={a∈ A|f(a)=b}.

Множество тех b∈ B, для которых существует прообраз в множестве A, называется областью значений отображения f и обозначается f(A)

f(A)={b∈ B|∃ a∈ A: b=f(a)}.

Пример

Пусть A={-2, -1, 0, 1, 2}, B={0, 1, 2, 3, 4, 5}, а отображение f действует по правилу f(a)=a2.

Тогда элемент 1∈ B является образом элементов -1, 1∈ A, а элементы -2, 2∈ A являются прообразами элемента 4∈ B.

Полные прообразы элементов множества B:

f-1(0)={0},   f-1(1)={-1, 1},   f-1(2)=∅,   f-1(4)={-2, 2}.

Множество f(A)={0, 1, 4}⊂ B является областью значений отображения f.

Если A={a1, a2, …, an}, B={b1, b2, …, bm}, то любое отображение f: A→ B задается упорядоченным набором (bi1, bi2, …, bin), где bi1=f(a1), bi2=f(a2) и т.д. При этом порядок записи элементов множества A предполагается фиксированным.

Пример

Пусть A={" Иванов", " Петров", " Сидоров" } — множество студентов, B={2, 3, 4, 5} — множество оценок. Пусть f: A→ B ставит в соответствие каждому студенту его оценку по математике.

Тогда отображение f может быть задано, например, строкой (3, 4, 3). Это означает, что Иванов и Сидоров имеют по математике оценки 3, а Петров — оценку 4.

Множество всех отображений множества A в множество B обозначается F(A, B) или BA.

Пример

Пусть A={1, 2, 3}, B={0, 1}. Перечислим все отображения A в B.

Каждое такое отображение определяется упорядоченным набором (b1, b2, b3), где каждый элемент равен 0 или 1. Мы будем теперь записывать их в столбцы.

Теорема   (Число всех отображений)

|F(A, B)|=|B||A|

Доказательство  

Вычислить мощность множества всех отображений одного множества в другое
Перечислить все сюръекции одного множества в другое
Вычислить мощность множества всех инъекций одного множества в другое
Перечислить все инъекции одного множества в другое
Перечислить все биекции одного множества в другое
Перечислить все перестановки данного множества
По словесному описанию логической функции построить ее выражение
По словесному описанию логической функции построить ее таблицу истинности
Для заданного логического тождества найти двойственное
По таблице истинности построить СДНФ функции
По таблице истинности построить СКНФ функции
По таблице истинности построить таблицу Карно
По таблице Карно получить минимальную дизъюнктную форму функции
По таблице Карно получить минимальную конъюнктную форму функции