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

Swetlana · Сообщение **Swetlana** » 30 окт 2015, 17:58

В любом разбиении чётное число троек, 0, 2, ..., 102. Если троек 102, то разбиение ровно одно.
Если троек 0, то набираем только единицами и двойками:
$$2x+4z=306; x+2z=153.$$

Задача о разбиении на единицы и двойки решена с эффектным к-том $a_{n}=\left \lfloor \frac{n}{2} \right \rfloor+1$ (см. в конце страницы "Задача о коммутативном разложении"):
http://www.genfunc.ru/theory/intro/
Отсюда для количества троек $$2i, i=0, ..., 50$$

количество разбиений равно... формула-инвалид. Что-то мне сегодня не везёт.

Swetlana · Сообщение **Swetlana** » 30 окт 2015, 18:50

Так. Снова да ладом.
В любом разбиении чётное число троек, 0, 2, ..., 102. Если троек 102, то разбиение ровно одно. Один на ум пошло.
Если троек $$2i, i=0...50$$

, то набираем единицами и двойками число $\frac{306-6i}{2}=153-3i.$
Количество способов набрать это число равно $a_{153-3i}=\left \lfloor \frac{153-3i}{2} \right \rfloor+1.$
Окончательно, количество разбиений для сабжевой задачи (если x, y, z одновременно не могут быть равны 0) равно
$1+\sum_{i=0}^{50}(\left \lfloor \frac{153-3i}{2} \right \rfloor+1).$
Это уже можно вычислить... с помощью программы

Swetlana · Сообщение **Swetlana** » 30 окт 2015, 19:58

Swetlana · Сообщение **Swetlana** » 30 окт 2015, 20:56

Разбить магическое число 306 на единицы и двойки можно 154 способами (это получено чрез производящие функции).
На двойки и четвёрки то же магическое число разбивается 77 способами, т.к. количество четвёрок меняется в пределах от 0 до 76.
$77\times 2=154.$
Сижу и пытаюсь вспомнить: а зачем мне были нужны производящие функции?

Swetlana · Сообщение **Swetlana** » 30 окт 2015, 21:05

Ещё одна мысль, ещё более нехорошая: задача решается тройным циклом.
Всем спокойной ночи, приятных кошмаров
ЗЫ. Нижайше прошу модератора удалить два моих последних поста.

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

1. Разбиения без повторений;
2. Да, сколько существует последовательностей $\left ( \lambda _{1}, .. ,\lambda _{k} \right )_{j}$ таких, что $\bigcup_{j=1}^{q}\left ( \sum_{i=1}^{k} a_{i}\lambda _{ij}=n\right )=q$
3. В задаче: Сколько существует последовательностей $\left ( \lambda _{1} ,\lambda _{2},\lambda _{3}\right )$ таких, что $2\lambda _{1}+ 3\lambda _{2}+ 4\lambda _{3} = n$
4. Возник вопрос: Как соотносится общее количество последовательностей q с последовательностями, которые у Вас обозначены как $\left ( a_{1}, a_{2}, .. \right )$ ?

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

Swetlana писал(а):Source of the post Сижу и пытаюсь вспомнить: а зачем мне были нужны производящие функции? scratch_one-s_head

Может с помощью них решить задачу?

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

Swetlana писал(а):Source of the post
Vlardenir: "Найти количество решений в целых числах у уравнения: 2x+3y+4z = 306 при x, y, z ≠ 0 По условию x, y, z ≠ 0 значит хотя бы по одному разу числа 2, 3, 4 входят в уравнение. Просумируем их 2+3+4 = 9 и вычтем из 306. Теперь будем иметь дело с числом 297"
. Проверьте своё решение для небольших n. Например, n = 6. Первый шаг: 6-9=-3.

n = 6 просто не подходит к условию задачи.

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

Всё более вникая в суть вопроса, становится понятным, что нужно привлекать целочисленное деление (div) и вычисление целочисленного остатка (mod).
А так же ввести функцию: $\mu \delta \left ( x, y \right ) = \left\{\begin{matrix} 0 , \left ( x \mod\ y=m \right )\\ 1 ,\left ( x\mod\ y=0 \right ) & \end{matrix}\right.$

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 06:05

Ну тогда проверьте для чего подходит

Так хватит дурачиться, стрелять из пушки по воробьям.
Задача №1. Коммутативное разложение на двойки и единицы.
Сколько существует последовательностей $(\lambda _1,\lambda _2)$ таких, что $\lambda _1 + 2\lambda _2=n?$
Решение. Количество двоек в разбиении однозначно определяет разбиение; количество двоек меняется в диапазоне от 0... $\left \lfloor \frac{n}{2} \right \rfloor$ .
Отсюда $a_{n}=\left \lfloor \frac{n}{2} \right \rfloor+1$ . Доказательство закончено.
офтоп
эффектный коэффициент... ой, мамочки... ну зачем надо было это решать производящими функциями?

yourdomain.com