Дискретная математика

107 Это соответствие, как легко видеть, взаимно однозначное и при этом г- выборка (4.5) является г-сочетанием без повторений из множества {1,2,..., п, «+], /7+2,..., п+г-\}. Таким образом, число г-сочетаний с повторениями из п- множества равно числу . Свойства чисел С,^. По определению чисел получим, что (по опрвделенто 0/=1): € „"=!; с М ; Г ' _ Г' " ~7? Г7" • г!( п~г)! Последнее свойство называется правилом ашметрии. Следующее соотношение называется правшам Паскаля: С + г"'"' Докажем это правило. Из определения чисел имеем: С' г!(п-1 -г)! (г - 1)!(п-1 -г +1) (п- }•)(п - 1)!+г( п~1)1 п! _ г г!(п-1)! г!(п-г)! ч т о и требовалось. Используя формулу Стирлинга: п! = ^2гсп(^-^ (]+0(1/п)), м о жн о получить следующую оценку чисел : 7 - - ' Ч т § 4. Биноминальная теорема Теорема 4.1. (Биноминальная теорема). Для произвольных чисел а, Ъ и целого положительного п имеет место соотношение: " (4 6 ) (a+b)"=T.C „ci"-'b'. ^ ^ 1=0 Формула (4,6) называется биномом Ньютона или биноминальной формулой (теоремой). Доказательство теоремы проведем методом математической индукции. Для п=1 имеем: