Инверсии в двоичной строке

Question

Сколько инверсий существует в двоичной строке длины n?

For example , n = 3 
000->0 
001->0 
010->1 
011->0 
100->2 
101->1 
110->2 
111->0 
So total inversions are 6 

Answer 1

Вопрос выглядит как домашнее задание, поэтому позвольте мне опустить детали. Вы можете:

1. Решить эту проблему как возвратность (см ответ Толя в)
2. визажистов и решить характеристическое уравнение, получим решение в виде тесной формулы с некоторыми произвольными постоянными (c1, c2,. .., cn); по сути, вы получите только один неизвестная константа.
3. Помещенный некоторые известные решения (например, f(1) = 0, f(3) = 6) в формулу и найти все неизвестные коэффициенты

Окончательный ответ вы должны получить это

f(n) = n*(n-1)*2**(n-3) 

где ** означает повышение в мощности (2**(n-3) есть 2 в n-3 мощность). Если вы не хотите иметь дело с ревальвацией и т.п., вы можете просто доказать формулу индукцией.

Answer 2

Простая рекуррентная функция. Предположим, что мы знаем ответ для n-1. И после всех предыдущих последовательностей мы добавляем 0 или 1 в качестве первого символа.

если мы добавим 0 в качестве первого символа, что означает, что количество инверсий не будет изменено: следовательно ответ будет таким же, как и для n-1.

если мы добавим 1 в качестве первого символа, что означает количество инверсий, будет таким же, как и раньше, и будет добавлено дополнительное инвертирование равным 0 во все предыдущие последовательности.

Количество нулей ANS единиц в последовательности длины n-1 будет:

(n-1)*2^(n-1) 

Половина из них нулей это даст следующий результат

(n-1)*2^(n-2) 

Это означает, что мы имеем следующие формулы:

f(1) = 0 
f(n) = 2*f(n-1) + (n-1)*2^(n-2)