Комбинаторная задача

[Whitaker]

Здравствуйте!
В урне лежат жетоны с числами 1,2,3,4,5,6,7,8,9,10. Вынимают три жетона. Во скольких случаях сумма написанных на них чисел будет равна 9?
Эта задача эквивалентна следующей: Сколько существует троек вида $(n,m,p)$ такие, что $n+m+p=9$, где $n,m,p \in \mathbb{N}$ и $n\neq m \neq p$.
Не догадываюсь с чего начать и как сделать. Подскажите пожалуйста.

[Sonic86]

Сначала попробуйте просто найти число решений уравнения $x_1+x_2+x_3=N$ в натуральных $x_j$. Если затрудняетесь - найдите сначала число решений уравнения $x_1+x_2=N$. Здесь будет удобно использовать символику функции числа решений уравнения.

[Whitaker]

Уважаемый Sonic86. Число решений уравнения $x_1+x_2+...+x_n=k$ в целых неотрицательных числах равно $C_{n+k-1}^{n-1}$.
А вот число решений того же уравнения в натуральных числах равно $C_{k-n}^{n-1}$. Но к сожалению последнее утверждение я не могу доказать никак.

[Sonic86]

Whitaker в сообщении #477358 писал(а):

А вот число решений того же уравнения в натуральных числах равно $C_{k-n}^{n-1}$. Но к сожалению последнее утверждение я не могу доказать никак.

Для уравнения в натуральных числах $x_j$ надо сделать замену $x_j=y_j+1$, и тогда $x_j \in \mathbb{N} \Leftrightarrow y_j \in \mathbb{N} \cup \{ 0\}$.
Можно и по-другому: рассмотреть случаи $x_j = 0 \vee x_j \neq 0$ и подставить...
Наконец, можно просто в лоб подсчитать, аналогично подсчету числа решений уравнения в неотрицательных числах.

[Whitaker]

Уважаемый Sonic86. Я последовал вашему совету и у меня получилось так: Число решений уравнения $x_1+x_2+....+x_n=k$ в натуральных числах равно $C_{k-1}^{n-1}$.
То что вы просили.

[Sonic86]

(Оффтоп)

ой! а можно без "уважаемого"

Ну вот теперь Вы можете найти число решений уравнения $m+n+p=9$ при $m,n,p \in \mathbb{N}$. Теперь подумайте, как еще учесть условия различности $m,n,p$.
Опять же - если затруднитесь - сократите число переменных до 2-х.

[Whitaker]

А вот неизвестно мне пока число решений уравнения $x_1+x_2+....+x_n=k$ в натуральных числах и $\forall {i,j}$ было $x_i \neq x_j$

[Sonic86]

Whitaker в сообщении #477428 писал(а):

А вот неизвестно мне пока число решений уравнения $x_1+x_2+....+x_n=k$ в натуральных числах и $\forall {i,j}$ было $x_i \neq x_j$

Здесь пока лучше ограничится только случаем $n=3$ (общая формула подзадачи Вам все равно потом понадобится). Может кто-то и знает, но я для произвольного $n$ пока не вижу как.

[Whitaker]

Думаю, что можно так сделать. Дано уравнение $x_1+x_2+x_3=k$. Всего натуральных троек $(x_1; x_2; x_3)$ ровно $C_{k-1}^{2}$.
Найдём количество различных троек, т.е. $x_1 \neq x_2 \neq x_3$. Для этого определим количество троек где есть одинаковые слагаемые.
Случай 1. Пусть $k$ - четное число, т.е. $k=2m$. Тогда тройки с одинаковыми слагаемыми это:
$(x_1; x_2; x_3)=(1,1,2m-2), (2,2,2m-4), (3,3,2m-6).....(m-1, m-1, 2)$
Их всего $m-1$.
А если еще число $k=3p$, то тройкой с одинаковым слагаемыми будет: $(p,p,p)$. В этом случае будет $m$.
Случай 2. Пусть $k$ - нечетное число, т.е. $k=2m+1$. Тогда тройки с одинаковыми слагаемыми это:
$(x_1; x_2; x_3)=(1,1,2m-1), (2,2,2m-3), (3,3,2m-5).....(m-1, m-1, 3), (m,m,1)$
Их всего $m$.
А если еще число $k=3t$, то такой тройкой будет еще $(t,t,t)$
В этом случае будет $m+1$

[Whitaker]

P.S. Забыл, что эти повторяющиеся тройки можно переставлять $P(1,2)=3$ способами. Остался только подсчёт и всё.

-- Ср авг 24, 2011 19:52:19 --

Там еще такая подзадача. Во скольких случаях сумма написанных на них чисел будет не меньше 9? Т.е. нужно найти количество решений неравенства $x_1+x_2+x_3 \geq 9$. Как ее решить?

[Sonic86]

Ну я предполагал по формуле включений-исключений сделать так:
Для $n=2$:
$N(x_1+x_2=k, x_1 \neq x_2) = N(x_1+x_2=k) - N(x_1+x_2=k, x_1 = x_2)$
Здесь $N(F(x_1,...,x_n)=0)$ - число решений уравнения $F(x_1,...,x_n)=0$ - это такой удобный формализм.

Whitaker в сообщении #477459 писал(а):

$x_1 \neq x_2 \neq x_3$.

Правильнее писать $x_1 \neq x_2 \neq x_3 \neq x_1$