Количество последовательностей более {0,1}, такое что последовательность содержит не менее половины - PullRequest
Новая
       15

Количество последовательностей более {0,1}, такое что последовательность содержит не менее половины

0 голосов
/ 08 октября 2009

Как рассчитать количество последовательностей более {0,1}, чтобы каждая последовательность содержала хотя бы половину единиц?

Ответы [ 3 ]

5 голосов
/ 08 октября 2009

Общее количество последовательностей длины n равно 2 ^ n.Если n нечетно, ровно половина из них (2 ^ (n-1)) имеет хотя бы половину из них.Для четного n необходимо учитывать, что существует n! / ((N / 2)! ^ 2) последовательностей с ровно половиной.Так что в этом случае я думаю, что у вас есть (1/2) * (2 ^ n + n! / ((N / 2)! ^ 2)).

1 голос
/ 08 октября 2009

Предположим, что общая длина последовательности равна n, а количество последовательностей, содержащих n / 2, равно:

n!/((n/2)!^2)

РЕДАКТИРОВАТЬ:

Извините, я ошибся. Я имел в виду n!/((n/2)!^2), но не n!/(2*(n/2)!). Я считал это комбинацией задач и использовал следующие формулы. (заменить k на n/2)

alt text

0 голосов
/ 08 октября 2009

Редактировать: Черт! Мы (я) всегда должны внимательно изучать проблему!
Следующее имеет дело с перечислением количества последовательностей, в которых число 0 и 1 равно! Фактическая проблема заключается в том, что число нулей должно быть меньше или равно единице !!!

Формула Пьера, n! / (2 * (n / 2)!) почти верна, на самом деле, n! / ((N / 2)! * (N / 2)!)

но это может использовать немного объяснения (каламбур предназначен ;-)).

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

Давайте сосредоточимся на размещении 0s . Для последовательности длины n у нас есть n / 2 нулевых битов, чтобы поместить в одну из n позиций последовательности . Нам нужно только считать нулевые биты, так как после этого не останется выбора в отношении однобитных: все остальные позиции потребуют 1 в них.

Итак ... n / 2 нулевых бита, для n позиций ... Существует n способов выбора первой позиции, затем (n-1) способов выбора второй позиции (два биты не могли занимать одну и ту же позицию) и т. д. Следовательно, это число вариантов выбора 

  n! / (n/2)!

например, для n = 6 имеем 

       6 * 5 * 4 choices,  
       which, by multiplying and dividing by (3*2*1) is equivalent to
    =  6 * 5 * 4 * (3 * 2 * 1) / (3 * 2 * 1)   
    =  6! / 3!
    =  n! / (n/2)!  (a)

Теперь ... некоторые из этих вариантов [куда поместить первый бит, второй бит и т. Д.] приводят к одной и той же комбинации , потому что все нулевые биты одинаковы и, следовательно, один ли скажем, «первый» бит в позиции x и «2-й» бит в позиции y, или первый в y, а второй в x, мы получили бы одну и ту же комбинацию. Есть (н / 2)! способы размещения этих n / 2 бит. В примере с n = 6 существует 3 способа выбора позиции для «первого» бита, 2 способа для 2-го бита и 1 (то есть без выбора) для последнего нулевого бита. Затем полная формула должна быть (а) разделена на (n / 2) !, то есть: 

  n! / (n/2)! * 1/(n/2)! 
= n! / ((n/2)! * (n/2)!)
...