3.5. Свойства биномиальных коэффициентов

Своим историческим названием числа C_n^r обязаны формуле бинома Ньютона:

(a + b)ⁿ = Σ _rⁿ _{= 0} C_n^ra^rb^n-r . (3.13)

В этой формуле числа C_n^r определяют число про­изведений a^rb^n-r, которое равно числу всех сочетаний из n по r при суммировании этих произведений от r = 0 до n. Этот факт имеет вполне комбинаторное обоснование. Формула (3.13) относится к классу производящих функций, которые будут рассмотрены в 3.6. Здесь же нас интересуют свойства биномиальных коэффициентов.

Полагая в (3.13) a = b = 1, получим, что

Σ_rⁿ _{= 0} C_n^r = 2ⁿ _. (3.14)

Этой формулой выражается число всех r‑подмножеств n‑X множества .

Из формул (3.6) и (3.12) следует, что

Структура соединений

F: r‑ S → n‑X,

r = 3, n = 4.

Размещений:n^r

111 112 113 114

121 122 123 124

131 132 133 134 Всех

141 142 143 144 инъективных (упорядоченных)

размещений:

211 212 213 214 A_n^r = n(n - 1)···(n - (r - 1))

221 222 223 224

231 232 233 234 123 132 213 231 312 321

241 242 243 244 124 142 214 241 412 421

134 143 314 341 413 431

311 312 313 314 234 243 324 342 423 432

321 322 323 324

331 332 333 334 перестановок: r!

341 342 343 344

Cочетаний, как классов

411 412 413 414 инъективных размещений:

421 422 423 424 C_n^r = A_n^r / r! = n! / (r!(n -r)!)

431 432 433 434

441 442 443 444

Рисунок 3.4

C_n^r = n(n - 1)…(n - (r - 1)) / r!.

Умножив и разделив обе части этого равенства на (n - r)!, получим

C_n^r = n!/(r!(n - r)!). (3.15)

Из этой формулы при подстановках вместо rзначения (n-r) следует, чтоC_n^r=C_n^n-r. Это свойство именуетсясимметрией биномиальных коэффициентов.

Далее, при r = 0 или r = n из (3.15) имеем

C_n⁰ = C_nⁿ = 1. (3.16)

Докажем, что для C_n^r имеет место соотношение:

C_n^r = C_n^r_-1+ C_n^r_-1^-1. (3.17)

Зафиксируем любой элемент x_i в ‹x₁, x₂, …x_n›. Тогда мно­­жество всех r‑элементных подмножеств n‑X множества рас­падается на два непересекающихся класса: тех, что не со­дер­жат x_i и тех, что его содержат. Число элементов первого клас­са равно C_n^r_-1, так как r‑подмножество строится на (n-1)‑X множестве. Число элементов второго класса равно C_n^{r -}_{- 1}¹, поскольку эти элементы определяются всеми (r-1)­‑под­множествами, построенными на (n-1)‑X множестве, с ко­торыми комбинирует элемент x_i. Доказательство окон­че­но.

Свойства (3.16) и (3.17) позволяют расположить биномиальные коэффициенты в виде треугольника, по краям которого записаны единицы, а каждый элемент внутри вычисляется как сумма чисел, находящихся в верхнем ряду над ним. Строки имеют номера, идущие сверху вниз, на­чинаясь с нуля. Ими определяется значения n в (3.17). Значения r в этом же соотношении определяются номером эле­мента в строке. Эти значения также начинаются с нуля.

Построенная треугольная таблица чисел известна как треугольник Паскаля. Ниже приведены числа треугольника Паскаля для строк с номерами от нуля до пяти. Из таблицы видно, что она наглядно определяет значения биномиальных коэффициентов при малых значениях n и r.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

…………………………..