Таблицы Брадиса

Например, подмножеству М а, с,

Например, подмножеству М а, с,

Элементы математики в задачах - Г. А. Мерзон

Ясно, что если мы будем расставлять скобки произвольно, то по­лучим бесконечно много вариантов. Поэтому возможное разумное прочтение условия такое:

Будем считать две расстановки скобок в выражении а + Ь — с ■ д одинаковыми, если при подстановке в них любого набора чисел (а, Ь, с, д) получается одно и то же число. Сколько существует различных (в этом смысле) расстановок скобок?

Решение. Расставить скобки — это то же самое, что определить по­рядок выполнения действий. В каком порядке выполнять сложение и вычитание неважно, остается решить, в какой момент выполнять умножение. Получаются 3 выражения:

(а + Ь — с ■ д), а + (Ь — с) ■ д, (а + Ь — с) ■ д.

Остается убедиться, что при некоторых значениях а, Ь, с и д все эти выражения принимают попарно различные значения. Для этого подойдут практически любые значения переменных, например, а = 3, Ь = 2, с = 1, д = 0.

Задача 10. а) Докажите, что подмножеств в множестве {а, Ь, с, д, е} столько же, сколько отображений этого множества в множество {0, 1}. б) Докажите, что это число равно числу последовательностей нулей и единиц длины пять.

Комбинаторика 1

Решение. Каждому подмножеству М множества А = {а, Ь, с, d, е} мы можем естественным образом сопоставить отображение / из мно­жества А в множество {0,1} по следующему правилу: элемент х е А отображается в 1 (то есть /(х) = 1), если х лежит в М, и в 0, если не лежит. Нетрудно заметить (хотя это надо формально и аккуратно проверить), что мы построили биекцию.

В пункте б) действуем аналогично. То есть строим биекцию из множества всех подмножеств множества А = {а, Ь, с, d, е} в множество последовательностей из нулей и единиц. Например, подмножеству М = {а, с, е} мы сопоставим последовательность (1, 0,1, 0,1); подмно­жеству М = {Ь, с} сопоставим (0,1,1, 0, 0); подмножеству М = {а, d, е} сопоставим (1, 0, 0,1,1) и так далее. А именно, занумеруем элементы множества, после чего любому подмножеству поставим в соответ­ствие последовательность, у которой на каждом месте стоит 1, если этот элемент принадлежит подмножеству, и 0, если нет.