[Комбинаторика] Задачи из книги Combinatorial Theory by Hall

[Klekota]

Доброго времени суток. Пытаюсь вспомнить комбинаторику, посему приступил к данной книге. Увы решебник я не смог найти, поэтому прошу помочь решить, то что у меня не вышло и скорректировать ответы. Задачки не тяжелые, но приятные для разминки))




2. $3\cdot2^{12}$
3. Я построил матрицу, которая похожа на треугольник биномиальных коэффициентов, но как сумму сосчитать не знаю. Но не уверен, что метод правилен.

$ \begin{array}{ccссссс} 0 & 1 & 2 & 3 & 4 & ... & 9 \\ 0 & 1 & 3 & 6 & 10 & ... & 45 \\ 0 & 1 & 4 & 10 & 20 & ... & 165 \\ 0 & 1 & 5 & 15 & 35 & ... & 495 \end{array}$

Смысл таков, что например для $n=5$, количество чисел, удовлетворяющие требованию, с цифрой 9 в старшей позиции $1+0+0$, для 8 это $2+1+1$, для 7 это $3+3+4$ и так далее (присутствует сдвиг по первой строке). Ну и думаю принцип заполнения матрицы тоже понятен. В зависимости от размерности задачи, нужно считать сумму всех элементов первых $(n-2)$ строк матрицы.
4.
a) $C^{n+r-1}_n$
b) $C^{n-1}_{n-r}$
5.
a) $ \frac{4(n-5+1)}{C^{4n}_{5}}$
б) $ \frac{12}{(4n-2)(4n-3)(4n-4)}$
в) $ \frac{C^{4}_{2}C^{4}_{3}C^{n}_{2}}{C^{4n}_{5}}$
г) $ \frac{4C^{n}_{5}}{C^{4n}_{5}}$
д) $ \frac{(n-5+1)4^5}{C^{4n}_{5}}$
е) $ \frac{30}{(4n-2)(4n-3)(4n-4)}$
ж) $ \frac{C^{n}_{2}C^{4}_{2}C^{4}_{2}}{C^{4n}_{4}}$
з) $ \frac{4^4C^{n}_{4}C^{4}_{2}}{C^{4n}_{5}}$

Спасибо!

[--mS--]

Можно, я на бегу пока очевидные вещи отмечу только?
2 и 4 - да, 5 - если забыть, что искать требовалось числа вариантов, а не вероятности, то (а), (г), (д) - верно, остальные ((б), (в), (е), (ж) и (з)) - нет. Например, в (в) правильно будет $\frac{C_4^2C_4^3 A_n^2}{C_{4n}^5}$, где $A_n^2=n(n-1)$ - число размещений, а не сочетаний. Это вдвое больше.

[Klekota]

Цитата:

--mS--

Спасибо за подсказку. Я теперь переосмыслил ответы.
ЗЫ: В условии просят найти частоты))
ЗЫ2: Я думаю, что Ж правильное, если нужно выбирать 4 карты.
Ответы на #5:
Б $\frac{ A^{n}_{2}C^{4}_{4}C^{4}_{1}}{C^{4n}_{5}}$
Е $\frac{ A^{n}_{3}C^{4}_{3}C^{4}_{1}C^{4}_{1}}{2!C^{4n}_{5}}$
З $\frac{ A^{n}_{4}C^{4}_{2}C^{4}_{1}C^{4}_{1}C^{4}_{1}}{3!C^{4n}_{5}}$

[--mS--]

Klekota в сообщении #483260 писал(а):

ЗЫ: В условии просят найти частоты))

Нет, в условии требуется упорядочить варианты по частоте их появления. Частота - это как часто они появляются среди данных (одних и тех же) наборов. Т.е. в скольких случаях.

Klekota в сообщении #483260 писал(а):

ЗЫ2: Я думаю, что Ж правильное, если нужно выбирать 4 карты.

Выбирается 5 карт, а не 4.
Б верно.

Klekota в сообщении #483260 писал(а):

Ответы на #5:
Е $\frac{ A^{n}_{3}C^{4}_{3}C^{4}_{1}C^{4}_{1}}{2!C^{4n}_{5}}$

Найдена вероятность получить три карты с одним номером, и две с другими и разными. Я понимаю условие иначе: ровно три карты с одним номером, и не важно, какие остальные. Возможно, Вы правы и условие следует понимать именно так. Тогда последний ответ к (З) тоже верен.

[--mS--]

Klekota в сообщении #483200 писал(а):

3. Я построил матрицу, которая похожа на треугольник биномиальных коэффициентов, но как сумму сосчитать не знаю. Но не уверен, что метод правилен.

Воспользуйтесь такой простой идеей: каждое подходящее число содержит на первых позициях сколько-то (возможно, ноль) единиц. Потом сколько-то (может, нисколько) двоек. Потом троек и т.д. И одно такое подходящее число отличается от другого тем, сколько в начале единиц, потом двоек, троек и т.д. При этом общее число единиц, двоек, троек и т.д. в числе должно быть $n$. Это в точности задача о размещении неразличимых частиц по ячейкам (или о сочетаниях с повторениями). Ответ $C_{n+9-1}^n$.

[Klekota]

Спасибо!

[ewert]

--mS-- в сообщении #483537 писал(а):

При этом общее число единиц, двоек, троек и т.д. в числе должно быть $n$.

Не больше, чем $n$, так что придётся ещё просуммировать $C_{k+9-1}^k$ по всем $k\leqslant n$. Но можно и не суммировать, а просто добавить в число допустимых цифирок ещё и нолик, не забыв потом вычесть единственную запрещённую комбинацию, состоящую только из нулей: $C_{n+10-1}^n-1$.

[--mS--]

Ваша правда :) Показалось, что в условии спрашивается про $n$-значные числа. А там про не более чем :)