Комбинации с повторения?

[kratuncho]

Здравейте,
Имам проблем със следната задача:
"В книжарница продават марки от 10 вида, като от всеки вид има поне 8 марки. Да се намери по колко начина могат да се купят 8 марки. (отг. 24 310)"

Разсъждавам по следния начин:
1 марка избираме като комбинация с повторения на 10 елемента от 8 клас, след което умножавам по 8 и получавам 155 584.

Задачата изглежда лесна, но не знам къде бъркам . Всякакви идеи са добре дошли.

[pal702004]

Не. Композиции на числото 8 с дължина 10, включващи нули

[tex]{8+10-1 \choose 10-1}[/tex]

[kratuncho]

Не разбрах как се получава биномния коефициент. Как се сещам, че трябва да използвам композиция ?

[drago]

Това с марките е еквивалентно на следното:
Да се намерят всички наредени 8-рки естествени числа [tex](x_1,x_2,\dots,x_8)[/tex] удовлетворяващи [tex]1\leq x_1\leq x_2 \leq \dots \leq x_8 \leq 10[/tex].
Ако неравенствата бяха строги щяхме да имам [tex]\binom{10}{8}[/tex] начини. Сега се прави следния трик: на [tex](x_1,x_2,\dots,x_8)[/tex] се съпоставя [tex](y_1,y_2,\dots,y_8)[/tex] с правилото: [tex]y_1 := x_1, y_2 := x_2+1,\dots,y_8 := x_8 +7[/tex]. Сега игреците вече са различни и са м/у 1 и 10+7=17. Тъй като това е взаимно еднозначно съответствие (защо?) то търсения брой е [tex]\binom{17}{8}[/tex]

ПП. Няма нужда да се помни формула за комбинации с повторение. Запомнете този трик! Тази година на Турнира на Декана във ФМИ имаше подобна задача и малко хора я бяха направили.

[pal702004]

Друг (по-естествен според мен начин е, че задачата се свежда до: Да се намери броят на различните наредените 10-ки цели неотрицателни числа, [tex](m_1,m_2,\cdots m_{10})[/tex], такива че [tex]m_1+m_2+\cdots+m_{10}=8[/tex] (нали, имам две марки с Гагарин, 1 с Иванов, 0 с Амрстронг и т.н), което си е композиции на числото 8 с дължина 10, естествено с нули. (дължина е броят на събираемите).

Броят на композициите на числото [tex]n[/tex] с дължина [tex]k\le n[/tex] без нули е [tex]C_{n-1}^{k-1}[/tex]. (Да разделим [tex]n[/tex] единици с "прегради" [tex]1|1|1\cdots|1[/tex]. Броят на преградите е [tex]n-1[/tex]. По колко начина можем да изберем прегради, които трябва да махнем, за да получим [tex]k[/tex] събираеми...)

Как да получим броят на композициите с нули? Ами ако добавим към всяко число 1, ще получим композициите без нули на [tex]n+k[/tex]

Или, броят на композициите с нули е [tex]C_{n+k-1}^{k-1}[/tex]

[drago]

Хм..., явно има разлика в "отговорите" Къде е грешката? Все пак, май че броя на комбинациите с повторение на k елемента от общо n е [tex]\binom{n+k-1}{k}[/tex] ?

[pal702004]

Грешка, разбира се, няма . При нас [tex]n[/tex] и [tex]k[/tex] са "разменени". Освен това

[tex]{n+k-1 \choose k-1}={n+k-1 \choose n}[/tex]