Комбинаторика

eqvinoks · Сообщение **eqvinoks** » 12 ноя 2016, 13:21

Группа, состоящая из 27 человек, пишет контрольную работу из 3 вариантов (каждый вариант по 9 человек). Сколькими способами можно выбрать 5 человек из группы так, чтобы среди них оказались писавшие все три варианта?
У меня получилось так: первого (1 вариант) можно выбрать 9 способами, второго (2 вариант) 9 способами, третьего (3 вариант) 9 способами. Четвертого и пятого можно выбрать 24*23 способами. Итого ответ 9*9*9*24*23, верный? Или четвертого и пятого выбираем по числу сочетаний C(2)(25), тогда (9*9*9*24*23)/2? Еще есть идея, что первого можно выбрать же вообще 27 способами, но как быть с остальными?

ARRY · Сообщение **ARRY** » 14 ноя 2016, 04:47

eqvinoks, нет, Ваш подсчёт неверен. Ну сами оцените число способов, найденное Вами: $9\cdot 9\cdot 9\cdot 24\cdot 23=402408$ . А между
тем полное число способов выбрать $$5$$

человек из $$27$$

всего $C_{27}^5=80730$ . Явно меньше. Ваша ошибка из-за того, что Вы пытались
расставить элементы набора по местам. Вы применили комбинаторный принцип умножения, используемый при вычислении количества упорядоченных
наборов - размещений.
В Вашей же задаче мы ищем число сочетаний - неупорядоченных наборов (нам же неважно, кто будет на первом месте, кто на втором и т.д.).
Начнём с того, что наше множество из $$27$$

элементов представляет собой $$3$$

непересекающихся подмножества из $$9$$

элементов каждое. Нам нужно выбрать набор из $$5$$

элементов такой, чтобы в него входил хотя бы один элемент из каждого подмножества.
Число $$5$$

может быть представлено в виде суммы трёх натуральных слагаемых двумя способами (с точностью до порядка слагаемых:
$$5=3+1+1$$

и

.
А вот теперь порядок слагаемых учтём, считая число способов выбора подмножеств в каждом из этих двух случаев и число способов выбора элементов
в каждом из подмножеств. Искомое число способов равно $C_3^1\cdot C_9^3\cdot C_9^1\cdot C_9^1+C_3^1\cdot C_9^2\cdot C_9^2\cdot C_9^1=55404$ .
Ну как-то так.

Самоед

eqvinoks писал(а):Source of the post Группа, состоящая из 27 человек, пишет контрольную работу из 3 вариантов (каждый вариант по 9 человек). Сколькими способами можно выбрать 5 человек из группы так, чтобы среди них оказались писавшие все три варианта?

Задача составлена безобразно.
1) Контрольную работу выполняют люди, а не группа. Иначе можно понять, что газету пишет группа №1, журнал пишет группа №2, книгу пишет группа №3.
2) В требовании задачи записано дополнительное условие: 5 человек принимали участие в написании газеты, журнала и книги одновременно (писавшие все три варианта).
3) "Способ выбора" - не определенное в математике понятие.

ARRY писал(а):Source of the post В Вашей же задаче мы ищем число сочетаний - неупорядоченных наборов (нам же неважно, кто будет на первом месте, кто на втором и т.д.). Начнём с того, что наше множество из элементов представляет собой непересекающихся подмножества из элементов каждое. Нам нужно выбрать набор из элементов такой, чтобы в него входил хотя бы один элемент из каждого подмножества.

Вот понятная задача, в интерпретации ARRI.

yourdomain.com