Сколькими способами можно расставить двухтомники 10 различных авторов на полке так, чтобы никакие две книги одного автора не стояли рядом.

задан 29 Апр '15 23:12

Если из общего числа способов 20! вычесть способы когда двухтомники стоят рядом (10!*2!). Будет ли это верным?

(29 Апр '15 23:13) 587896

@587896: нет, здесь сложнее. Числу $%10!\cdot2!$% ничего не соответствует. Это количество способов расставить в каком-то порядке "сложенные" двухтомники, умноженное на 2. Но ведь вычитать надо все способы, где хотя бы какие-то книги одного автора стоят рядом -- их намного больше. Например, два тома Пушкина где-то в середине, а порядок остальных томов может быть "хаотическим".

(29 Апр '15 23:19) falcao

Да не учел... Помогите, пожалуйста, решить.

(29 Апр '15 23:39) 587896
10|600 символов нужно символов осталось
1

Решим задачу для общего случая, когда имеется $%n$% двухтомников.

Общее число способов расставить $%2n$% томов на полке равно $%(2n)!$%. Из него надо вычесть число "плохих" способов, когда какие-то два тома одного автора стоят рядом. Введём обозначение $%A_i$% для $%1\le i\le n$%: это множество способов расставить тома так, что у $%i$%-го автора оба тома стоят рядом. Нас интересует число $%|A_1\cup\cdots\cup A_n|$%. Чтобы его найти, применим формулу включений и исключений.

В "свёрнутом" виде правая часть формулы имеет вид $$\sum\limits_{s=1}^n\sum\limits_{i_1 < \cdots < i_s}(-1)^{s-1}|A_{i_1}\ldots A_{i_s}|.$$ Для заданного набора индексов $%i_1 < \cdots < i_s$% найдём значение величины $%|A_{i_1}\ldots A_{i_s}|$%. У нас тома авторов с номерами $%i_1$%, ... , $%i_s$% стоят рядом, поэтому их можно "склеить". Вместо $%2n$% томов станет $%2n-s$% "томов" с учётом этих "склеек". Их можно расположить на полке $%(2n-s)!$% способами. Также надо домножить на $%2^s$% с учётом того, что в каждой "склеенной" паре тома могут идти в одном или другом порядке. Таким образом, $%|A_{i_1}\ldots A_{i_s}|=2^s(2n-s)!$%.

Заметим, что число слагаемых во "внутренней" сумме для заданного $%s$% равно $%C_n^s$%. Вычитая из общего количества $%(2n)!$% нашу сумму, мы будем иметь следующее: $$(2n)!+\sum\limits_{s=1}^n(-2)^s(2n-s)!C_n^s.$$ Можно первое слагаемое считать частью дальнейшей суммы, если суммировать по $%s$% от нуля.

Это и есть общий ответ. При $%n=1,2,3$% эта формула даёт значения 0, 8, 240. Для числа $%n=10$% из условия получается $%871804170613555200$%.

ссылка

отвечен 30 Апр '15 2:16

изменен 30 Апр '15 17:24

То ли я условие не понял, то ли вообще не понятно что вы посчитали.)

В самом простом случае, при $%n=2$%, имеем 2 двухтомника двух авторов, т.е. 4 книжки, которые можем расставить только двумя способами: 1212 или 2121. Откуда 8?

(30 Апр '15 16:32) Isaev
1

@Isaev: пусть есть двухтомники Пушкина и Лермонтова. Тогда у нас есть не ПЛПЛ и ЛПЛП, а П_1Л_1П_2Л_2, П_2Л_1П_1Л_2, и так далее. За счёт различия первого и второго тома, получается в 4 раза больше случаев.

(30 Апр '15 16:37) falcao

@falcao, логично

(30 Апр '15 17:12) Isaev
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×967

задан
29 Апр '15 23:12

показан
1274 раза

обновлен
30 Апр '15 17:24

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru