Индукция в комбинаторике

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

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

База при очевидна.

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

— посчитали все элементы выкинутого множества.

— посчитали количество множеств, пересекающихся с выкинутым(по каждому из элементов с ним пересекается множество, c другой стороны по условию оно пересекается с множествами).

Тогда по ранее проведённым рассуждениям при возврате выкинутого множества сумма из условия увеличится на

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