Найдите количество различных способов написания «1» в виде суммы дробей, каждый с «1» в качестве числителя и степенью «2» в качестве знаменателя

Question

Мне дано число n, и я должен найти число различных способов записи числа 1 в виде суммы n дробей, где каждая дробь имеет следующий формат:

• Числитель всегда равен 1.
• Знаменатель представляет собой степень 2 (например, 2 ^ 1, 2 ^ 2 и т. Д.).

Два метода записи 1 в виде суммы таких дробей НЕ различны, если они содержат одинаковые дроби.Например, скажем n=4.Один из способов записи 1 в виде суммы 4 дробей будет следующим: 1/2 + 1/4 + 1/8 + 1/8.Но написание его как 1/8 + 1/4 + 1/2 + 1/8 считается одинаковым (поскольку оно содержит точно такие же дроби, изменен только порядок) и, следовательно, НЕ различимо по сравнению с первым способом записи.Таким образом, для n=4 было бы только два способа записать 1 как сумму из 4 дробей.Первый будет 1/2 + 1/4 + 1/8 + 1/8 (упомянутый выше), а второй будет 1/4 + 1/4 + 1/4 + 1/4.Таким образом, результат будет 2.Границы n: 2 <= n <= 2000.

Я написал первые несколько на бумаге (для n=2, для n=3, для n=4 и еще несколько) и я подумал, что результаты являются частью последовательности Фибоначчи, поэтому я попыталсяно когда я отправил источник на сайт, он сказал, что это неправильно.У меня есть ощущение, что я должен использовать динамическое программирование, но я не уверен, как это реализовать.Любая помощь будет принята с благодарностью.Большое спасибо!

Answer 1

Я предлагаю вам начать с нескольких раундов 2048 .Но не вините меня, если не можете остановиться.

Ваш список слагаемых имеет наименьшее значение: 2 ^{- k} .Вы можете масштабировать всю сумму на 2 ^k , чтобы все числа были целыми числами, а на самом деле степени двойки.Это может облегчить размышление о проблеме.Теперь представьте сумму как операцию над двоичными числами, например

   0100
   0100
   0100
   0010
   0001
+  0001
= 10000

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

Итак, важным инвариантом здесь является то, что вы можете добавлять термины таким образом, чтобы они оставались отрицательными степенями двойки.Последовательность дополнений сформирует двоичное дерево, значение узла которого будет обозначено глубиной: корень имеет 1, следующий уровень 1/2, следующий 1/4 и т. Д.Каждый узел является либо листом с нулевыми дочерними элементами, либо внутренним узлом с двумя дочерними элементами.Вы интересуетесь бинарными деревьями с n листьями, но считаете деревья равными, если у них одинаковое количество листьев на каждом уровне.

Чтобы начать рекурсивно думать, как вы уходите от деревас n листьев к одному с n + 1 листьев?Вы добавляете пару детей к существующему листу.Давайте напишем код на Python.

def expansions(v):
    for i in range(len(v) - 1):
        if v[i]:
            yield tuple(x - 1 if j == i else x + 2 if j == i + 1 else x
                        for j, x in enumerate(v))
    yield v[:-1] + (v[-1] - 1, 2)  # start a new level

s = set([(1,)])  # start with a bare root
for n in range(1, 21):
    print("{:4d}: {:10d}".format(n, len(s)))
    s = set(y for x in s for y in expansions(x))

Затем перейдите к http://oeis.org/ и введите последовательность, которую вы получили сложным путем.Поиск будет отображать один хит, A002572 , который описывается как

Количество разбиений 1 на n степеней 1/2

Бинго,К сожалению, это не идет с закрытой формулой.Но есть список значений, предварительно рассчитанных для n = 2000.Итак, вот сценарий оболочки для определения результата для любого заданного n путем поиска в этом:

wget -qO- 'http://oeis.org/A002572/b002572.txt' | tail -n+${n:?} | head -n1 | cut -d' ' -f2

Если вы хотите более серьезный ответ, я предлагаю вам следовать приведенным ссылкамна OEIS.Или попытайтесь понять, что функция v, которая описывается как

v ( c , d ), являетсячисло разбиений d на целые положительные числа вида d = c + c ₁ + c ₂ +… + c _n , где c ₁ ≤ 2 c , c _{i + 1} ≤ 2 c _i .

и который используется для магического динамического программирования в Mathematica, Maple и Pari.

Так где же связь?Чтобы ответить на это, переключитесь с рассмотрения конечных узлов на рассмотрение внутренних узлов.Если у вас есть n конечных узлов, то у вас есть d = n -1 внутренних узлов. v (1, d ) рассчитывает способы упорядочения этих внутренних узлов, поделив количество внутренних узлов в соответствии со слоем.Вам нужен один внутренний узел в корне, если у вас нет n = 1, который не очень хорошо охватывается этим соображением.И каждый последующий слой может иметь по крайней мере ноль внутренних узлов и самое большее в два раза больше внутренних узлов по сравнению с предыдущим уровнем.

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

v(c, d) = sum(v(i, d-c) for i=1..2*c)

, посколькуесли d = c + c ₁ + c ₂ +… + c _m , тогда это соответствует d - c = c ₁ + c ₂ +… + c _m , поэтому вам нужны способы разбиения d-cс i = c ₁ в диапазоне от 0 до 2 c .Это может быть использовано для хорошей реализации динамического программирования.Вот все значения, которые нужно вычислить до d = 20, т.е. n = 21:

v(c,d)   c=1   c=2   c=3   c=4   c=5   c=6   c=7   c=8   c=9
 d= 1:     1
 d= 2:     1     1
 d= 3:     2     1     1
 d= 4:     3     2     1     1
 d= 5:     5     4     2     1     1
 d= 6:     9     7     4     2     1     1
 d= 7:    16    12     7     4     2     1     1
 d= 8:    28    22    13     7     4     2     1     1
 d= 9:    50    39    24    13     7     4     2     1     1
 d=10:    89    70    42    24    13     7     4     2
 d=11:   159   126    76    43    24    13     7     4
 d=12:   285   225   137    78    43    24    13     7
 d=13:   510   404   245   140    78    43    24    13
 d=14:   914   725   441   251   141    78
 d=15:  1639  1299   792   452
 d=16:  2938  2331  1420   812
 d=17:  5269  4182  2550  1457
 d=18:  9451  7501
 d=19: 16952 13458
 d=20: 30410