Задача 30712

Темы:    [ Треугольник Паскаля и бином Ньютона ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 3+ Классы: 8,9

Условие

Докажите, что  

Решение 1

   – это количество "чётных" подмножеств множества из n элементов, а      – количество "нечётных" подмножеств. Эти количества равны (см. решение 1 задачи 30711).

Решение 2

Сумма чисел, стоящих на чётных местах в n-й строке треугольника Паскаля, равна сумме чисел, стоящих на нечётных местах той же строки. Действительно, пусть в предыдущей строке стоят числа  c₀, c₁, ..., c_n–1.  Тогда на чётных местах n-й строки стоят числа  c₀,  c₁ + c₂,  c₃ + c₄, ...; их сумма равна
c₀ + c₁ + ... + c_n–1.  А на нечётных местах стоят числа  c₀ + c₁,  c₂ + c₃,  c₄ + c₅, ...  с той же суммой.

Замечания

См. также решение задачи 60412 б).

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	11
Название	Комбинаторика-2
Тема	Классическая комбинаторика
задача
Номер	026