[tenax]

ребята, хелп ми плиз)

дискретная математика, лучше до завтрашнего утра)

1.найти число способов разложить n одинаковых шаров по m разным урнам, причем во второй урне k шаров.

2. \Имеется m разных шаров и m разных корзин. Сколькими способами можно разложить шары по корзинам так, чтобы никакой i-тый шар не попал в i-тую корзину. (пустые корзины допускаются) решить с помощью правила исключений.

3. доказать 1/(1-x)^2=сумма (k от 0 до бесконечности) (k+1)*x^k

4. найти производящую ф-ю последовательности {3^(n+2)-2*(n+1)+3^n/n!}

5. решить однородное рекурентное соотношение
U(n+2)-U(n+1)-2*U(n)=0 U(0)=1, U(1)=0

@темы: Дискретная математика

Comments

[Trotil]

Какие-то догадки будут?

[Trotil]

Вот у меня на листочке решенная за 15 минут котрольная, так что ждем ваши вопросы и ответ на комментарий выше )

[tenax]

ну так)

1. очевидно что одна из урн занят k шарами и общее количество урн в нашей будущей ф-ле будет составлять (m-1), а количество шаров соответственно (n-k). дальше уже не совсем ясно. мы можем положить все шары в первую урну и это будет один способ. далее мы можем взять из нее один шар и это будет еще +(m-2) способов. дальше забираем еще один шар, и у нас есть еще +(m-2)^2. и так пока не останется ни одного шара. но я совсем не уверен)

2.тут меня выбивает из колеи информация про пустые корзины. так количество способов возрастает многократно но как это посчитать представления не имею

3. 1/(1-x)^2=(1-x)^(-2)=(сумма от k=0 до бесконечности) (количеств сочетаний из -2 по k)*(-x)^k=(сумма от k=0 до бесконечности) ((-2)!/k!*(-2-k)!)*(-1)^k*x^k=(сумма от k=0 до бесконечности) (((-2)*(-3)*(-4)*...*(-k-1))/k!)*(-1)^k*x^k=(сумма от k=0 до бесконечности) ((k+1)!/k!)*x^k=(сумма от k=0 до бесконечности) (k+1)*x^k

так?)

4. не имею понятия

5. аналогично)

[tenax]

ну так)

1. очевидно что одна из урн занят k шарами и общее количество урн в нашей будущей ф-ле будет составлять (m-1), а количество шаров соответственно (n-k). дальше уже не совсем ясно. мы можем положить все шары в первую урну и это будет один способ. далее мы можем взять из нее один шар и это будет еще +(m-2) способов. дальше забираем еще один шар, и у нас есть еще +(m-2)^2. и так пока не останется ни одного шара. но я совсем не уверен)

2.тут меня выбивает из колеи информация про пустые корзины. так количество способов возрастает многократно но как это посчитать представления не имею

3. 1/(1-x)^2=(1-x)^(-2)=(сумма от k=0 до бесконечности) (количеств сочетаний из -2 по k)*(-x)^k=(сумма от k=0 до бесконечности) ((-2)!/k!*(-2-k)!)*(-1)^k*x^k=(сумма от k=0 до бесконечности) (((-2)*(-3)*(-4)*...*(-k-1))/k!)*(-1)^k*x^k=(сумма от k=0 до бесконечности) ((k+1)!/k!)*x^k=(сумма от k=0 до бесконечности) (k+1)*x^k

так?)

4. не имею понятия

5. аналогично)

[Trotil]

tenax

1. Ползадачи уже решили )

Существует такая интерпретация задачи:

.найти число способов разложить n одинаковых шаров по m разным урнам

Заменим урны перегородками. Пример: 4 шара, 3 урны

"В первой два шара, в остальных по одному": ШШ|Ш|Ш
"В первой два шара, в третьей - два шара": ШШ||ШШ
"Шары только во второй урне": |ШШШШ|

Задача сводится к числу расстановок шаров и перегородок между ними.

Здесь: Урн - (m-1), перегородок: (m-2), шаров - (n-k).

Нужно записать расстановок шаров и перегородок.

[Trotil]

3. Лучше наоборот!

База: сумма (k от 0 до бесконечности) x^k = 1/(1-x)

Нужно найти сумма (k от 0 до бесконечности) K*x^k = ?
для этого требуется производную от базы с обоих частей.

[Trotil]

5) U(n+2)-U(n+1)-2*U(n)=0 U(0)=1, U(1)=0

Пишем характеристическое уравнение: k^2 - k - 2 =0
Находим корни k1 и k2
Общий вид решения U_n = a *k1^n + b*k2^n
Находим U_0 = ... = 1 и U_1 = ... = 0 - получилось СЛАУ, из которой можно найти a и b.

[Trotil]

найти производящую ф-ю последовательности {3^(n+2)-2*(n+1)+3^n/n!

В википедии есть понятие производящей функции... И примеры по ссылкам.

[Trotil]

(пустые корзины допускаются)

Это значит, что пустые корзины допустаются, и в свою очередь это значит, что каждый шар опускается независимо, для него есть пять положений, значит общее количество - 5^6 = 15625 способов.

Осталась маленькая проблема - тот же ответ нужно получить методом включения - исключения.

[tenax]

1. (n-k+m-2)!/((n-k)!*(m-2)!)

думаю теперь правильно?)

3. разобрался, спасибо)

2. в том-то все и дело. я знаю как бы решалась такая задача, если бы пустые урны не допускались. и еще не понятно откуда взялось

для него есть пять положений, значит общее количество - 5^6 = 15625 способов