Вход через социальные сети

  • 7страниц:
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 29.10.2015, 10:09
    0 up down
    Сообщение

    Число разбиений числа n на k слагаемых равно числу разбиений числа n с максимальным слагаемым, равным k.

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

  • 29.10.2015, 10:18
    0 up down
    Сообщение

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

  • 29.10.2015, 17:07
    0 up down
    Сообщение

    Забыл уточнить, что рассматриваются наборы из натуральных чисел.

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

  • 30.10.2015, 11:06
    0 up down
    Сообщение

    Vlardenir в 29.10.2015, 04:21 написал(а): link
    2x+3y+4z = 306 при x, y, z ≠ 0

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

     

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

    А с НОК-ом не поняла.

  • 31.10.2015, 19:21
    0 up down
    Сообщение

    Swetlana: "С НОК-ом не поняла."

    Так как с комбинаторикой знаком, лишь поверхностно, а будет правильно сказать, что не знаком, то задачку решал исключительно из своих соображений.

    Получилось вот что:

    Найти количество решений в целых числах у уравнения:

    2x+3y+4z = 306 при x, y, z ≠ 0

     

    По условию x, y, z  ≠ 0 значит хотя бы по одному разу числа 2, 3, 4  входят в уравнение. Просумируем их 2+3+4 = 9 и вычтем из 306. Теперь будем иметь дело с числом 297.

    Так как необходимо учесть все комбинации чисел 2, 3 и 4, то ищем НОК (наименьшее общее кратное) трёх чисел. Очевидно, что НОК(2, 3, 4) = 12.

    Теперь можно найти все комбинации сумм для 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 комбинаций.

    Далее, воспользуемся модульностью по НОК(2, 3, 4):

    297 mod 12 = 9, т.е. получаем целочисленный остаток от деления на 12, и нужно найти комбинации для числа 9:

    3+3+3

    2+2+2+3

    2+3+4

    Имеем 3 комбинации.

    Далее, вычитаем остаток 9 из 297 и делим на 12

    (297-9)/12 = 24

    Теперь остаётся подсчитать общее количество комбинаций чисел 2, 3, 4 для заданного уравнения:

     

    Как-то так и получился частный случай с НОК( ).

     

     

    Сообщение было отредактировано Vlardenir в 31.10.2015, 19:55.

     

    Сообщение было отредактировано Vlardenir в 31.10.2015, 20:21.


  • 30.10.2015, 13:55
    0 up down
    Сообщение

    Ну что за ужас такой: набрала почти полностью решение в техе с рядами и всеми делами, потом случайно куда-то нажала... Щас уже пора на работу. 

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

    Сообщение было отредактировано Swetlana в 30.10.2015, 14:55.


  • 30.10.2015, 18:19
    0 up down
    Сообщение

    Постановка задачи в общем виде, разбиения коммутативные, т.е 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 в 30.10.2015, 19:19.


  • 30.10.2015, 18:48
    0 up down
    Сообщение

    Двойку можно взять ни разу (одним способом), можно одну, две двойки и т.д. Запишем следующий ряд:

    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}. 

    А ещё есть интегральная теорема Коши, но не помню.

  • 30.10.2015, 20:09
    0 up down
    Сообщение

    Vlardenir в 30.10.2015, 14:48 написал(а): link
    Найти количество решений в целых числах у уравнения: 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. 

  • 30.10.2015, 20:11
    0 up down
    Сообщение

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

  • 7страниц:
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7