You are here

Комбинаторика


4eBOOra6ka
Дата: Вторник, 12.06.2012, 14:28 | Сообщение # 1

3. Сколько имеется цепочек длины n над алфавитом {0,1}? Сколько среди них слов, в которых ровно k единиц? Сколько цепочек с четным числом едениц?


Admin
Дата: Вторник, 12.06.2012, 21:34 | Сообщение # 2

1) На каждом из n мест может оказаться одна из двух цифр, имеем размещение с повторениями из двух элементов по n, количество 2n.

2) Образуем цепочку из всех n нулей, в ней выберем ровно k мест для размещения ровно k единиц. Порядок этих мест, естественно, не имеет значения, так как все они заполнятся одинаковым символом: "1". Следовательно имеем неупорядоченную выборку k элементов из n, а это сочетание из n по k элементов, количество оных: Cnk = n!/((n-k)!*k!).

3) Ответы на первые два вопроса связаны интересным соотношением, которое вытекает из бинома Ньютона:
сумма всех Cnk, где k пробегает все целые значения от 0 до n равна 2n, чему собственно говоря, они являются прекрасной иллюстрацией. Несложно доказать, что ровно половину из этой суммы составит сумма Cnk с четными k, а вторую половину - с нечетными. Ответ 2n-1.


4eBOOra6ka
Дата: Среда, 13.06.2012, 07:27 | Сообщение # 3

спасибо)

Undefined
author: 
admin
Категория: