Задача от комбинаториката!

[EndIsNear]

Дадена е азбуката A = { a , b , c } да се намери броят на думите с дължина 10 символа , такива че броят на 'a' е по-голям от този на 'b'. Тази задача нещо ме затруднява може ли някой да ми помогне ,ако може и да е с по-подробни обяснения , благодаря предварително !

[Гост]

Азбука [tex]A=\{a,\hspace{2mm}b,\hspace{2mm}c\}[/tex]. Дължина на думите [tex]10[/tex]. Искаме участието на [tex]a[/tex] да е по-голямо от участието на [tex]b[/tex] като брой.
Нека [tex]a[/tex] участва [tex]k[/tex] пъти. Очевидно [tex]k\ge[/tex], понеже [tex]k[/tex] е по-голямо от участието на [tex]b[/tex], което най-малко е [tex]0[/tex]. Също така [tex]k\le 10[/tex]. Нека участието на [tex]b[/tex] е [tex]m[/tex]. Тук [tex]0\le m\le k-1[/tex]. Освен това [tex]k+m\le 10[/tex].
Нека броят на думите с [tex]k[/tex] [tex]a[/tex] и [tex]m[/tex] [tex]b[/tex] е [tex]w_{km}[/tex]. Тогава търсеният брой е [tex]\sum_{k=1}^{10}{\sum_{m=0}^{\min{(k-1, 10-k)}}{w_{km}}}[/tex].
Сега да сметнем [tex]w_{km}[/tex]. [tex]a[/tex]-тата избираме по [tex]{10 \choose k}[/tex] начина (по колко начина можем да ги сложим на [tex]k[/tex] места от [tex]10[/tex]). Остават незаети [tex]10-k[/tex] места. Слагаме [tex]b[/tex]-тата на тях по [tex]{10 -k \choose m}[/tex]. Останалите места пълним с [tex]c[/tex]-та. Значи [tex]w_{km}={10 \choose k}{10 -k \choose m}[/tex].
Остава сега да сметне сумата по горе. За малки числа като дадените сигурно просто се разписва.

[ptj]

Тази задача има и друго решение(чрез допълнение до пълното множество).

Броя на всички 10 символни думи в [tex]A[/tex] е 10^3.

Броя на думите съдържащи по равен брой символи [tex]a[/tex] и [tex]b[/tex] е [tex]{10\choose 0}+{10\choose 2}+{10\choose 4}+{10\choose 6 }+{10\choose 8}+{10\choose 10}[/tex]
Горе използваме факта, че думите съдържащи равен брой [tex]a[/tex]
и [tex]b[/tex], имат четен брой [tex]c[/tex]-та.

Накрая изваждаме от първата група втората, а резултата делим на 2, защото може да разменим символите [tex]a[/tex] и [tex]b[/tex].
Т.е. на всяка дума, съдържаща повече [tex]а[/tex] отколкото [tex]b[/tex], да съпоставим еднозначно дума, съдържаща повече [tex]b[/tex] отколкото [tex]a[/tex].

П.П. Решението на дуалната задача е често срещан метод, имащ приложение в различни области на математиката.

[pal702004]

Броя на всички 10 символни думи в [tex]A[/tex] е 10^3.

$3^{10}$

ТБроя на думите съдържащи по равен брой символи [tex]a[/tex] и [tex]b[/tex] е [tex]{10\choose 0}+{10\choose 2}+{10\choose 4}+{10\choose 6 }+{10\choose 8}+{10\choose 10}[/tex]

[tex]{10\choose 0}\cdot {10 \choose 5}+{10\choose 2}\cdot {8 \choose 4}+{10\choose 4}\cdot {6 \choose 3}+{10\choose 6 }\cdot {4 \choose 2}+{10\choose 8}\cdot {2 \choose 1} +{10\choose 10}[/tex]

[ptj]

Да, съгласен съм с забележките.