Проверка начальных условий с помощью полученной формулы

,

что согласуется с (1) #

Пример. Пусть дано множество S ={1,2,3,4}. Найти число сочетаний с повторениями при r =2. По прямой формуле: . По рекуррентной формуле: . Если r -сочетание содержит единицу, то это одно из следующих сочетаний: 11, 12, 13, 14 – всего 4 Þ . Если r -сочетание не содержит единицу, то это одно из следующих сочетаний: 22, 23, 24, 33, 34, 44 – всего 6 Þ .

.

Используя рекуррентную формулу, можно построить таблицу для . В приведенной ниже таблице столбцы соответствуют значениям r, строки – значениям n. Так как , в строке 1 находятся единицы. Так как , в столбце 0 находятся единицы. Так как , в столбце 1 находятся номера строк. Из рекуррентной формулы следует, что значение в n -й строке r -м столбце (заданная клетка) равно сумме значения в n ‑й строке (r- 1)-м столбце (клетка слева от заданной) и значения в (n‑ 1)‑й строке r -м столбце (клетка сверху над заданной).

r n						…
						…
						…
						…
						…
						…
M	M	M	M	M	M

Дата добавления: 2014-01-05