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

Swetlana · Сообщение **Swetlana** » 05 ноя 2015, 09:10

Володиславир, просто не поняла, о чём вы спрашиваете. Гафу итегез))
Конечно, вычитаем 9 и для 297 решаем задачу в общем виде. Получается 1875.

Swetlana · Сообщение **Swetlana** » 05 ноя 2015, 09:11

Володиславир писал(а):Source of the post То есть, в общем случае, этот результат верен для разбиений на единицы и с коэффициентом α?

α > 1.

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

Всё-таки НОК не даёт покоя
Так как большинство странных мыслей приходит ночью, то за правильность не особо ручаюсь.
Наверное с помощью НОК(a,b) можно выразить количество разбиений числа n, суммами чисел а и b.
$1+\left \lfloor n/HOK(a,b) \right \rfloor$ при n - чётное;
$1+\left \lfloor (n-a)/HOK(a,b) \right \rfloor$ при n - не чётное
Но при условиях достаточно больших n и $$a< b$$

Достаточно большое n означает, что оно превышает последнее не выражаемое число суммой чисел a и b.
Так для пары 5 и 7, последним не выражаемым числом будет 23.

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

Нашёл формулы для последних не выражаемых чисел, суммами чисел a и b. Обозначу это число как $\bg_white \nu _{max}\left ( a,b \right )$ Здесь так же два случая:
1) Когда а и b одновременно не чётные числа или одно число чётно, другое не чётно. Тогда формула выглядит:
$\bg_white \nu _{max}\left ( a,b \right )= b(a-1)-a = a(b-1)-b$
2) Когда а и b одновременно чётные числа:
$\bg_white \nu _{max}\left ( a,b \right )= b(a/2-1)-a = a(b/2-1)-b$
Тогда дополнительные (все?) не выражаемые числа можно найти простым последовательным вычитанием из $\bg_white \nu _{max}(a,b)$ комбинаций чисел а и b.

Люди, ау! Кто-нить, может я тут велосипед изобретаю, увлекательно конечно, но может есть где об этом прочитать? Плюс время сэкономиться.

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

Эх, никто так и не подсказал, а литература-то есть.
Г.Эндрюс "Теория разбиений". (1982)

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

Swetlana писал(а):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.

А можно ли получить формулу в закрытом виде?

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

Swetlana писал(а):Source of the post \sum_{i=0}^{\left \lfloor\frac{n}{6} \right \rfloor }(1+\left \lfloor \frac{n-6i}{4} \right \rfloor) Хорошо бы её преобразовать и упростить, но пока не соображу, как.

Упростить не удасться. Данная форма, видимо, наиболее простая.
А перевести ряд в закрытую форму, т.е. в обычную формулу можно. Выкладки приводить не буду, если заинтересуетесь как получилось дайте знать.
Результат в общем виде следующий:
$\sum_{i=0}^{\left \lfloor n/a \right \rfloor}(1+\left \lfloor (n-ai)/k \right \rfloor) =\sum_{i=0}^{\left \lfloor n/a \right \rfloor}(1+\left \lfloor (mod(n,a)+ai)/k \right \rfloor)$

$r_{b}=mod(n,a);$
$r_{e}=mod(n,k);$
$\sum_{i=0}^{\left \lfloor n/a \right \rfloor}(1+\left \lfloor \frac{mod(n,a)+ai}{k} \right \rfloor) = \frac{\left \lfloor n/a \right \rfloor+1}{k}\left ( \frac{a\left \lfloor n/a \right \rfloor}{2} + mod(n,a)\right )-\frac{k-1}{2}\left \lfloor n/ak \right \rfloor-\frac{r_{b}(r_{b}+1)}{2k}+\frac{r_{e}(r_{e}-1)}{2k}+\left \lfloor n/a \right \rfloor+1$

grigoriy · Сообщение **grigoriy** » 26 дек 2015, 18:13

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

grigoriy писал(а):Source of the post ...

"Нам помогут только массовые расстрелы" (с)

Может заглянет.
Однако, исправил формулу на неправильную, но сейчас обнаружил, что и прежняя хоть и давала правильный результат по условиям задачи, но в общем случае тоже не верна. К тому же, сама метода вывода, мало содержательна по отношению к комбинаторике.
В общем, я в депрессии.

yourdomain.com