Сочетания и бином Ньютона
В математике известна формула бинома (двучлена) Ньютона. Она используется для возведения двучлена a + b в n-ю степень. Эта формула имеет вид:
Числа
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Его можно записать иначе и сразу обозначить строки треугольника:
Номера строк. Треугольник Паскаля.
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
. . . . . . . . . . . . . . . . .
n
Пример 11. Вычислить сумму пяти средних элементов девятой строки треугольника Паскаля.
Всего в девятой строке треугольника Паскаля 10 элементов. Пять средних элементов будут находиться начиная с третьего места и по 7-е место.
Эти элементы будут следующими:
Ясно, что для вычисления их суммы необходимо организовать цикл по "верхним" индексам сочетаний. Каждый цикл надо вызывать процедуру числа сочетаний из 9 элементов по j (j - переменная цикла) и прибавлять к переменной, заведенной для суммы.
Программа
Program Problem11;
uses WinCrt;
var
s, j, s1 : longint;
{----------------------------------------------------------------------------------------}
Procedure Combination(n, k : integer; var c : longint);
var
i : longint;
begin
c := 1;
for i := 1 to k do
c := c*(n - k + i) div i
end;
{----------------------------------------------------------------------------------------}
begin
s := 0;
for j := 2 to 6 do
begin
combination(8, j, s1); s := s + s1
end;
writeln('Сумма пяти средних элементов 9-й строки равна ', s)
end.
Пример 12. Составить программу вывода на экран n заданных строк треугольника Паскаля.
Понятно, что для вывода строк треугольника Паскаля на экран необходимо организовать два цикла for. Один - по числу строк, второй - по числу элементов в каждой строке.
Первый, внешний цикл, для числа строк должен быть организован от 0 до n, пусть с переменной j1.
Второй, внутренний цикл, надо организовать от 0 до j1. Это легко объясняется тем, что в каждой строке должно быть на 1 больше элементов, чем номер ее строки. В нулевой строке 1 элемент, в 1-й 2 элемента, во 2-й три элемента и т. д., в n-й строке будет n + 1 элементов. Такое вызвано тем, что элементы начинают нумероваться с нуля.
Программа
Program
Problem12;
uses WinCrt;
var
j, j1, n, p : longint;
{----------------------------------------------------------------------------------------}
Procedure Combination(n, k : integer; var c : longint);
var
i : longint;
begin
c := 1;
for i := 1 to k do
c := c*(n - k + i) div i
end;
{----------------------------------------------------------------------------------------}
begin
write('Введите число строк треугольника Паскаля ');
readln(n);
writeln('Треугольник Паскаля ');
for j1 := 0 to n do
begin
for j := 0 to j1 do
begin
combination(j1, j, p);
write(p, ' ')
end;
writeln
end
end.
