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

У этой задачи есть другое

У этой задачи есть другое

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

Шаг индукции. Пусть Ап верно. Докажем Ап+1. Для к = 0и к = п +1

по определению треугольника Паскаля ^ п +1) = ^ п + +1 ^ = 1. Оста­лось доказать для 1 ^ к ^ п. Для таких к

(п +1 Ї = (п^ + ( п Ї = ( п Ї + ( п Ї = ( п + 1 |

V к ) 1к^ 1к-1) \п-к) \п-к +1) \п-к +1^

Решение 2. По задаче 4 ( ^ равно числу способов пройти из левого нижнего угла прямоугольника (п - к) х к в правый верхний, идя только вверх или вправо, а [пп ^ —аналогичному числу для пря­моугольника к х (п - к). Но эти числа равны из-за симметрии.

Задача 4. Докажите, что число способов пройти из левого нижнего угла прямоугольника т х п в правый верхний, двигаясь только вверх                                                                                           (^)

( п + тЛ

или вправо по границам клеток, равно ^ J.

Решение. Обозначим число способов пройти из левого нижнего угла прямоугольника т х п в правый верхний указанным способом через С(т, п) (прямоугольником п х 0 считаем отрезок длины п).

Поскольку в любой узел сетки можно попасть либо снизу, либо слева, то С(т, п) = С(т - 1, п) + С(т, п - 1). Кроме того, заметим, что С(п, 0) = С(0, п) = 1. Будем писать в узлах сетки числа С(т, п). По­вернув получившуюся таблицу на 135° по часовой стрелке, получим новую таблицу, которая строится по тому же правилу, что и треуголь­ник Паскаля. Следовательно, эта таблица совпадает с треугольником Паскаля.

& У этой задачи есть другое решение индукцией по т + п, на при­мере которого школьников можно учить аккуратно записывать рас­суждения «по индукции», относящиеся к биномиальным коэффици­ентам.

Задача 5. В каких строках треугольника Паскаля все числа нечет­ные?

122                     Комбинаторика 2. Бином Ньютона