Сколько существует двоичных чисел длины n , таких, что в их записи количество единиц больше количества нулей?

Question

n = int(input())
ans = 1                       # начиная со случая где вообще нет 0, а просто 1
for i in range(1,(n+1)//2):   # i - это нули
    ans +=(n- 1 - i) * i + 1  #взять число, убрав нули и самую первую цифру(тоесть 1, т.к. числа с начинающиеся с нуля не считаются) и умножить на количество нулей, рассмотрев тем самым все возможные перемещения нулей

print(ans)

не проходит и нескольких тестов я налажал с формулой, с количеством итераций или с чем еще?

Answer 1

если не путаю, то решение в лоб будет выглядеть так:

res = 0

for i in range(math.floor(1 + n / 2), n + 1):
    res += math.factorial(n) // (math.factorial(i) * math.factorial(n - i))

print(res)

Answer 2

Чтобы узнать, сколькими способами можно получить k элементов (в нашем случае единиц) из n элементов (в нашем случае полная длинна) используются сочетания. А конкретно, нас интересует, сколькими способами можно выбрать k элементов из n-элементного множества. Для этого используется формула C^k_n.

import math

def c_n_k(n, k):
    """
    Получение количества сочетаний k элементов из n-элементного множества
    """
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

n = int(input())  # Длина двоичного числа

minimum_ones = math.floor(n / 2) + 1  # Минимальное количество единиц, чтобы удовлетворялось условие

ans = 0

for ones_count in range(minimum_ones, n + 1):  # Перебираем количество единиц, начиная от минимума до полной длины
    ans += c_n_k(n, ones_count)  # Прибавляем количество чисел, в которых ones_count единиц

Последние 3 строки можно написать в одну, используя функцию map:

ans = sum(map(lambda x: c_n_k(n, x), range(minimum_ones, n + 1)))

Answer 3

Думаю можно решить быстрее без цикла суммирования:

import math

def binomial(a, b):
    return math.factorial(a) // (math.factorial(b) * math.factorial(a - b))

n = int(input())
if n > 1:
    c = 2 ** (n - 2) + (n % 2) * binomial(n - 1, (n - 1) // 2) // 2
elif n == 1:
    c = 1
else:
    c = 0

Числа начинающиеся с нуля не учитываются.

БЛОГ НА HUSL

Сколько существует двоичных чисел длины n , таких, что в их записи количество единиц больше количества нулей?

Ответы (3 шт):