Чему равна сумма чисел $%𝑛$%-й строки треугольника Паскаля с номерами кратными 3? В особенности интересует комбинаторное доказательство. Как тут рассуждать?

задан 2 Апр 16:51

изменен 2 Апр 16:52

@Autocellar: стандартный путь таков (на форуме не раз обсуждалось). Берём биномиальную формулу (1+x)^n, и подставляем туда комплексные корни степени 3 из единицы. Получаем систему, которая связывает между собой три суммы. В каждой из них берутся числа C_n^k с заданным остатком от деления k на 3. После решения системы получается значение каждой из сумм в виде (2^n+A)/3, где A -- "поправка", принимающая значения +-1, +-2 с периодом 6.

Чисто комбинаторное доказательство тут если и возможно, то оно длинное и искусственное, скорее всего.

(2 Апр 18:38) falcao
10|600 символов нужно символов осталось
3

На самом деле, тут есть и чисто простые комбинаторные соображения, хотя вид формул нуждается в некоторой "доводке". Комплексных чисел и прочего не привлекаем.

Вводим три величины a(n), b(n), c(n) -- это число подмножеств n-элементного множества, число элементов в которых сравнимо с 0, 1, 2 по модулю 3, соответственно.

Ясно, что a(0)=1, b(0)=c(0)=0. Теперь выведем рекуррентные формулы. Пусть n>=1. Зафиксируем некоторый элемент x из множества. Чему равно a(n)? Подмножества, в которых число элементов кратно 3, либо содержат x в качестве элемента, либо не содержат. Подмножеств второго вида a(n-1), а подмножеств первого c(n-1), так как удаление элемента x даёт подмножество (n-1)-элементного множества с числом элементов =2(mod 3). Аналогично для b(n) и c(n). В итоге имеем такие рекуррентные формулы при n>=1:

a(n)=a(n-1)+c(n-1)

b(n)=b(n-1)+a(n-1)

c(n)=c(n-1)+b(n-1)

Им соответствует матрица (1 1 0 // 0 1 1 // 1 0 1). Применяя её к вектору-столбцу (1 0 0), мы получаем все следующие векторы вида (a(n),b(n),c(n)).

Чтобы проследить явный вид этих величин, для начала замечаем, что подмножеств каждого из типов примерно поровну, то есть около 2^n/3. Тогда умножаем их на 3 и сравниваем с 2^n. Отличие там составляет +-1 или +-2, и при этом имеет место периодичность этой "погрешности" с периодом 6. Дальше можно выписать явно формулы для всех случаев, и доказать их методом математической индукции.

ссылка

отвечен 2 Апр 19:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,476
×1,297
×16

задан
2 Апр 16:51

показан
178 раз

обновлен
2 Апр 19:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru