Треугольник Паскаля. Рассмотрим рекуррентную по n процедуру определения биномиальных коэффициентов, т.е

Рассмотрим рекуррентную по n процедуру определения биномиальных коэффициентов, т.е. определение если известно Пусть число r- элементных подмножеств (n+1)-элементного множества равно и известно, как определить И пусть |А | = n и мощность множества А È {a₀} равна n + 1.Тогда r- элементные подмножества множества А È {a₀} будут состоять из подмножеств двух типов: тех, которые не содержат элемент а₀, число их будет равно , и тех, которые содержат элемент а₀. Последние можно получить, взяв все (r-1) - элементные подмножества множества А, и добавив к каждому из них а₀. Тогда число r - элементных подмножеств (n + 1)-элементного множества определится, как Это рекуррентное соотношение используется для построения таблицы биномиальных коэффициентов, в которой коэффициенты расположены рядами друг над другом. Ряды следуют в порядке возрастания n, а позиция коэффициента в ряду определяет m, причем 0 £ m £ n, 0 £ n £ N.

Рисунок 1. Треугольник Паскаля.

Таблица биномиальных коэффициентов приводится в математических справочниках и имеет вид, представленный на Рис. 1.