Двоични вектори

[Nona]

[Реклама]

[r2d2]

Как да отгатнем какво е [tex]\nu (\alpha)[/tex] i B(n,k)?

[Nona]

[tex]\nu (\alpha)=\sum_{i=1}^n\alpha_i.2^{n-i}[/tex] - номер на вектора α.

Пример: [tex]\alpha=(0,1,1)\in J_2^3 \Rightarrow \nu (\alpha)=2^2.0+2^1.1+2^0.1=3.[/tex]

[tex]\omega(\alpha)=\sum_{i=1}^n\alpha_i[/tex] - тегло на вектор.

Пример: [tex]\alpha=(0,1,1)\in J_2^3 \Rightarrow \omega (\alpha)=2.[/tex]

[tex]B_k^n=\left{\alpha|\omega(\alpha)=k\right}[/tex] - k-ти слой на n-мерния булев куб.

[tex]n-k[/tex]-мерна стена (повърхнина) - множеството от всички вектори, в което k компонента са избрани и фиксирани.

n-мерен булев куб - граф с върхове n-мерните двоични вектори и ребра едномерните повърхнини.

[Nona]

[tex] \left( \begin{array} j \\ k \end{array} \right) - \left( \begin{array} i \\ k \end{array} \right) [/tex]

[nikko1]

Хмм.
Трудничка задача.
Добре значи трябва да разгледаме двоичните числа между [tex]2^i[/tex] и [tex]2^j.[/tex] Ще разгледам два случая.
I. [tex]k=1[/tex], тогава имаме [tex]j-i+1[/tex] двоични числа с тегло 1 (трябва да имаме само по една единица, но тогава те са степени на двойката и са [tex]2^i,\ 2^{i+1}, \dots, 2^{j}[/tex]
II. [tex]k\geq 2.[/tex] Ще използвам таблица и ще разделя числата в интервала [tex]2^i[/tex] и [tex]2^j[/tex] на групи след което ще преброя по колко двоични числа с тегло [tex]k[/tex] има във всяка от тях.
Първата група числа е между [tex]2^i[/tex] и [tex]2^{i+1}-1[/tex]. Всички те изглеждат така [tex]\begin{array}{lllllll}position&&i+1&i&i-1&\dots&0\\0&\dots&0&1&0&\dots&0\\0&\dots&0&1&0&\dots&1\\\dots&\dots&\dots&\dots&\dots&\dots&\dots\\0&\dots&0&1&1&\dots&1\end{array}[/tex]. Тук понеже в позиция i винаги имаме 1, то остава от станалите i позиции (да не забравим, че има и нулева) да изберем k-1 единици, което можем да направим по [tex]i\choose {k-1}[/tex] начина.
Аналогично за следващата група числа получаваме [tex]i+1\choose {k-1}[/tex] вектора с тегло k.
...
Накрая за последната група числа, които са между [tex]2^{j-1}[/tex] и [tex]2^{j}[/tex] (числото [tex]2^j[/tex] изключваме защото има само 1 единица, а тук [tex]k\geq 2[/tex]) получаваме [tex]j-1\choose {k-1}[/tex] вектора.
Сега остава да сумираме и окончателно получаваме [tex]\sum\limits_{s=i}^{j-1}{s\choose k-1}.[/tex]

P. S. Като смятаме по формулата не трябва да забравяме, че [tex]{n \choose k} = 0[/tex], ако [tex]k < 0[/tex] или [tex]k>n.[/tex]

[2sxy4u]

Алелуя !
Стигнах до същия отговор , но ми се струваше толкова изродски и брутален , че проверявам от 1/2 час дали нямам грешка и като видях пост-а ти се израдвах като малко дете

[nikko1]

[Nona]

Благодаря за решението

[Nona]

От n- та до j-та позиция не трябва да има нули, за да е изпълнено условието, значи трябва да разположим k единици на j позиции: [tex]{j \choose k} .[/tex] От i-та до j-та позиция трябва да има поне една единица, т.е. неблагоприятен е само случаят, в който всички елементи от този интервал са нули, затова го изваждаме: [tex]{j\choose k} - {i\choose k}.[/tex]



С индукция може да се докаже, че [tex] \sum\limits_{s=i}^{j-1}{s\choose k-1} = {j\choose k} - {i\choose k}.[/tex]

[2sxy4u]

E tova trqbva da e "Evala" ...

[nikko1]

Права си, но все пак твоята формула не е вярна при [tex]k=1[/tex].
Ето как може да се докаже, че двете формули са равносилни при [tex]k\geq2.[/tex]
Първо ще докажа, че [tex]{{n+1}\choose k}-{n\choose k}={n\choose{k-1}}.[/tex]
[tex]{{n+1}\choose k}-{n\choose k}=\frac{(n+1)!}{k!(n-k+1)!}-\frac{n!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}\left(\frac{n+1}{n-k+1}-1\right)=\frac{n!}{\not{k}!(n-k)!}\frac{\not{n}+\not{1}-\not{n}+\not{k}-\not{1}}{n-k+1}=\frac{n!}{(k-1)!(n-k+1)!}={n\choose{k-1}}[/tex]
Сега разглеждам e равенствата
[tex]{j\choose k}-{j-1\choose k}={j-1\choose k-1},[/tex]
[tex]{{j-1}\choose k}-{{j-2}\choose k}={j-2\choose k-1},[/tex]
...
[tex]{{i+1}\choose k}-{{i}\choose k}={i\choose k-1}.[/tex] Събираме ги и получаваме
[tex]{j\choose k}-{i\choose k}=\sum\limits_{s=i}^{j-1}{s\choose {k-1}}.[/tex]