Бином Ньютона, или Треугольник Паскаля
Треугольник Паскаля — это последовательность рядов чисел, которые строятся по следующему принципу: первый ряд состоит из одного числа 1, каждый следующий ряд состоит из попарных сумм соседних элементов предыдущего ряда, а также начальной и конечной единиц. Например, первые пять рядов таковы:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Скажем, ряд «1 4 6 4 1» получается из предыдущего ряда «1 3 3 1» так: в начале всегда 1, 1+3=4, 3+3=6, 3+1=4, в конце всегда 1.
Числа, составляющие треугольник Паскаля, обладают многочисленными важными и интересными свойствами. В частности, они встречаются в биноме Ньютона — формуле для разложения суммы двух переменных на отдельные слагаемые:
(a+b)^n=SUMM[C(n.k)*a^(n-k)*b^k] k=0...n =
=C(n,0)*a^n+C(n,1)*a^n-1*b+...+C(n,n-1)*a*b^n-1+C(n,n)*b^n
Поэтому эти числа также называются биномиальными коэффициентами.
Напишите программу, которая выводит первые несколько рядов треугольника Паскаля.
Натуральное число n — количество рядов треугольника Паскаля, которые нужно вывести.
Элементы n первых рядов треугольника Паскаля, разделённые символами пустого пространства (пробелами, табуляциями, переносами строки); точный формат вывода неважен, но крайне желательно, чтобы одному ряду треугольника Паскаля соответствовала одна строка вывода.
Пример
Ввод
4
Вывод
1
1 1
1 2 1
1 3 3 1