Сколько вариантов окраски

[stanislav55]

Имеем 126 квадратов. Их надо раскрасить в 4 цвета (красный,синий, жёлтый, зеленый) В один цвет нельзя окрашивать более 41 квадрата где бы они не стояли. Сколько вариантов окраски.

[NetSpace]

комбинаторика...эх...

[Аватар]

Там же бешенные числа )) Можно попытаться динамическим программированием (+ длинная арифметика, очень длинная).
V(n) - число вариантов для n квадратов
V(1) = 4

Для n<41: V(n+1) = V(n)*4

Для 41<=n<82: V(n+1) = V(n)*4 - (C(41,n)*3^(n-41))*4
где C(41,n) = n!/41!/(n-41)! (может и ошибся, идея - вычесть те варианты где перевалило за 41 у одного из цветов)

Для 82<=n<123 уже два цвета может быть по 41, для 123<=n - 3 цвета, лень формулу выводить да и смысла не вижу ))

[Serge_Bliznykov]

согласен.
в "лоб" перебором не решишь.
если порядок расположения имеет значение, тогда общее число вариантов раскраски 4^126 ~ 7.8E75 (75значное число)
поэтому перебирать все варианты - это не выход. нужно думать над алгоритмом/формулой.

[Аватар]

С другой стороны там всего 10660 решений целочисленного уравнения:
a+b+c+d=126 где 3<=a,b,c,d<=41
для каждого решения посчитать число вариантов, а это реально, и сложить. И та же длинная арифметика

[stanislav55]

Сообщение от Serge_Bliznykov

согласен.
в "лоб" перебором не решишь.
если порядок расположения имеет значение, тогда общее число вариантов раскраски 4^126 ~ 7.8E75 (75значное число)
поэтому перебирать все варианты - это не выход. нужно думать над алгоритмом/формулой.

Квадраты расположены на одной линии.Значит имет.

[stanislav55]

Сообщение от Аватар

Там же бешенные числа )) Можно попытаться динамическим программированием (+ длинная арифметика, очень длинная).
V(n) - число вариантов для n квадратов
V(1) = 4

Для n<41: V(n+1) = V(n)*4

Для 41<=n<82: V(n+1) = V(n)*4 - (C(41,n)*3^(n-41))*4
где C(41,n) = n!/41!/(n-41)! (может и ошибся, идея - вычесть те варианты где перевалило за 41 у одного из цветов)

Для 82<=n<123 уже два цвета может быть по 41, для 123<=n - 3 цвета, stanislav55 ))

лень формулу выводить да и смысла не вижу


Что надо чтобы было не лень

[stanislav55]

Сообщение от Serge_Bliznykov

согласен.
в "лоб" перебором не решишь.
если порядок расположения имеет значение, тогда общее число вариантов раскраски 4^126 ~ 7.8E75 (75значное число)
поэтому перебирать все варианты - это не выход. нужно думать над алгоритмом/формулой.

свыше перечисленами условиями может быть число вариантов меньше чем 4^125

[Dekay]

Сообщение от Аватар

a+b+c+d=126 где 3<=a,b,c,d<=41

Ога.
а потом 126!/a!/b!/c!/d!
Интересно, а есть ли что-то получше?
Я дык сходу не знаю

[Аватар]

а потом 126!/a!/b!/c!/d!

Потом чуть не так, например на 4! еще умножить для разных a,b,c,d. Для совпадающих подумать немножко еще нужно. Но это же не перебор, а расчет просто. Динамическим программированием может и быстрей, но там еще формулы нужно придумать. И тоже считать большие факториалы ))