2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Несколько задач по комбинаторике
Сообщение13.11.2010, 17:12 
Помогите пожалуйста разобраться со след. задачками, а то всё никак не получается:

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!$

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

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 18:26 
Аватара пользователя
Alexander_rn в сообщении #374590 писал(а):
У меня 0 выходит, сколько ни крутил...

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

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 18:34 
caxap в сообщении #374623 писал(а):
Alexander_rn в сообщении #374590 писал(а):
У меня 0 выходит, сколько ни крутил...

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


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

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

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

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 18:41 
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}$ (аналогично). А потом просто скомбинируйте эти два результата.

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 18:43 
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}$

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 19:08 
Вся беда в том и заключается что надо комбинаторно... :(

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 19:22 
Alexander_rn в сообщении #374651 писал(а):
Вся беда в том и заключается что надо комбинаторно... :(

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

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

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 19:54 
ewert в сообщении #374660 писал(а):
Alexander_rn в сообщении #374651 писал(а):
Вся беда в том и заключается что надо комбинаторно... :(

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


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

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 20:19 
Alexander_rn в сообщении #374590 писал(а):
3. Найти комбинаторное доказательство следующего равенства:
$\sum_{i=0}^{n}(-1)^i{n \choose i} (n-i)^n=n!$
Справа у Вас стоит факториал, то есть количество способов которыми можно расположить $n$ первых натуральных чисел. Попробуйте использовать формулу включения исключения.

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 21:10 
Alexey1 в сообщении #374698 писал(а):
Alexander_rn в сообщении #374590 писал(а):
3. Найти комбинаторное доказательство следующего равенства:
$\sum_{i=0}^{n}(-1)^i{n \choose i} (n-i)^n=n!$
Справа у Вас стоит факториал, то есть количество способов которыми можно расположить $n$ первых натуральных чисел. Попробуйте использовать формулу включения исключения.


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

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 21:10 
А в чём сложность?

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 21:15 
Не смог найти как с помощью включения-исключения дойти до кол-ва способов которыми можно расположить n первых натуральных чисел.

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 21:17 
Подробнее расскажите в чём сложность.

 
 
 
 Re: Несколько задач по комбинаторике
Сообщение13.11.2010, 21:27 
Даже не знаю как рассказать... Формула очень похожа на формулу включения-исключения в симметрическом случае. Вот я и не смог найти такой вот симметрический случай который бы в итоге дал кол-во пермутаций.

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group