Question

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

Answer 1

Данную задачу можно решать обобщённо, за вычетом лишних вариантов

А можно – методом частичных сумм,
рассматривая все возможные комбинации:

[ 7f ] все кружки одного цвета f - 5 вариантов
[ 1f + 6g ] одна кружка цвета f и остальные 6 – цвета g, уже 20 вариантов.
[ 2f + 5g ] две кружки цвета f и остальные 5 – цвета g, 3*20=60 вариантов.
[ 3f + 4g ] три кружки цвета f и остальные 4 – цвета g, 5*20=100 вариантов.
[ 1f + 1g + 5h ] – 3*80 = 240 вариантов.
[ 1f + 2g + 4h ] – 15*80 = 1200 вариантов.
[ 1f + 3g + 3h ] – 20*80 = 1600 вариантов.
[ 2f + 2g + 3h ] – 14*80 = 1120 вариантов.
[ 1f + 1g + 1h + 4i ] - подсчёт довольно сложный.
[ 1f + 1g + 2h + 3i ] - подсчёт слишком сложный.
[ 1f + 2g + 2h + 2i ] - подсчёт неоправданно сложный.
[ 1f + 1g + 1h + 1i + 3j ] - подсчёт запредельно сложный.
[ 1f + 1g + 1h + 2i + 2j ] - ...

Такой оказывается значительно более сложным, но, тем не менее, он интересен просто как самопроверка достоверности обобщённого Хоть и нет смысла доводить его до конца, и даже раскрывать все тонкости его вычисления (если вам непонятны подсчёты частичных сумм вариантов, то объяснение было бы очень длинным), всё же, этот вариант подсчёта показывает, что искомое число вариантов должно быть, видимо, порядка 10 000 (ну т.е. точно не 100, и точно не миллион).

Но в силу сложноси такого подхода, намного удобнее будет обойтись именно вариантом подсчёта через обобщённый подход, за вычетом лишних вариантов. Приступим.

Вообще говоря, понятно, что на каждом блюдце может оказаться кружка 5 разных цветов. Ну, тогда поставив первую кружку – 5 вариантов, ставим вторую – у нас на каждый из пяти первых вариантов, оказывается по пять новых, значит поставить две кружки – уже 25 вариантов. Ставим третью кружку и у нас на каждый из 25-ти предыдущих вариантов, оказывается по пять новых, значит поставить три кружки – уже 125 вариантов и т.д.

Всего, предварительный расчёт даёт:    $5^7$    вариантов.

Но нужно понимать, что при полном переборе, почти для каждого расположения – найдётся его 6 дублёров, образующихся при повороте стола. Почти все, а именно: все, кроме пяти одноцветных расстановок.

Итак, будет    $5$    одноцветных расстановок и    $5^7-5$    разноцветных расстановок.

Среди общего числа разноцветных расстановок будет по 7 совпадающих расстановок (на каждую уникальную по 6 дублёров), а поэтому общее число разноцветных расстановок нужно разделить на 7.

Тогда истинное число уникальных
разноцветных расстановок будет равно:

$\frac{ 5^7 - 5 }{7} = 5 \cdot \frac{ 5^6 - 1 }{7} = 5 \cdot \frac{ ( 5^3 - 1 ) ( 5^3 + 1 ) }{7} = 5 \cdot \frac{ 124 \cdot 126 }{7} = \\\\ = 5 \cdot 124 \cdot 18 = 90 \cdot 124 = ( 100 - 10 ) \cdot 124 = 12 \ 400 - 1 \ 240 = 11 \ 160 \ ;$

*** обратите внимание, то что выражение    $(5^7 - 5)$     разделилось на 7 – это довольно удивительно и довольно слолжно доказывается. Вообще-то это частный случай одной из легендарных теорем Ферма.

А общее число все расстановок,
и одноцветных и разноцветных составит:  11 160 + 5 = 11 165.

О т в е т :  11 165 вариантов.