Помощ с една задача от комбинаторика

[rosysm]

Колко е броят на всички двоични вектори с дължина 15, които съдържат:
а) нечетен брой единици и са палинроми
б)четен брой нули и са палиндроми

[peyo]

Колко е броят на всички двоични вектори с дължина 15, които съдържат:
а) нечетен брой единици и са палинроми
б)четен брой нули и са палиндроми

Ще предположа, че "двоични вектори с дължина 15" означчава 15 битово двоично число. Тогава да се опитаме да решим а) като просто преброим числата:

Може да имаме числа с 1,3,5,7,9,11,13,15 единици.

За 1:
Имаме само едно число което отговаря на ословит:
000000010000000
1=1

За 3:
Ще поставим едната единица вв средата и това ще правим с виски останали числа също:
000000010000000
И вждаме, че имаме само 7 числа които отговарят на условието:
100000010000001
010000010000010
...
000000111000000
3=7

За 5:
Започваме от
000000010000000
И след това огледално от всяка страна всички комбинации от 2 числа:
110000010000011
101000010000101
...
Тук стават много да ги изброяваме и затова да сметнем по колко начина може да сложим 2 единици на 7 позиции?
5 = $\frac{7*6}{1*2} = 21$

И тук забелязваме, че тази формула обхваща и първите два случая, Затова ще напишем по-обща формула :

[tex]\sum_{n=1}^{15} a_n[/tex] само за нечетни n, където $a_n$ е:

$a_n = \frac{\prod_{k=7-(n-1)/2}^{7}k } {((n-1)/2)!}$, а това нещо много прилича, тоест е същото като биномния коефицент:

$a_n = {7 \choose (n-1)/2}$

И сега можем просто да разпишем сумата:

[tex]\sum_{}^{} a_n = 1 + \frac{7}{1} + \frac{7.6}{1.2} + \frac{7.6.5}{1.2.3} + \frac{7.6.5.4}{1.2.3.4} + \frac{7.6.5.4.3}{1.2.3.4.5} + \frac{7.6.5.4.3.2}{1.2.3.4.5.6} + \frac{7.6.5.4.3.2.1}{1.2.3.4.5.6.7}[/tex]

И сега това много е лесно да го сметнем, защото тази съма също палиндром , тоеаст първите 4 члена са огледално симетрични на вторите 4 члена.

$\sum_{}^{} a_n = 2*(1 + 7 + 7*3 + 7*5) = 128 $

С което задачата е решена.

Сега някой ще каже, трябваше ли да пишем толкова много за да получим просто 128. Не можем ли да сведем задачата задачата до въпроса колко е $2^7 = 128$ ? И смешното е че всъщност можем, защото понеже разглеждаме само първите 7 бита от числото, задачата се свежда до колко двоични числа можем да направим от 7 бита и отговора е $2^7 = 128$, но това е прекалено кратко решение и дългия вариант е доста по-забавен. Сега може би някой друг да реши б) по дълъг или кратък начин.

[pal702004]

Четен брой нули $\Longleftrightarrow$ нечетен брох единици $\Rightarrow a=b=128$

[rosysm]

Благодаря ви!