Несколько задач по комбинаторике

[Alexander_rn]

Помогите пожалуйста разобраться со след. задачками, а то всё никак не получается:

1. Упростить:
$\sum_{i=0}^{n}i(i+1){n \choose i}$

2. Найти множитель $x^6$ в разложении $(x^2-2/x)^8$

У меня 0 выходит, сколько ни крутил...

3. Найти комбинаторное доказательство следующего равенства:

$\sum_{i=0}^{n}(-1)^i{n \choose i} (n-i)^n=n!$

Спасибо за внимание! :)

[caxap]

Alexander_rn в сообщении #374590 писал(а):

У меня 0 выходит, сколько ни крутил...

Правильно выходит. Если по биному Ньютона разложить, $x$ будет в степени $3k-8$, а $k$ -- целое от $1$ до $8$.

[Alexander_rn]

caxap в сообщении #374623 писал(а):

Alexander_rn в сообщении #374590 писал(а):

У меня 0 выходит, сколько ни крутил...

Правильно выходит. Если по биному Ньютона разложить, $x$ будет в степени $3k-8$, а $k$ -- целое от $1$ до $8$.

Это радует :) Просто почему-то казалось нелогичным.

А вот с остальными двумя я таки застрял.

В 3-ей задаче ясно что n! это кол-во пермутаций, а левый фланг явно намекает на принцип включения-исключения, а вот применить его всё никак не могу...

[ewert]

Alexander_rn в сообщении #374590 писал(а):

1. Упростить:
$\sum_{i=0}^{n}i(i+1){n \choose i}$

Тупо в лоб. Сперва сверните $\sum_{i=0}^{n}i{n \choose i}$ (факториальчик внизу подсократится, а первое слагаемое, между прочим, исчезнет). Потом $\sum_{i=0}^{n}i(i-1){n \choose i}$ (аналогично). А потом просто скомбинируйте эти два результата.

[EtCetera]

Alexander_rn

Alexander_rn в сообщении #374590 писал(а):

1. Упростить:
$\sum_{i=0}^{n}i(i+1){n \choose i}$

Можно еще так:
$\sum\limits_{i=0}^{n}i(i+1)\binom{n}{i}=\left.\left(\sum\limits_{i=0}^{n}\binom{n}{i}x^{i+1}\right)''\right|_{x=1}=\left.\left(x(x+1)^n\right)''\right|_{x=1}=\dots$
Правда, это не комбинаторное решение...

-- Сб ноя 13, 2010 19:05:56 --

Alexander_rn в сообщении #374590 писал(а):

3. Найти комбинаторное доказательство следующего равенства:

$\sum_{i=0}^{n}(-1)^i{n \choose i} (n-i)^n=n!$

Некомбинаторное решение:
$\sum\limits_{i=0}^{n}(-1)^i\binom{n}{i}(n-i)^n=\left.\left(\sum\limits_{i=0}^{n}(-1)^i\binom{n}{i}e^{x(n-i)}\right)^{(n)}\right|_{x=0}=\left.\left(\left(e^x-1\right)^n\right)^{(n)}\right|_{x=0}$

[Alexander_rn]

Вся беда в том и заключается что надо комбинаторно... :(

[ewert]

Alexander_rn в сообщении #374651 писал(а):

Вся беда в том и заключается что надо комбинаторно... :(

Ну это как-то нелепо смотрится. Типа "угадайте задачку, решением которой было бы такое выражение"

[EtCetera]

Я в комбинаторике ничего не понимаю, но, по-видимому, решение третьей задачи $\text{---}$ это доказательство (тем или иным способом) равенства $\left\{n\atop n\right\}=1$, где $\left\{n\atop k\right\}$ $\text{---}$ числа Стирлинга второго рода.

[Alexander_rn]

ewert в сообщении #374660 писал(а):

Alexander_rn в сообщении #374651 писал(а):

Вся беда в том и заключается что надо комбинаторно... :(

Ну это как-то нелепо смотрится. Типа "угадайте задачку, решением которой было бы такое выражение"

Вот в этой нелепице и проблема :(

[Alexey1]

Alexander_rn в сообщении #374590 писал(а):

3. Найти комбинаторное доказательство следующего равенства:
$\sum_{i=0}^{n}(-1)^i{n \choose i} (n-i)^n=n!$

Справа у Вас стоит факториал, то есть количество способов которыми можно расположить $n$ первых натуральных чисел. Попробуйте использовать формулу включения исключения.

[Alexander_rn]

Alexey1 в сообщении #374698 писал(а):

Alexander_rn в сообщении #374590 писал(а):

3. Найти комбинаторное доказательство следующего равенства:
$\sum_{i=0}^{n}(-1)^i{n \choose i} (n-i)^n=n!$

Справа у Вас стоит факториал, то есть количество способов которыми можно расположить $n$ первых натуральных чисел. Попробуйте использовать формулу включения исключения.

Абсолютно верно, я и сам пошёл тем же путём. Но к сожалению до цели дойти не смог.

[Alexey1]

А в чём сложность?

[Alexander_rn]

Не смог найти как с помощью включения-исключения дойти до кол-ва способов которыми можно расположить n первых натуральных чисел.

[Alexey1]

Подробнее расскажите в чём сложность.

[Alexander_rn]

Даже не знаю как рассказать... Формула очень похожа на формулу включения-исключения в симметрическом случае. Вот я и не смог найти такой вот симметрический случай который бы в итоге дал кол-во пермутаций.