Задача о лапах и общая постановка вопроса

[Володиславир]

Source of the post Не поняла вашу формулу с НОКом, проверить ваше решение не могу.

Само собою не поняли, т.к. её нету. Именно её (формулу) и стал искать для произвольных , для начала для троек , потом для четвёрок и далее может общий случай станет проклёвываться. Но у меня проблемы с самой записью того, что приходит в голову.
А идея с НОКом, подсчитать количество комбинаций в меньшей части, чем НОК по сравнению с n является, а потом скомбинировать части. Кстати, скомбинировал не правильно - получил все комбинации с повторениями.

[Володиславир]

Source of the post Количество коммутативных разбиений на двойки, тройки, четвёрки для любого натурального n, n\geq 2 равно a_{n} = \sum_{i=0}^{\left \lfloor\frac{n}{6} \right \rfloor }(1+\left \lfloor \frac{n-6i}{4} \right \rfloor) для чётного n и a_{n} = \sum_{i=0}^{\left \lfloor\frac{n-3}{6} \right \rfloor }(1+\left \lfloor \frac{n-3-6i}{4} \right \rfloor) для нечётного n.

Симпатично!

[Володиславир]

Давайте возьмём n = 24.
24 = 12 + 12 , число 12 содержит 7 комбинаций сумм (2, 3, 4). Т.е. нужно скомбинировать без повторений 7 с 7.
Каждую отдельную комбинацию для числа 12 пронумеруем с 1 до 7.
1:  2+2+2+2+2+2
2:  4+2+2+2+2
3:  4+4+2+2
4:  4+4+4
5:  3+3+3+3
6:  3+3+2+2+2
7:  3+3+4+2
Скомбинируем вручную между собой 7 комбинаций для первого числа 12 с 7-ю комбинациями для второго числа 12 :
{1,1} {1,2} {1,3} {1,4} {1,5} {1,6} {1,7}
{2,2} {2,3} {2,4} {2,5} {2,6} {2,7}
{3,3} {3,4} {3,5} {3,6} {3,7}
{4,4} {4,5} {4,6} {4,7}
{5,5} {5,6} {5,7}
{6,6} {6,7}
{7,7}
Так {2,3} будет представлять сумму (4+2+2+2+2)+(4+4+2+2) = 24
Варианты такие как {3,2} отбрасываем, т.к. фактически это есть повторение.
Итак, для числа 24 имеем 28 комбинаций сумм чисел (2,3,4)
А для числа 36 будет 84 комбинации.
По сути комбинирования, в результате получаются фигурные числа порядка 3, т.е.
28 - это 7-е треугольное число 
84 - это 7-е тетраэдральное число
Треугольные числа представляются формулой:
Тетраэдральные числа ищутся по формуле:
В общем случае k-симплексное q-е число находится:
Для задачи про лапы имеем:  комбинаций.
 

[Swetlana]

Source of the post Итак, для числа 24 имеем 28 комбинаций сумм чисел (2,3,4)

Для числа 24 таки 19 разбиений.

[Swetlana]

Чёто неудобно на печать решения вывела.
Проверяйте по последнему столбику с двойкой - там количество двоек пробегает все возможные значения от 0 до 12.

[Володиславир]

Мммда...
{3,5} = {7,7} ; {3,7} = {4,6} ; {2,4} = {3,3}
{2,5} = {6,7} ; {2,7} = {3,6} ; {1,4} = {2,3}
{1,5} = {6,6} ; {1,7} = {2,6} ; {1,3} = {2,2}
И как так не заметил?

[Swetlana]

Можно очень грубые оценки сверху делать, с помощью килькулятора. Должны получить 306 лап. Если зафиксируем тройки, то задача сводится к набору 1 и 2, формула  Самое большое n, какое может быть, 306. Получаем 154. Количество троек меняется от 0 до 102, берём по максимуму: 102*154 = 15708. Прилично так ошиблись. Но всё же видно, что не миллион.
А ещё можно просто брать и в хорошую формулу подставлять))
 

[Swetlana]

Ну, вот. И сама ошиблась в два раза. Для набора единицами и двойками надо 306 делить на 2 - 153. По формуле - 77. 77*102 = 7854. А на самом деле - 2028. Порядок тот же.

[Swetlana]

Сколько влезло в экран ноутбука.

[Володиславир]

Понял, что комбинировать последовательности сумм плохо.
Нужно искать количество комбинаций сначала из двух чисел. Но тогда при произвольно заданном n может не быть решений или количество комбинаций будет равно нулю.
В связи с этим нужно как-то проверять существование решения.