Как решать уравнения с множествами

Операции над множествами

Пересечение множеств

Рассмотрим два множества: множество друзей Джона и множество друзей Майкла.

Друзья Джона = <

Том,
Фред,
Макс,
Джорж >

Друзья Майкла = <

Лео,
Том,
Фред,
Эван >

Видим, что Том и Фред одновременно являются друзьями Джона и Майкла.

Говоря на языке множеств, элементы Том и Фред принадлежат как множеству друзей Джона, так и множеству друзей Майкла.

Зададим новое множество с названием «Общие друзья Джона и Майкла» и в качестве элементов добавим в него Тома и Фреда :

Общие друзья Джона и Майкла

В данном случае множество «Общие друзья Джона и Майкла» является пересечением множеств друзей Джона и Майкла.

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

В нашем случае элементы Том и Фред принадлежат каждому из исходных множеств, а именно: множеству друзей Джона и множеству друзей Майкла.

Обозначим множество друзей Джона через букву A , множество друзей Майкла — через букву B , а множество общих друзей Джона и Майкла обозначим через букву C :

Тогда пересечением множеств A и B будет множество C и записываться следующим образом:

Символ ∩ означает пересечение.

Говоря о множестве, обычно подразумевают элементы, принадлежащие этому множеству. Символ пересечения ∩ читается, как союз И. Тогда выражение A ∩ B = C можно прочитать следующим образом:

«Элементы, принадлежащие множеству A И множеству B, есть элементы, принадлежащие множеству C».

«Друзья, одновременно принадлежащие Джону И Майклу, есть общие друзья Джона и Майкла».

Теперь представим, что у Джона и Майкла нет общих друзей. Для удобства, как и прежде обозначим множество друзей Джона через букву A , а множество друзей Майкла через букву B

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

Пример 2. Рассмотрим два множества: множество A , состоящее из чисел 1, 2, 3, 5, 7 и множество B, состоящее из чисел 1, 2, 3, 4, 6, 12, 18

Зададим новое множество C и добавим в него элементы, которые одновременно принадлежат множеству A и множеству B

Множество С является пересечением множеств A и B , поскольку элементы множества C одновременно принадлежат множеству A и множеству B

Пример 3. Рассмотрим два множества: множество A, состоящее из чисел 1, 5, 7, 9 и множество B , состоящее из чисел 1, 4, 5, 7

Множество С является пересечением множеств A и B , поскольку элементы множества C одновременно принадлежат множеству A и множеству B.

Пример 4. Найти пересечение следующих множеств:

Пересечением множеств A , B и C будет множество, состоящее из элементов, принадлежащих каждому из множеств A , B и C . Этими элементами являются числа 3 и 9.

Зададим новое множество D и добавим в него элементы 3 и 9. Затем с помощью символа пересечения ∩ запишем, что пересечением множеств A, B и C является множество D

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

К примеру, пусть первое множество состоит из элементов 1, 3, 5, а второе из элементов 2, 3, 5 . Пересечением в данном случае является множество, состоящее из элементов 3 и 5 . Чтобы записать пересечение, можно воспользоваться прямым перечислением:

Числовые промежутки, которые мы рассмотрели в предыдущих уроках, тоже являются множествами. Элементами таких множеств являются числа, входящие в числовой промежуток.

Например, отрезок [2; 6] можно понимать, как множество всех чисел от 2 до 6. Для наглядности можно перечислить все целые числа, принадлежащие данному отрезку:

Следует иметь ввиду, что мы перечислили только целые числа. Отрезку [2; 6] также принадлежат и другие числа, не являющиеся целыми, например, десятичные дроби. Десятичные дроби располагаются между целыми числами, но их количество настолько велико, что перечислить их не представляется возможным.

Еще пример. Интервал (2; 6) можно понимать, как множество всех чисел от 2 до 6, кроме чисел 2 и 6. Ранее мы говорили, что интервал это такой числовой промежуток, границы которого не принадлежат ему. Для наглядности можно перечислить все целые числа, принадлежащие интервалу (2; 6) :

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

Пример 5. Даны два числовых промежутка: [2; 6] и [4; 8] . Найти их пересечение.

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

Для наглядности перечислим все целые числа, принадлежащие промежуткам [2; 6] и [4; 8] :

Видно, что числа 4, 5, 6 принадлежат как первому промежутку [2; 6] , так и второму [4; 8] .

Тогда пересечением числовых промежутков [2; 6] и [4; 8] будет числовой промежуток [4; 6]

Изобразим промежутки [2; 6] и [4; 8] на координатной прямой. На верхней области отметим числовой промежуток [2; 6] , на нижней — промежуток [4; 8]

Видно, что числа, принадлежащие промежутку [4; 6] , принадлежат как промежутку [2; 6] , так и промежутку [4; 8] . Можно также заметить, что штрихи, входящие в промежутки [2; 6] и [4; 8] пересекаются в промежутке [4; 6] . В такой ситуации, когда перед глазами есть координатная прямая, понятие пересечения множеств можно понимать в прямом смысле, что очень удобно.

Пример 6. Найти пересечение числовых промежутков [−2; 3] и [4; 7]

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

Для наглядности перечислим все целые числа, принадлежащие промежуткам [−2; 3] и [4; 7] :

−2, −1, 0, 1, 2, 3 ∈ [−2; 3]

Видно, что числовые промежутки [−2; 3] и [4; 7] не имеют общих чисел. Поэтому их пересечением будет пустое множество:

Если изобразить числовые промежутки [−2; 3] и [4; 7] на координатной прямой, то можно увидеть, что они нигде не пересекаются:

Пример 7. Дано множество из одного элемента < 2 >. Найти его пересечение с промежутком (−3; 4)

Множество, состоящее из одного элемента < 2 >, на координатной прямой изображается в виде закрашенного кружка, а числовой промежуток (−3; 4) это интервал, границы которого не принадлежат ему. Значит границы −3 и 4 будут изображаться в виде пустых кружков:

Пересечением множества < 2 >и числового промежутка (−3; 4) будет множество, состоящее из одного элемента < 2 >, поскольку элемент 2 принадлежит как множеству < 2 >, так и числовому промежутку (−3; 4)

На самом деле мы уже занимались пересечением числовых промежутков, когда решали системы линейных неравенств. Вспомните, как мы решали их. Сначала находили множество решений первого неравенства, затем множество решений второго. Затем находили множество решений, которые удовлетворяют обоим неравенствам.

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

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

В данном примере решением первого неравенства x ≥ 3 является множество всех чисел, которые больше 3 (включая само число 3). Иначе говоря, решением неравенства является числовой промежуток [3; +∞)

Решением второго неравенства x ≤ 6 является множество всех чисел, которые меньше 6 (включая само число 6). Иначе говоря, решением неравенства является числовой промежуток (−∞; 6]

А общим решением системы будет пересечение множеств решений первого и второго неравенства, то есть пересечение числовых промежутков [3; +∞) и (−∞; 6]

Если мы изобразим множество решений системы на координатной прямой, то увидим, что эти решения принадлежат промежутку [3; 6] , который в свою очередь является пересечением промежутков [3; +∞) и (−∞; 6]

Поэтому в качестве ответа мы указывали, что значения переменной x принадлежат числовому промежутку [3; 6], то есть пересечению множеств решений первого и второго неравенства

Пример 2. Решить неравенство

Все неравенства, входящие в систему уже решены. Нужно только указать те решения, которые являются общими для всех неравенств.

Решением первого неравенства является числовой промежуток (−∞; −1) .

Решением второго неравенства является числовой промежуток (−∞; −5) .

Решением третьего неравенства является числовой промежуток (−∞; 4) .

Решением системы будет пересечение числовых промежутков (−∞; −1), (−∞; −5) и (−∞; 4) . В данном случае этим пересечением является промежуток (−∞; −5) .

На рисунке представлены числовые промежутки и неравенства, которыми эти числовые промежутки заданы. Видно, что числа, принадлежащие промежутку (−∞; −5) , одновременно принадлежат всем исходным промежуткам.

Запишем ответ к системе с помощью числового промежутка:

Пример 3. Решить неравенство

Решением первого неравенства y > 7 является числовой промежуток (7; +∞) .

Решением второго неравенства y является числовой промежуток (−∞; 4) .

Решением системы будет пересечение числовых промежутков (7; +∞) и (−∞; 4) .

В данном случае пересечением числовых промежутков (7; +∞) и (−∞; 4) является пустое множество, поскольку эти числовые промежутки не имеют общих элементов:

Если изобразить числовые промежутки (7; +∞) и (−∞; 4) на координатной прямой, то можно увидеть, что они нигде не пересекаются:

Объединение множеств

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

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

Рассмотрим множество A с элементами 1, 2, 3 и множество B с элементами 4, 5, 6.

Зададим новое множество C и добавим в него все элементы множества A и все элементы множества B

В данном случае объединением множеств A и B является множество C и обозначается следующим образом:

Символ ∪ означает объединение и заменяет собой союз ИЛИ. Тогда выражение A ∪ B = C можно прочитать так:

Элементы, принадлежащие множеству A ИЛИ множеству B, есть элементы, принадлежащие множеству C.

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

Вернёмся к созданному нами множеству C , куда входят все элементы множеств A и B . Возьмём для примера из этого множества элемент 5. Что можно про него сказать?

Если 5 является элементом множества C , а множество С является объединением множеств A и B , то можно с уверенностью заявить, что элемент 5 принадлежит хотя бы одному из множеств A и B . Так оно и есть:

Возьмем ещё один элемент из множества С , например, элемент 2. Что можно про него сказать?

Если 2 является элементом множества C , а множество С является объединением множеств A и B , то можно с уверенностью заявить, что элемент 2 принадлежит хотя бы одному из множеств A и B . Так оно и есть:

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

Например, рассмотрим множество A с элементами 1, 2, 3, 4 и множество B с элементами 2, 4, 5, 6.

Видим, что элементы 2 и 4 одновременно принадлежат и множеству A , и множеству B . Если мы захотим объединить множества A и B , то новое множество C будет содержать элементы 2 и 4 только один раз. Выглядеть это будет так:

Чтобы при объединении не допустить ошибок, обычно поступают так: сначала в новое множество добавляют все элементы первого множества, затем добавляют элементы второго множества, которые не принадлежат первому множеству. Попробуем сделать такое объединение с множествами A и B .

Итак, у нас имеются следующие исходные множества:

Зададим новое множество С и добавим в него все элементы множества A

Теперь добавим элементы из множества B , которые не принадлежат множеству A . Множеству A не принадлежат элементы 5 и 6 . Их и добавим во множество C

Пример 2. Друзьями Джона являются Том, Фред, Макс и Джордж. А друзьями Майкла являются Лео, Том, Фред и Эван. Найти объединение множеств друзей Джона и Майкла.

Для начала зададим два множества: множество друзей Джона и множество друзей Майкла.

Друзья Джона = <

Том,
Фред,
Макс,
Джорж >

Друзья Майкла = <

Лео,
Том,
Фред,
Эван >

Зададим новое множество с названием «Все друзья Джона и Майкла» и добавим в него всех друзей Джона и Майкла.

Заметим, что Том и Фред одновременно являются друзьями Джона и Майкла, поэтому мы добавим их в новое множество только один раз, поскольку сразу двух Томов и двух Фредов не бывает.

Все друзья Джона и Майкла

В данном случае множество всех друзей Джона и Майкла является объединением множеств друзей Джона и Майкла.

Друзья Джона ∪ Друзья Майкла = Все друзья Джона и Майкла

Пример 3. Даны два числовых промежутка: [−7; 0] и [−3; 5] . Найти их объединение.

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

Для наглядности перечислим все целые числа, принадлежащие этим промежуткам:

−7, −6, −5, −4, −3,−2, −1 , 0 ∈ [−7; 0]

−3,−2, −1 , 0, 1, 2, 3, 4, 5 ∈ [−3; 5]

Объединением числовых промежутков [−7; 0] и [−3; 5] будет числовой промежуток [−7; 5] , который содержит все числа промежутка [−7; 0] и [−3; 5] без повторов некоторых из чисел

−7, −6, −5, −4, −3,−2, −1, 0, 1, 2, 3, 4, 5 ∈ [−7; 5]

Обратите внимание, что числа −3,−2, −1 принадлежали и первому промежутку и второму. Но поскольку в объединение допускается включать такие элементы только один раз, мы включили их единоразово.

Значит объединением числовых промежутков [−7; 0] и [−3; 5] будет числовой промежуток [−7; 5]

Изобразим на координатной прямой промежутки [−7; 0] и [−3; 5] . На верхней области отметим числовой промежуток [−7; 0] , на нижней — промежуток [−3; 5]

Ранее мы выяснили, что промежуток [−7; 5] является объединением промежутков [−7; 0] и [−3; 5] . Здесь полезно вспомнить про определение объединения множеств, которое было приведено в самом начале. Объединение трактуется, как множество, состоящее из всех элементов, принадлежащих хотя бы одному из исходных множеств.

Действительно, если взять любое число из промежутка [−7; 5] , то окажется, что оно принадлежит хотя бы одному из промежутков: либо промежутку [−7; 0] либо промежутку [−3; 5] .

Возьмём из промежутка [−7; 5] любое число, например число 2 . Поскольку промежуток [−7; 5] является объединением промежутков [−7; 0] и [−3; 5] , то число 2 будет принадлежать хотя бы одному из этих промежутков. В данном случае число 2 принадлежит промежутку [−3; 5]

Возьмём ещё какое-нибудь число. Например, число −4 . Это число будет принадлежать хотя бы одному из промежутков: [−7; 0] или [−3; 5] . В данном случае оно принадлежит промежутку [−7; 0]

Возьмём ещё какое-нибудь число. Например, число −2 . Оно принадлежит как промежутку [−7; 0] , так и промежутку [−3; 5] . Но на координатной прямой оно указывается только один раз, поскольку в одной точке сразу два числа −2 не бывает.

Не каждое объединение числовых промежутков является числовым промежутком. Например, попробуем найти объединение числовых промежутков [−2 ; −1] и [4 ; 7].

Идея остаётся та же самая — объединением числовых промежутков [−2 ;−1] и [4 ; 7] будет множество, состоящее из элементов, принадлежащих хотя бы одному из промежутков: [−2; −1] или [4; 7] . Но это множество не будет являться числовым промежутком. Для наглядности перечислим все целые числа, принадлежащие этому объединению:

Получили множество < −2, −1, 4, 5, 6, 7 >. Это множество не является числовым промежутком по причине того, что числа, располагающиеся между −1 и 4 , не вошли в полученное множество

Числовой промежуток должен содержать все числа от левой границы до правой. Если одно из чисел отсутствует, то числовой промежуток теряет смысл. Допустим, имеется линейка длиной 15 см

Эта линейка является числовым промежутком [0; 15], поскольку содержит все числа в промежутке от 0 до 15 включительно. Теперь представим, что на линейке после числа 9 сразу следует число 12.

Эта линейка не является линейкой в 15 см, и её нежелательно использовать для измерения. Также, её нельзя назвать числовым промежутком [0; 15] , поскольку она не содержит все числа, которые должна была содержать.

Решение неравенств, содержащих знак ≠

Некоторые неравенства содержат знак ≠ (не равно). Например, 2x ≠ 8 . Чтобы решить такое неравенство, нужно найти множество значений переменной x , при которых левая часть не равна правой части.

Решим неравенство 2x ≠ 8 . Разделим обе части данного неравенства на 2, тогда получим:

Получили равносильное неравенство x ≠ 4 . Решением этого неравенства является множество всех чисел, не равных 4. То есть если мы подставим в неравенство x ≠ 4 любое число, которое не равно 4, то получим верное неравенство.

Подставим, например, число 5

5 ≠ 4 — верное неравенство, поскольку 5 не равно 4

7 ≠ 4 — верное неравенство, поскольку 7 не равно 4

И поскольку неравенство x ≠ 4 равносильно исходному неравенству 2x ≠ 8 , то решения неравенства x ≠ 4 будут подходить и к неравенству 2x ≠ 8 . Подставим те же тестовые значения 5 и 7 в неравенство 2x ≠ 8 .

Изобразим множество решений неравенства x ≠ 4 на координатной прямой. Для этого выколем точку 4 на координатной прямой, а всю оставшуюся область с обеих сторон выделим штрихами:

Теперь запишем ответ в виде числового промежутка. Для этого воспользуемся объединением множеств. Любое число, являющееся решением неравенства 2x ≠ 8 будет принадлежать либо промежутку (−∞; 4) либо промежутку (4; +∞). Так и записываем, что значения переменной x принадлежат (−∞; 4) или (4; +∞) . Напомним, что для слова «или» используется символ ∪

В этом выражении говорится, что значения, принимаемые переменной x , принадлежат промежутку (−∞; 4) или промежутку (4; +∞).

Неравенства, содержащие знак ≠ , также можно решать, как обычные уравнения. Для этого знак ≠ заменяют на знак = . Тогда получится обычное уравнение. В конце решения найденное значение переменной x нужно исключить из множества решений.

Решим предыдущее неравенство 2x ≠ 8 , как обычное уравнение. Заменим знак ≠ на знак равенства = , получим уравнение 2x = 8 . Разделим обе части данного уравнения на 2 , получим x = 4 .

Видим, что при x , равном 4, уравнение обращается в верное числовое равенство. При других значениях равенства соблюдаться не будет. Эти другие значения нас и интересуют. А для этого достаточно исключить найденную четвёрку из множества решений.

Пример 2. Решить неравенство 3x − 5 ≠ 1 − 2x

Перенесем −2x из правой части в левую часть, изменив знак, а −5 из левой части перенесём в правую часть, опять же изменив знак:

Приведем подобные слагаемые в обеих частях:

Разделим обе части получившегося неравенства на 5

Решением неравенства x ≠ 1,2 является множество всех чисел, не равных 1,2 .

Изобразим множество решений неравенства x ≠ 1,2 на координатной прямой и запишем ответ в виде числового промежутка:

В этом выражении говорится, что значения, принимаемые переменной x принадлежат промежутку (−∞; 1,2) или промежутку (1,2; +∞)

Решение совокупностей неравенств

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

Совокупность неравенств очень похожа на систему неравенств. Различие в том, что в системе неравенств нужно найти множество решений, удовлетворяющих каждому неравенству, образующему эту систему.

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

Совокупность неравенств обозначается квадратной скобкой. Например, следующая запись из двух неравенств является совокупностью:

Решим данную совокупность. Сначала нужно решить каждое неравенство по отдельности.

Решением первого неравенства x ≥ 3 является числовой промежуток [3; +∞) . Решением второго неравенства x ≤ 6 является числовой промежуток (−∞; 6] .

Множество значений x , при которых верно хотя бы одно из неравенств, будет принадлежать промежутку [3; +∞) или промежутку (−∞; 6] . Так и записываем:

В этом выражении говорится, что переменная x , входящая в
совокупность принимает все значения, принадлежащие промежутку [3; +∞) или промежутку (−∞; 6] . А это то, что нам нужно. Ведь решить совокупность означает найти множество решений, удовлетворяющих хотя бы одному неравенству, образующему эту совокупность. А любое число из промежутка [3; +∞) или промежутка (−∞; 6] будет удовлетворять хотя бы одному неравенству.

Например, число 9 из промежутка [3; +∞) удовлетворяет первому неравенству x ≥ 3. А число −7 из промежутка (−∞; 6] удовлетворяет второму неравенству x ≤ 6.

Посмотрите внимательно на выражение x ∈ [3; +∞) ∪ (−∞; 6], а именно на его правую часть. Ведь выражение [3; +∞) ∪ (−∞; 6] представляет собой объединение числовых промежутков [3; +∞) и (−∞; 6] . Точнее, объединение множеств решений первого и второго неравенства.

Стало быть, решением совокупности неравенств является объединение множеств решений первого и второго неравенства.

Иначе говоря, решением совокупности будет объединение числовых промежутков [3; +∞) и (−∞; 6]

Объединением числовых промежутков [3; +∞) и (−∞; 6] является промежуток (−∞; +∞) . Точнее, объединением числовых промежутков [3; +∞) и (−∞; 6] является вся координатная прямая. А вся координатная прямая это все числа, которые только могут быть

Ответ можно оставить таким, каким мы его записали ранее:

либо заменить на более короткий:

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

Возьмем для примера число 8. Оно удовлетворяет первому неравенству x ≥ 3.

Возьмем еще какое-нибудь число, например, число 1. Оно удовлетворяет второму неравенству x ≤ 6

Возьмем еще какое-нибудь число, например, число 5 . Оно удовлетворяет и первому неравенству x ≥ 3 и второму x ≤ 6

Пример 2. Решить совокупность неравенств

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

Для начала найдём множество решений первого неравенства x . Этим множеством является числовой промежуток (−∞; −0,25) .

Множеством решений второго неравенства x ≥ −7 является числовой промежуток [−7; +∞).

Решением совокупности неравенств будет объединение множеств решений первого и второго неравенства.

Иначе говоря, решением совокупности будет объединение числовых промежутков (−∞; −0,25) и [−7; +∞)

Объединением числовых промежутков (−∞; −0,25) и [−7; +∞) является является вся координатная прямая. А вся координатная прямая это все числа, которые только могут быть

Ответ можно оставить таким, каким мы его записали ранее:

либо заменить на более короткий:

Пример 3. Решить совокупность неравенств

Решим каждое неравенство по отдельности:

Множеством решений первого неравенства x является числовой промежуток (−∞; −3) .

Множеством решений второго неравенства x ≤ 0 является числовой промежуток (−∞; 0] .

Решением совокупности неравенств будет объединение множеств решений первого и второго неравенства.

Иначе говоря, решением совокупности будет объединение числовых промежутков (−∞; −3) и (−∞; 0]

Объединением числовых промежутков (−∞; −3) и (−∞; 0] является числовой промежуток (−∞; 0]

Ответ можно оставить таким, каким мы его записали ранее:

Решение некоторых задач по теории множеств

Разделы: Математика

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

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

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

Множества обозначим А, В, С…, а элементы множеств а, b, с…, используя латинский алфавит.

Можно сделать такую запись определения множества:

, где

“” – принадлежит;
“=>“ – следовательно;
“ø” – пустое множество, т.е. не содержащее ни одного элемента.

Два множества будем называть равными, если они состоят из одних и тех же элементов

Если любой элемент из множества А принадлежит и множеству В, то говорят, что множество А включено в множество В, или множество А является подмножеством множества В, или А является частью В, т.е. если , то , где “С” знак подмножества или включения.

Графически это выглядит так (рис.1):

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

Рассмотрим операции над множествами и их графическую иллюстрацию (рис.2).

Объединением множеств А и В называется множество С, образованное всеми элементами, которые принадлежат хотя бы одному из множеств А или В. Слова “или ” ключевое в понимании элементов входящих в объединение множеств.

Это определение можно записать с помощью обозначений:

А υ В, где

где “ υ ” – знак объединения,

“ / ” – заменяет слова ”таких что“

Пресечение двух множеств А и В называется множество С, образованное всеми элементами, которые принадлежат и множеству А, и множеству В. Здесь уже ключевое слово “и”. Запишем коротко:

А ∩ В = С, где

“∩“ – знак пересечения. (рис.3)

Обозначим буквой Е основное или универсальное множество, где A С Е (“”- любо число), т.е. А Е = Е; АЕ =А

Множество всех элементов универсального множества Е, не принадлежащих множеству А называется дополнением множества А до Е и обозначается Ā Е или Ā (рис.4)

Примерами для понимания этих понятий являются свойства:

А Ā=Е Ø = Е Е Ā=Ā

Свойства дополнения имеют свойства двойственности:

АВ = А∩В

АВ = АUВ

Введем еще одно понятие – это мощность множества.

Для конечного множества А через m (A) обозначим число элементов в множестве А.

Из определение следуют свойства:

Для любых конечных множеств справедливы так же утверждения:

m (AB) =m (A) + m (В) – m (А∩В)

m (A∩B) = m (A) + m (В) – m (АВ)

m (ABC) = m (A) + m (В) + m (С)– m (А∩В) — m (А∩С) – m (В∩С) – m (А∩В∩С).

А теперь рассмотрим ряд задач, которые удобно решать, используя графическую иллюстрацию.

Задача №1

В олимпиаде по математике для абитуриентов приняло участие 40 учащихся, им было предложено решить одну задачу по алгебре, одну по геометрии и одну по тригонометрии. По алгебре решили задачу 20 человек, по геометрии – 18 человек, по тригонометрии – 18 человек.

По алгебре и геометрии решили 7 человек, по алгебре и тригонометрии – 9 человек. Ни одной задачи не решили 3 человека.

Сколько учащихся решили все задачи?
Сколько учащихся решили только две задачи?
Сколько учащихся решили только одну задачу?

Задача № 2

Первую или вторую контрольные работы по математике успешно написали 33 студента, первую или третью – 31 студент, вторую или третью – 32 студента. Не менее двух контрольных работ выполнили 20 студентов.

Сколько студентов успешно решили только одну контрольную работу?

Задача № 3

В классе 35 учеников. Каждый из них пользуется хотя бы одним из видов городского транспорта: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 6 учеников, метро и автобусом – 15 учеников, метро и троллейбусом – 13 учеников, троллейбусом и автобусом – 9 учеников.

Сколько учеников пользуются только одним видом транспорта?

Решение задачи № 1

Запишем коротко условие и покажем решение:

m (Е) = 40
m (А) = 20
m (В) = 18
m (С) = 18
m (А∩В) = 7
m (А∩С) = 8
m (В∩С) = 9

m (АВС) = 3 => m (АВС) = 40 – 3 = 37

Обозначим разбиение универсального множества Е множествами А, В, С (рис.5).

К 1 – множество учеников, решивших только одну задачу по алгебре;

К 2 – множество учеников, решивших только две задачи по алгебре и геометрии;

К 3 – множество учеников, решивших только задачу по геометрии;

К 4 – множество учеников, решивших только две задачи по алгебре и тригонометрии;

К 5 – множество всех учеников, решивших все три задачи;

К 6 – множество всех учеников, решивших только две задачи, по геометрии и тригонометрии;

К 7 – множество всех учеников, решивших только задачу по тригонометрии;

К 8 – множество всех учеников, не решивших ни одной задачи.

Используя свойство мощности множеств и рисунок можно выполнить вычисления:

m (К 5 ) = m (А∩В∩С)= m (АВС) — m (А) — m (В) — m (С) + m (А∩В) + m (А∩С) + m (В∩С)
m (К 5 ) = 37-20-18-18+7+8+9=5
m (К 2 ) = m (А∩В) — m (К 5 ) = 7-5=2
m (К 4 ) = m (А∩С) — m (К 5 ) = 8-5=3
m (К 6 ) = m (В∩С) — m (К 5 ) = 9-5=4
m (К 1 ) = m (А) — m (К 2 ) — m (К 4 ) — m (К 5 ) = 20-2-3-5=10
m (К 3 ) = m (В) — m (К 2 ) — m (К 6 ) — m (К 5 ) = 18-2-4-5=7
m (К 7 ) = m (С) — m (К4) — m (К 6 ) — m (К 5 ) = 18-3-4-5 =6
m (К 2 ) + m (К 4 ) + m (К6) = 2+3+4=9 – число учеников решивших только две задачи;
m (К 1 ) + m (К 3 ) + m (К 7 ) = 10+7+6=23 – число учеников решивших только одну задачу.

Ответ:

5 учеников решили три задачи;

9 учеников решили только по две задачи;

23 ученика решили только по одной задаче.

С помощью этого метода можно записать решения второй и третьей задачи так:

Решение задачи № 2

m (АВ) = 33
m (АС) = 31
m (ВС) = 32
m (К 2 ) + m (К 4 ) + m (К 6 ) + m (К 5 ) = 20

Найти m (К 1 ) + m (К 3 ) + m (К 7 )

m (АUВ) = m (К 1 ) + m (К 2 ) + m (К 3 ) + m (К 4 ) + m (К 5 ) + m (К 6 ) = m (К 1 ) + m (К 3 ) + 20 = 33 =>
m (К 1 ) + m (К 3 ) = 33 – 20 = 13
m (АUС) = m (К 1 ) + m (К 4 ) + m (К 2 ) + m (К 5 ) + m (К 6 ) + m (К 7 ) = m (К 1 ) + m (К 7 ) + 20 = 31 =>
m (К 1 ) + m (К 7 ) = 31 – 20 = 11
m (ВUС) = m (К 3 ) + m (К 2 ) + m (К 5 ) + m (К 6 ) + m (К 7 ) + m (К 4 ) = m (К 3 ) + m (К 7 ) + 20 = 32 =>
m (К 3 ) + m (К 7 ) = 32 – 20 = 12
2m (К 1 ) + m (К 3 ) + m (К 7 ) = 13+11=24
2m (К 1 ) + 12 = 24
m (К 3 )= 13-6=7
m (К 7 )=12-7=5
m (К 1 ) + m (К 3 ) + m (К 7 ) = 6+7+5=18

Ответ:

Только одну контрольную работу решили 18 учеников.

Решение задачи № 3

m (Е) = 35
m (А∩В∩С)= m (К 5 ) = 6
m (А∩В)= 15
m (А∩С)= 13
m (В∩С)= 9

Найти m (К1) + m (К3) + m (К 7 )

m (К 2 ) = m (А∩В) — m (К 5 ) = 15-6=9
m (К 4 ) = m (А∩С) — m (К 5 ) = 13-6=7
m (К 6 ) = m (В∩С) — m (К 5 ) = 9-6=3
m (К 1 ) + m (К 3 ) + m (К 7 ) = m (Е) — m (К 4 ) — m (К 2 ) — m (К 6 ) — m (К 5 ) = 35-7-9-3-6=10

Ответ:

Только одним видом транспорта пользуется 10 учеников.

Литература: А.Х. Шахмейстер «Множества. Функции. Последовательности»

Решение уравнений в алгебре множеств.

При решении уравнений в алгебре множеств исходят из того, что: 1) два множества равны тогда и только тогда, когда их симметрическая разность пуста; 2) определяются условия, при которых уравнения имеют решение [23].

Например, XUC=D. Преобразуем уравнение к виду (XUC)ÅD=Æ. Любое уравнение, в правой части которого указано пустое множество может быть преобразовано в уравнение с декомпозицией по X:

(F₁IX)U(F₂I )=Æ,

где F₁, F₂ – формулы, не содержащие X.

Очевидно, что объединение пусто тогда и только тогда, когда объединяемые множества пусты:

(F₁IX)=Æ и (F₂I )=Æ.

Два полученных уравнения и исходное уравнение имеют решение тогда и только тогда, когда:

Поэтому необходимо определить F₁, F₂, что и является результатом решения уравнения.

Итак, (XUC)ÅD=Æ. Декомпозицию по X выполним, с помощью формулы симметрической разности двух множеств, использующей только операции объединения, пересечения и дополнения:

где – разность , – разность .

Выполним алгебраические операции:

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

Далее раскрываем скобки и применяем законы алгебры множеств:

Здесь налицо поглощение , поэтому:

Выносим за скобку:

Обращаем внимание, что , поэтому:

Таким образом: , т.е. – это и есть ответ.

Само собой, в этом случае может быть множество решений для конкретных C, D.

Пусть C=<2,3,6,9>, D=<1,2,3,5,6,7,8,9>. Тогда (CÅD)=<1,5,7,8>ÍD. X может быть, например, таким: X=<1,2,5,7,8,9>, т.е. соотношение (CÅD)ÍXÍD – выполняется.

Пусть C=<2,3,4,6,9>, при том же D=<1,2,3,5,6,7,8,9>. Тогда (CÅD)= <1,4,5,7,8>не включается в D=<1,2,3,5,6,7,8,9>. В этом случае решения нет!

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

Комбинаторные вычисления

При решении теоретико-множественных задач большое значение имеет определение мощности конечных множеств.

Очевидно, что |AUB|=|A|+|B|–|AIB|, т.е., когда А и В в «общем положении», т.е. пересекаются.

Кроме того, |A\B|=|A|–|B|, когда А включается в В, |A\B|=|A|–|AIB|, когда А и В в «общем положении», т.е. пересекаются.

Нетрудно заметить, что |AÅB|=|A|+|B|–2|AIB|.

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

Пусть в базе данных имеется n записей об объектах недвижимости (например, квартирах) в виде запроса (что требуется) и предложения (что имеется) Требуется найти такие пары записей, в которых предложение первой записи совпадает с запросом второй и, наоборот, предложение второй записи совпадает с запросом первой («подбор вариантов обмена»).

Допустим, на проверку варианта обмена тратится одна миллисекунда. Можно показать, что при сравнении каждой записи с каждой требуется n(n-1)/2 сравнений.

(6,7),(6,8),(7,8) – всего 28 вариантов: 8´7/2=28=7+6+5+4+3+2+1. Здесь отношение сравнения симметрично и сам с собой вариант не сравнивается.

Если n=100, то при указанном быстродействии, на сравнения уйдет 4,95 секунды. Но, если n=100000 (в задачах реальной размерности), то необходимо 1999950 секунд, т.е. без малого – 1389 часов! Столько ждать клиент вряд ли будет. Это и есть «проклятие размерности». И это только сравнение прямых вариантов, а существуют варианты, в которых число участников сделки больше двух.

Поэтому комбинаторные вычисления требуют предварительного анализа и ориентировочной количественной оценки исходных данных. Иначе, можно подумать, что компьютер просто «завис» и не выдаёт ответа. Здесь речь идет о сложности вычислений в смысле времени решения. В ряде задач комбинаторной сложности необходимо время, сравнимое с геологическими эпохами. Но есть еще и пространственная сложность – в смысле объема памяти. Ведь промежуточные результаты часто надо где-то хранить. В ряде задач требуется объем памяти, превышающий количество атомов во Вселенной.

Основным инструментом такого анализа сложности вычислений и является комбинаторика.

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

Основная задача комбинаторики, как раздела дискретной математики, – пересчет и перечисление элементов в конечных множествах [24].

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

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

При этом под решением задачи оптимизации «в сильном смысле» понимается нахождение всех элементов минимизирующих (максимизирующих) целевую функцию, а под решением задачи оптимизации «в слабом смысле» – нахождение единственного произвольного элемента [24].

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

Пусть Х – конечное множество, состоящее из n элементов х. Тогда говорят, что элемент х из Х может быть выбран n способами и пишут |Х|=n. Эта запись совпадает с записью мощности множества Х.

Пусть Х₁. Х_k – попарно непересекающиеся множества, т.е. Х_iIХ_j=Æ, i¹j.

Очевидно, что в этом случае

Таково комбинаторное правило суммы. Для k=2 оно формулируется следующим образом. Если объект х может быть выбран n способами из множества Х, а объект y из непересекающегося с ним множества Y, – другими m способами, то выбор «х или y» может быть осуществлен n+m способами.

Правило произведения для k=2 формулируется следующим образом. Если объект х может быть выбран n способами и после каждого из таких выборов объект y в свою очередь может быть выбран m способами, то выбор упорядоченной пары – вектора (х,y) может быть осуществлен n×m способами.

Тогда упорядоченные пары (x,y) описываются декартовым произведением

Выбор упорядоченной последовательности из k объектов вектора (х₁,х₂. х_k) может быть осуществлен n₁·n₂·. ·n_k способами, где n_i – число способов выбора i-го объекта х_i, i меняется от 1 до k (записывается: ).

В частности, если все n_i равны, что может быть, например, в случае, когда элементы принадлежат одному и тому же множеству, т.е. рассматривается декартово произведение Х k , то число способов равно n k .

Набор элементов х_i₁. x_ik из множества Х=1. x_n> (вектор) называется выборкой (комбинацией) объема k из n элементов или, иначе, (n,k) выборкой.

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

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

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

Размещения

Упорядоченная (n,k) выборка, в которой элементы могут повторяться, называется (n,k) размещением с повторениями.

Иными словами размещениями с повторениями из n элементов по k называют векторы длины k, составленные из n элементов множества Х.

Число размещений с повторениями из n элементов по k определяется оценкой соответствующего декартова произведения Х k n-элементного множества, обозначается (по-видимому от английского слова Assing – назначать) и вычисляется следующим образом:

=n k .

Таким образом, первый элемент вектора длины k выбирается n способами, второй – n способами и т.д.: n×n×. ×n=n k .

Пример. Сколькими способами можно оснастить две различные фирмы компьютерами трех типов?

Каждый способ оснащения есть выборка (3,2), вектор длины 2, составленный из 3-х элементного множества типов Т=1,t₂,t₃>. Поэтому число способов оснащения – число размещений с повторениями из 3 по 2:

Получили различные упорядочения двухэлементных векторов из 3-х элементного множества, т.е. множество Т 2 .

Здесь каждый вектор соответствует способу оснащения. Видно, что, например, (t₁,t₂), (t₂,t₁) считаются разными способами, так как фирмы предполагаются различными («первая – первым типом», «вторая – вторым» и т.д.). Имеются повторения: (t₁,t₁), (t₂,t₂), (t₃,t₃).

В ряде задач необходимо определить число векторов длины k из n элементов данного множества без повторения элементов.

Если элементы упорядоченной (n,k) выборки попарно различны, то они называются (n,k) размещением без повторений или просто (n,k) размещением.

Число таких размещений без повторений обозначается .

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

=(n-1)(n-2). [n-(k-1)].

Преобразуем эту формулу, умножая и деля ее на произведение чисел 1×2×××(n-k):

В частности, при k=0 . Очевидно, что при k>n =0.

Пример. Сколькими способами из 3-х студентов можно назначить группу на прополку клубники в составе начальника и подчиненного?

Речь идет о выборе упорядоченных двухэлементных подмножеств множества студентов, состоящего из трех элементов (K=<1,2,3>), т.е. о размещениях без повторений из 3 элементов по 2, поэтому:

Подробнее, в виде векторов из номеров студентов, например, по журнальному списку, первая компонента которого обозначает номер студента-начальника, вторая – подчиненного:

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

Пример. Сколькими способами можно провести распределение 10 механизаторов по 3 сушильным установкам? Один механизатор назначается на одну сушильную установку.

Распределение механизаторов – размещение без повторений из 10 элементов по 3, поэтому:

Перестановки

Рассмотрим различные упорядочения n элементного множества Х (вектора длины n, составленные из n элементного множества). В отличие от декартова произведения, полученные при этом векторы, отличаются лишь порядком следования элементов и называются перестановками без повторений из n элементов. Число перестановок без повторений из n элементов обозначается P_n. К перестановкам без повторений можно прийти, полагая, что осуществляется размещение без повторений из n элементов по n:

Считается, что 0!=1.

Пример. Сколько существует возможных последовательностей выполнения проверок финансовой деятельности трех подразделений?

Требуется получить число перестановок без повторений из трех элементов, т.е. Р₃=3!=6.

Получим все эти последовательности:

Пример. Сколько можно составить пятизначных шифров-чисел, не кратных 5, из цифр 1,2,3,4,5 без повторений цифр?

Всего из пяти цифр можно составить Р₅=5!=120 пятизначных шифров-чисел, но они будут включать и кратные 5. Сколько будет шифров кратных 5? Из данного набора чисел кратными 5 могут быть числа, содержащие 5 в младшем разряде. Если цифру 5 записать в младшем разряде, то остальные цифры 1,2,3,4 можно распределить по разрядам Р₄=4!=24 способами. Таким образом, число пятизначных шифров из чисел 1,2,3,4,5 без повторения чисел и не кратных 5 будет 120-24=96.

Перестановки без повторений можно интерпретировать как различные варианты векторов, состоящих из неповторяющихся компонентов, получаемые перестановкой компонентов.

По аналогии при наличии одинаковых компонент в некотором векторе получаем задачу оценки так называемых перестановок с повторениями данного состава [23].

Рассмотрим вначале пример: сколько различных последовательностей – кодов можно получить, переставляя цифры в числе 010, т.е. векторов длины k=3 из 2-х элементного множества В=<0,1>, содержащих два нуля.

Имеется всего три разряда, которые обозначим р₁, р₂, р₃. Их можно переставить р₃=3!=6 способами. Запишем различные получаемые сочетания разрядов и соответствующие коды:

Видно, что коды повторяются тогда, когда несущественен порядок следования разрядов с одинаковой цифрой 0 (р₁,р₃). Все это соответствует тому факту, что имеется два способа (2!) перестановки этих разрядов (р₁,р₃), (р₃,р₁) без изменения кода, т.е. неповторяющихся кодов будет меньше во столько раз, сколько имеется способов перестановки повторяющихся разрядов.

Рассмотрим более сложный случай.

Сколько различных «слов», не обязательно имеющих смысл, можно получить, переставляя буквы в слове «кишмиш»?

Здесь шесть букв слова можно переставить друг с другом р₆=6!=720 способами, но в данном слове буквы «и» и «ш» повторяются дважды и при их перестановке слова могут повторяться. Сколько же существует вариантов перестановок этих букв без изменения слова? Первый вариант – исходный, второй – поменять местами буквы «и», третий – поменять местами буквы «ш», четвертый – поменять местами как буквы «и», так и буквы «ш». Всего четыре варианта. С учетом того, что эти четыре варианта участвуют в порождении 720 способов, получим 720/4=180 различных «слов». Можно показать, что число раз, во сколько уменьшается количество слов по сравнению с числом перестановок без повторений, представляет собой произведение факториалов количества повторяющихся букв.

Таким образом, если из n элементов множества Х=1,x₂. x_n> составлен вектор V длины k, причем каждому i-му компоненту можно поставить в соответствие число k_i, указывающее его число повторений в V, то задан вектор S=(k₁,k₂. k_n), который называется составом данного вектора.

Так, для Х= <0,1,2,3>и V=(010223), состав: S=(2,1,2,1).

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

Общая формула числа перестановок с повторениями данного состава имеет вид

Р(k₁,k₂. k_n)= .

Пример. Сколько различных кодовых последовательностей можно получить перестановками кода 102202030?

Такому вектору, составленному из элементов множеств <0,1,2,3>соответствует вектор состава (1,4,3,1), поэтому число различных кодовых комбинаций определяется как число перестановок с повторениями этого состава

Р(1,4,3,1)= .

Сочетания

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

В результате получают так называемые сочетания без повторения.

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

Число сочетаний без повторений из n элементов по k, обозначаемое как определяется, исходя из числа размещений без повторений с учетом того, что различных неупорядоченных векторов (подмножеств исходного множества) будет меньше в число раз, соответствующее числу перестановок без повторений из k элементов:

Пример. Определить число двухэлементных подмножеств множества, состоящего из трех элементов. Перечисляем все двухэлементные подмножества множества Х=<х₁,х₂,х₃>:

Здесь мы имеем дело с сочетаниями из 3-х по 2:

Это величина в 2! раза меньше, чем число размещений из , поскольку компоненты двухэлементных векторов можно переставить Р₂=2! способами.

Пример. Сколькими способами можно выбрать 3 различных комбайна из 5 имеющихся?

Число размещений из 5 по 3 без повторений: =5×4×3=60.

Один и тот же набор комбайнов можно получить различными способами, например, векторы (а,b,с) и (b,а,с) дают один и тот же набор. Поскольку три элемента можно переставить Р₃=3!=6 способами, то число способов выбора различных 3 комбайнов равно

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

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

Получаем сочетания с повторениями из 2 элементов по 3:

где m означает тип комплекса.

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

Определение числа сочетаний с повторениями можно произвести следующим образом [24].

Каждому сочетанию с повторениями из 2 по 3 ставится в однозначное соответствие вектор длины n+k-1=2+3-1=4, состоящий из 3 нулей и n-1=1 единицы:

Количество комплексов 1-го типа	Разделитель	Количество комплексов 2-го типа	Состав вектора бригады
000	1	(m₁,m₁,m₁)
0	1	00	(m₁,m₂,m₂)
00	1	0	(m₁,m₁,m₂)
1	000	(m₂,m₂,m₂)

В таком случае число сочетаний с повторениями, которое обозначается , равно числу перестановок с повторениями данного состава (вектор имеет одну единицу и три нуля), т.е. Р(3,1)= =4.

В общем случае, это выражение имеет вид

что соответствует выражению

Например, требуется составить подразделения из 6 рабочих 4 специальностей и определить количество способов формирования таких подразделений.

Получаем сочетания с повторениями из 4-х элементов по 6:

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

Сочетаниями без повторений занимался еще великий Паскаль. Он предложил специальную таблицу значений сочетаний без повторений.

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

k n	0	1	2	3	4	5	6	7	8
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
8	1	8	28	56	70	56	28	8	1

Заметим, что .

Этот треугольник удивительно красив своей математической красотой, и в его числах можно при желании отыскать различные закономерности. Его можно представить несколько иначе – в виде [26]: равнобедренного треугольника (рис. 10).

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

Здесь каждое число, кроме единиц на боковых сторонах, является суммой двух чисел, стоящих над ним. Поэтому:

(приводим к общему знаменателю)

(выносим n! за скобку в знаменателе)

Из этого соотношения и вытекает эффективный способ рекуррентного вычисления значений биномиальных коэффициентов.

Докажем соотношение 1)

Это может использоваться при вычислениях, например, вместо можно вычислить .

Докажем соотношение 2)

Бином Ньютона

Имеется формула, называемая биномом Ньютона, которая использует выражения числа сочетаний с повторениями

где а, b – действительные или комплексные числа.

Коэффициенты называются биномиальными.

Докажем формулу бинома Ньютона по индукции. Доказательство по индукции предполагает:

1) базис индукции – доказательство того, что формула верна для конкретного n, например, для n=1. В нашем случае мы убедились, что формула верна для n=2,3,4. Убедимся, что она верна и для n=1.

2) индукционный шаг. Предполагая, что формула верна для некоторого n, убеждаются, что тогда она верна и для n+1.

3) при истинности шагов 1 и 2 заключают, что формула верна для любого n.

Приступим к индукционному шагу.

Возьмем выражение и получим из него выражение для n+1. Очевидно, что это можно сделать путем умножения на a+b:

Преобразуем полученное выражение:

Для выполнения индукционного шага необходимо показать, что это выражение равно выражению:

Рассмотрим подвыражение выражения (1): и заменим i на i-1.

Получим , т.е. одинаковые коэффициенты перед выражениями , для числа сочетаний в первом и втором подвыражении выражения (1).Это позволит вынести за скобку. Но тогда в не учтен n-й член подвыражения (суммирование идет до n): тогда, учитывая его, получаем: