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

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

Всех приветствую!
История вопроса сложилась случайно. В одном из испанских журналов попалась задачка: «В зоопарке есть животные с четыремя, шестью и восьмью лапами. Всего лап 612. Найти количество животных если количество животных разных видов одинаковое.» То есть нужно решить уравнение 2x+3x+4x = 306
Задачка, само-собою, элементарная, поэтому задался вопросом, - а сколько решений имеет задача, если количество животных разных видов разное?
2x+3y+4z = 306 при x, y, z ≠ 0
Решил. Но при решении обратил внимание, что хорошо бы найти общую формулу для количества комбинаций таких сумм:
НОК(2, 3, 4) = 12
2+2+2+2+2+2
4+2+2+2+2
4+4+2+2
4+4+4
3+3+3+3
3+3+2+2+2
3+3+4+2
Имеем 7 комбинаций.
Или в общем виде:
$\bigcup \left ( \sum aixj = HOK(a1, .. ,ak) \right )=q$ c заданными ai ≠ aj i, j ∈ {1, .., k}
Далее начинаются существенные трудности. Может кто подскажет решение или хотя бы как подступиться к возникшему вопросу.

Swetlana · Сообщение **Swetlana** » 29 окт 2015, 07:09

Число разбиений числа $$n$$

на

слагаемых равно числу разбиений числа $$n$$

с максимальным слагаемым, равным $$k$$

.
Посмотрите В. Липского "Комбинаторика для программиста" (на рутрекере пдф хорошего качества), там в первой главе эти вопросы рассматриваются.

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

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

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

Забыл уточнить, что рассматриваются наборы из натуральных чисел.
А так же имеется обобщение: вместо НОК( ) любое натуральное число. Но тогда возможно q=0, т.е. ни одной комбинации может не найтись.

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

Володиславир писал(а):Source of the post 2x+3y+4z = 306 при x, y, z ≠ 0

Производящая функция в общем-то стандартным способом пишется для случая, когда слагаемые, которыми набираем, могут ни разу не встретится в разбиении. Если из разложений для набора 2, 3, 4 убрать соответствующие этому случаю единичные слагаемые, то это всё равно, что из функций (сумм соответствующих рядов) вычесть 1. Как-то так. Число разбиений - коэффициент при $z^{306}$ , равен значению 306-й производной производящей функции в точке 0. Может, как-то попроще это всё можно сделать, отпишусь попозже. Только начала с производящими функциями разбираться

В общем виде эта задача решается с помощью производящей функции, равной произведению трёх производящих функций, соответствующих набору суммы только 2, 3, 4.
А с НОК-ом не поняла.

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

Ну что за ужас такой: набрала почти полностью решение в техе с рядами и всеми делами, потом случайно куда-то нажала... Щас уже пора на работу.
Поняла, что условие означает, что x,y,z одновременно не равны 0. Вроде это и так понятно. Не надо 1 вычитать, производящая ф-ция попроще получится.

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

Постановка задачи в общем виде, разбиения коммутативные, т.е 2+3 = 3+2.
Сколько существует последовательностей $(\lambda _{1},...,\lambda _{i},...,\lambda _{n})$ таких, что $\sum_{i=1}^{n}i\lambda _{i}=n?$
В сабжевой задаче число $$n$$

набирается только двойками, тройками, четвёрками.
Сколько существует последовательностей $(\lambda _{2},\lambda _{3},\lambda _{4})$ таких, что $2\lambda _{2}+3\lambda _{3}+4\lambda _{4}=n?$
Количество таких последовательностей для $$n$$

(количество разбиений числа $$n$$

на 2, 3, 4) обозначим $a_{n}$ .
Теперь для последовательности $(a_{1}, a_{2}, ...)$ найдём производящую функцию. Производить она будет эти самые $a_{1}, a_{2}, ...$ . При разложении производящей функции в степенной ряд к-т при $x^{n}$ будет в точности равен $a_{n}$ .

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

Двойку можно взять ни разу (одним способом), можно одну, две двойки и т.д. Запишем следующий ряд:
$1+x^{2}+x^{4}+...++x^{2\lambda _{i}}+...$ с суммой $\frac{1}{1-x^{2}}$ (это геометрическая прогрессия). Аналогично для тройки и четвёрки:
$1+x^{3}+x^{6}+...++x^{3\lambda _{i}}+... = \frac{1}{1-x^{3}}$
$1+x^{4}+x^{8}+...++x^{4\lambda _{i}}+... = \frac{1}{1-x^{4}}$
Производящая функция получается умножением этих рядов и равна $f(x)=\frac{1}{1-x^{2}}\frac{1}{1-x^{3}}\frac{1}{1-x^{4}}.$
Произведение этих трёх рядов (согласно определению умножения рядов) состоит из слагаемых вида $x^{2\lambda _{2}}x^{3\lambda _{3}}x^{4\lambda _{4}}$ , где $\lambda _{i}$ - номер члена, выбранного из ряда для i-го слагаемого, i = 2, 3, 4.
Коэффициент при $x _{n}$ равен числу последовательностей $(\lambda _{2},\lambda _{3},\lambda _{4})$ таких, что $2\lambda _{2}+3\lambda _{3}+4\lambda _{4}=n.$
Как найти этот коэффициент при $$n=306?$$

Можно производящую функцию разложить в сумму простых дробей, для каждой дроби записать ряд, сложить к-ты при $x^{n}.$
А ещё есть интегральная теорема Коши, но не помню.

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

Володиславир писал(а):Source of the post Найти количество решений в целых числах у уравнения: 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.$$

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

С суммой простейших дробей не получится, в знаменателе комплексные корни.

yourdomain.com