Доказательства в комбинаторики[Дискретная математика]

[Worsel]

Добрый вечер! Помогите, пожалуйста, как мне доказать тождества в комбинаторике?
p.s. хотел создать в теме "Дискретная математика, Комбинаторика...", но не получилось

[arseniiv]

Эти формулы можно доказать как «в лоб» с помощью $C_n^k = \frac{n!}{k!(n-k)!}$, так и используя «комбинаторный смысл» сочетаний и размещений (видимо, этот способ вам и нужен?). Например, есть какое-то произвольное размещение из $n$ по $k$. Как его можно получить из размещения из $n-1$?

(Оффтоп)

Worsel в сообщении #778683 писал(а):

p.s. хотел создать в теме "Дискретная математика, Комбинаторика...", но не получилось

Это специально сделано, они потом сортируются по разделам модераторами.

[Worsel]

arseniiv в сообщении #778706 писал(а):

Эти формулы можно доказать как «в лоб» с помощью $C_n^k = \frac{n!}{k!(n-k)!}$, так и используя «комбинаторный смысл» сочетаний и размещений (видимо, этот способ вам и нужен?). Например, есть какое-то произвольное размещение из $n$ по $k$. Как его можно получить из размещения из $n-1$?

Т.е. при n=1, при n=k и при n=k+1 решить?
Вы бы не могли бы 1-ый расписать, чисто для примера, а то я вообще не знаю как

arseniiv в сообщении #778706 писал(а):

(Оффтоп)

Worsel в сообщении #778683 писал(а):

p.s. хотел создать в теме "Дискретная математика, Комбинаторика...", но не получилось

Это специально сделано, они потом сортируются по разделам модераторами.

спасибо

[arseniiv]

Worsel в сообщении #778708 писал(а):

Т.е. при n=1, при n=k и при n=k+1 решить?

Извините, не понял. Если «в лоб», то ничего не надо подставлять. Надо просто заменить в формулах все вхождения $C_n^k$ на соответствующие дроби.

Если это относится к предложению получить сочетание из $n$ по $k$ каким-то образом из сочетаний из $n-1$, то тут тоже всё прямо: есть у вас предметы $1,\ldots,n-1,n$. Из них $k$ каких-то предметов вы выбрали — это то самое сочетание. Теперь представьте, что у вас не было до этого предмета $n$ и было какое-то неизвестное сочетание из $n-1$. Потом $n$ появилось, и вы как-то сделали из неизвестного сочетания известное. Как, и что можно сказать о неизвестном сочетании? Сколько в нём могло быть элементов?

-- Вт окт 22, 2013 23:13:25 --

Ах да, к чему всё это: если вы видите в комбинаторике формулу $A_0 = A_1 + A_2 + \ldots$, в которой $A_i$ — число каких-то штук вида $i$, она, вполне вероятно, может быть получена из того, что каждая штука вида 0 получается или из штуки вида 1, или из штуки вида 2 и т. д., причём из разных получаются разные.

А если видите формулу $A_0 = A_1 \cdot A_2 \cdot\ldots$, то она, сдаётся, означает, что каждая штука вида 0 может быть получена складыванием упорядоченно вместе одной 1-штуки, одной 2-штуки и т. д. (и тут тоже из разных наборов получаются разные 0-штуки).

[Toucan]

Тема перемещена в Карантин.

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.