Биномиальная теорема и тождества: какие комбинаторные тождества реально нужны на олимпиадах?
Знаю биномиальную теорему (a+b)^n = Σ C(n,k) a^k b^{n-k}, но на контестах часто нужно быстро свернуть какую-нибудь сумму с C(n,k). Какие тождества стоит знать наизусть и как их доказывать комбинаторно, чтобы не зубрить, а выводить?
2 ответа
Минимальный набор, который реально экономит время:
- Σ_{k=0}^{n} C(n,k) = 2^n (подставь a=b=1 в бином — число всех подмножеств).
- Σ_{k=0}^{n} (−1)^k C(n,k) = 0 при n≥1 (a=1, b=−1; чётных и нечётных подмножеств поровну).
- Тождество симметрии: C(n,k) = C(n,n−k).
- Рекуррента Паскаля: C(n,k) = C(n−1,k−1) + C(n−1,k).
- «Хоккейная клюшка»: Σ_{i=k}^{n} C(i,k) = C(n+1,k+1).
- Свёртка Вандермонда: Σ_{k} C(m,k)·C(n,r−k) = C(m+n, r).
Комбинаторное доказательство Вандермонда: выбираем r человек из группы m мужчин и n женщин; перебор по числу k выбранных мужчин даёт левую часть, а прямой выбор — правую. Такие «двойные подсчёты» — главный способ доказывать тождества без алгебры.
На практике это позволяет, например, сумму Σ C(n,k)·C(n,k) = C(2n,n) увидеть как частный случай Вандермонда (m=n, r=n, с симметрией) и не считать её циклом.
Ещё два полезных: Σ_{k} k·C(n,k) = n·2^{n−1} (продифференцируй бином по a или посчитай «выбрать комитет и председателя»), и поглощающее тождество k·C(n,k) = n·C(n−1,k−1). Последнее часто спасает, когда в сумме мешается множитель k — его «снимают» этим тождеством и сводят к стандартной сумме.