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

Рассмотрим треугольник Паскаля по модулю

Рассмотрим треугольник Паскаля по модулю

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

Ответ. В строках с номерами вида 2п.

Указание. Треугольник Паскаля «по модулю 2» получается из обыч­ного заменой всех четных чисел на 0, а нечетных — на 1. Выпишите первые 16 строк этого треугольника. (Как по уже выписанной строке этого треугольника построить следующую?)

Решение. Рассмотрим треугольник Паскаля «по модулю 2», то есть треугольник, который получается из треугольника Паскаля заме­ной всех четных чисел на нули, а нечетных на единицы. Заметим, что такой треугольник может быть получен способом, аналогичным определению треугольника Паскаля, только с таблицей сложения 0 + 0 = 1 + 1 = 0, 0 +1 = 1 + 0 = 1.

1       0 1 1111

1 0 0 0 1 110011 10 10 10 1 11111111 100000001 1100000011 10100000101 111100001111 1000100010001 11001100110011 101010101010101 1111111111111111

Рассмотрим последовательность утверждений Ап: В 2п-й строке треугольника Паскаля «по модулю 2» все числа — единицы, а при 2п-1 < к < 2п в к-й строке есть нуль.

База. п = 0. Очевидно.

Шаг индукции. Пусть утверждение Ап верно. Докажем утвержде­ние Ап+1. Заметим, что в (2п + 1)-й строке первое и последнее числа — единицы, а остальные — нули. Следовательно, при 2п < к ^ 2п+1 к-я строка устроена следующим образом: слева и справа (к — 2п)-я стро­ка, а между ними нули (упражнение: доказать индукцией по к). При этом в 2п+х-й строке будут только единицы (2п единиц справа, 2п слева, нулям места не хватает). Шаг индукции доказан.

Определение 2. Числом сочетаний из п пот называется количество т-элементных подмножеств множества из п элементов. Обозначение:

Ст.

п

& Другими словами, Ст —это число способов выбрать т предметов из п различных предметов. Существенно, что порядок выбора не имеет значения.

Задача 6. Найдите: а) С[00, б) С^, в) С|, г) С^.