Комбинаторика: количество 7-значных чисел с суммой цифр 41

[RinaM]

Условие:
Сколько существует 7-значных чисел, у которых сумма цифр равна 41? Число может начинаться с нуля.
Попытка решение:
Задачу можно ряшить используя метод единиц - имеющиеся 41 единицу расставляем без учета порядка по 7 разрядам.
Примение формулу С с чертой из 7 по 41 (=(41+7-1)!/(41!*(7-1)!)) получим общее число этих чисел.
Однако необходимо учесть, что мы не можем поставить больше 9 единиц в один разряд.
Здезь необходимо использование формулы включений-ислючений. Проблема в том что не найдена формула для для A[i] - множества чисел, не удовлетворяющих данному условию.
Вопрос - какая это формула?
Или можно по-другому решить эту задачу?

[Whitaker]

В Виленкине "Комбинаторика" есть такой параграф "Жетоны в мешке".
Пусть имеется мешок, в котором $m$ занумерованных жетонов - на них написаны числа $0,1,...,m-1$. Из мешка вытаскивают очередной жетон, записывают его номер, затем кладут жетон обратно в мешок. Так получают последовательность из $n$ чисел, каждое из которых заключено в пределах от $0$ до $m-1$. Требуется узнать, сколько из получающихся таким образом различных последовательностьей имеют сумму $N$.
Эту величину обозначим через $C_m(n,N)$.

Существует такая реккурентная формула: $C_m(n,N)=C_m(n-1,N)+C_m(n-1,N-1)+C_m(n-1,N-2)+...+C_m(n-1,N-m+1)$.
В вашем случае нужно найти $C_{10}(7,41)$

-- Пт ноя 18, 2011 19:26:52 --

Вашу задачу также можно решить методом включений-исключений. Подумайте как сделать

[Null]

Если в каком-то разряде стоит "цифра" $\ge 10$ вычтите 10 из нее и из суммы цифр.(Сколько таких вариантов?)

Правда это будет только второе слагаемое суммы включений-исключений

[Shadow]

А я увидел в заголовке слово "информатика" и не постыдился включить Excel и решить задачу. Вам что нужно, аналитическая формула, или алгоритм?

[Whitaker]

Null Вам дал очень ценную подсказку. Воспользуйтесь ею.

[Zealint]

Ответ к вашей задачи, если я с утра ничего не перепутал, будет 247380.
А решается она методом производящих функций. Вам нужен коэффициент при $z^{41}$ разложения функции

$$ G(z) = \left(\frac{1-z^{10}}{1-z\phantom{^{10}}}\right)^7= 1+7z+28z^2+84z^3+\cdots+\underline{247380}z^{41}+O(z^{42}). $$

Который нетрудно отыскать через бином ньютона. Почему это так?

Ответ вы найдёте здесь, где аналогичная техника использовалась для того, чтобы узнать, сколько 6-значиных чисел имеют сумму 27 (счастливые билеты).

[Null]

Zealint, как вы собираететесь это считать? можете объяснить по подробнее?

[Zealint]

Null в сообщении #505405 писал(а):

Zealint, как вы собираететесь это считать? можете объяснить по подробнее?

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

И притом я же дал ссылку на сайт, где аналогичный пример считается подробно. Но попробую, раз влез в тему...

Очевидно, что

$$ G(z)=\left(\frac{1-z^{10}}{1-z}\right)^7=(1-z^{10})^7(1-z)^{-7}= \sum_{n=0}^{\infty}\binom{7}{n}(-z^{10})^n\sum_{n=0}^{\infty}\binom{-7}{n}(-z)^n. $$

Нам нужно собрать множитель при $z^{41}$. Перебираем все возможности получить такую степень:

$$ [z^{41}]G(z) = -\binom{7}{0}\binom{-7}{41}+\binom{7}{1}\binom{-7}{31} -\binom{7}{2}\binom{-7}{21}+\binom{7}{3}\binom{-7}{11}-\binom{7}{4}\binom{-7}{1}=247380. $$

Сейчас ясно или мне следует ещё подробней расписать? Если да, то что именно вызвало затруднение?