Задачи по комбинаторика - задачи с решения

Решение:
Всеки от петте ученици попада в точно една от трите паралелки независимо от останалите, а едно разпределение се определя напълно от паралелката на всеки ученик. По правилото за умножение броят на разпределенията е
[tex]3\cdot 3\cdot 3\cdot 3\cdot 3=3^5=243[/tex]

Решение:
Редът на играчите във всяка група няма значение, затова броим комбинации. Броят на начините да се изберат вратарят, двамата защитници и тримата нападатели е съответно
[tex]\binom{2}{1}=2,\qquad \binom{6}{2}=15,\qquad \binom{8}{3}=56[/tex]
Тези избори са независими, затова по правилото за умножение броят на съставите е
[tex]2\cdot 15\cdot 56=1680[/tex]

Решение:
Цифрата [tex]0[/tex] не може да участва: тя би била най-малката цифра и би трябвало да стои на първо място, което е невъзможно за седемцифрено число. Следователно всички цифри са измежду [tex]1,2,\dots,9[/tex].
Обратно, всеки избор на [tex]7[/tex] различни цифри измежду [tex]1,2,\dots,9[/tex] дава точно едно такова число – избраните цифри, записани в нарастващ ред. Затова търсеният брой е равен на броя на начините да се изберат [tex]7[/tex] цифри от [tex]9[/tex]:
[tex]\binom{9}{7}=\binom{9}{2}=\frac{9\cdot 8}{2}=36[/tex]

Решение:
Разглеждаме случаи според мястото на единствената цифра [tex]3[/tex]. Ако тя е цифрата на стотиците, цифрите на десетиците и на единиците може да са всяка от деветте цифри, различни от [tex]3[/tex]:
[tex]9\cdot 9=81[/tex]
Ако тя е цифрата на десетиците, цифрата на стотиците не може да е [tex]0[/tex] или [tex]3[/tex] ([tex]8[/tex] възможности), а цифрата на единиците е всяка цифра без [tex]3[/tex] ([tex]9[/tex] възможности):
[tex]8\cdot 9=72[/tex]
Ако тя е цифрата на единиците, аналогично получаваме
[tex]8\cdot 9=72[/tex]
Случаите не се припокриват, затова броят на тези числа е
[tex]81+72+72=225[/tex]

Решение:
Думата има [tex]10[/tex] букви: М се среща [tex]2[/tex] пъти, А – [tex]3[/tex] пъти, Т – [tex]2[/tex] пъти, а Е, И и К – по веднъж. Ако всичките десет букви бяха различни, те биха могли да се подредят по [tex]10![/tex] начина.
Размяната на еднакви букви помежду им не променя думата, затова всяка дума е преброена точно [tex]2!\cdot 3!\cdot 2!=24[/tex] пъти сред тези подреждания. Следователно броят на различните думи е
[tex]\frac{10!}{2!\cdot 3!\cdot 2!}=\frac{3628800}{24}=151200[/tex]

Решение:
Три точки са върхове на триъгълник точно когато не лежат на една права. Затова трите върха не може да са върху една и съща от дадените прави, т.е. триъгълникът има два върха върху едната права и един връх върху другата. Обратно, всяка такава тройка точки дава триъгълник, защото третата точка не лежи на правата през другите две (правите са успоредни и различни).
Два върха върху правата с [tex]10[/tex] точки и един върху другата права:
[tex]\binom{10}{2}\cdot 20=45\cdot 20=900[/tex]
Два върха върху правата с [tex]20[/tex] точки и един върху другата права:
[tex]\binom{20}{2}\cdot 10=190\cdot 10=1900[/tex]
Двата случая не се припокриват, затова общият брой на триъгълниците е
[tex]900+1900=2800[/tex]

Решение:
Има значение кой в кой град заминава, затова броим наредените тройки от различни служители, избрани измежду всичките [tex]9[/tex] (вариации). Без ограничения броят им е
[tex]9\cdot 8\cdot 7=504[/tex]
Недопустими са изборите без икономист, т.е. когато и тримата заминаващи са юристи:
[tex]5\cdot 4\cdot 3=60[/tex]
Всеки друг избор съдържа поне един икономист, затова търсеният брой е
[tex]504-60=444[/tex]

Решение:
Според Нютоновия бином общият член на развитието е
[tex]T_{k+1}=\binom{7}{k}\left(2x^{4}\right)^{7-k}\left(\frac{1}{x^{3}}\right)^{k}=\binom{7}{k}\cdot 2^{7-k}\cdot x^{28-7k},\qquad k=0,1,\dots,7[/tex]
Членът не съдържа [tex]x[/tex] точно когато [tex]28-7k=0[/tex], т.е. [tex]k=4[/tex]. Следователно свободният член е
[tex]T_{5}=\binom{7}{4}\cdot 2^{3}=35\cdot 8=280[/tex]

Решение:
Изразите са [tex]2^4=16[/tex], но различни изрази може да имат равни стойности, затова броим директно стойностите. Нека [tex]S[/tex] е сборът на числата, пред които стои знак минус. Тогава стойността на израза е
[tex](2+4+6+8)-2S=20-2S[/tex]
Следователно различните стойности на [tex]S[/tex] дават различни стойности на израза и обратно. Записваме [tex]S=2T[/tex], където [tex]T[/tex] е сборът на някои от числата [tex]1; 2; 3; 4[/tex] (евентуално на нито едно от тях). Всяко цяло число от [tex]0[/tex] до [tex]10[/tex] е такъв сбор:
[tex]0; 1; 2; 3; 4; 5=1+4; 6=2+4; 7=3+4; 8=1+3+4; 9=2+3+4; 10=1+2+3+4[/tex]
Други стойности не са възможни, тъй като [tex]0\le T\le 10[/tex]. Следователно стойността [tex]20-4T[/tex] на израза приема точно [tex]11[/tex] различни стойности:
[tex]-20; -16; -12; \dots; 16; 20[/tex]

Решение:
Първо подреждаме в редица [tex]8[/tex] червени химикалки; тъй като са еднакви, това става по единствен начин. Те образуват [tex]9[/tex] места за сините химикалки: [tex]7[/tex] празнини между съседни червени химикалки и [tex]2[/tex] места в двата края.
Две сини химикалки са съседни точно когато са поставени на едно и също място, затова сините химикалки трябва да заемат [tex]4[/tex] различни места измежду тези [tex]9[/tex]. Сините химикалки са еднакви, така че има значение само кои места са избрани, и всяко допустимо подреждане се получава точно веднъж:
[tex]\binom{9}{4}=\frac{9\cdot 8\cdot 7\cdot 6}{4!}=126[/tex]

Решение:
Фигурата трябва да се премести с [tex]7[/tex] колони надясно и с [tex]7[/tex] реда нагоре. Всеки ход променя или колоната, или реда с [tex]1[/tex], затова са нужни поне [tex]14[/tex] хода, а [tex]14[/tex] хода са достатъчни.
Път от [tex]14[/tex] хода не може да съдържа ход наляво или надолу: такъв ход би трябвало да се компенсира с допълнителен ход надясно или нагоре и пътят би станал по-дълъг от [tex]14[/tex] хода.
Следователно най-кратките пътища са точно редиците от [tex]7[/tex] хода „надясно“ и [tex]7[/tex] хода „нагоре“ в някакъв ред (всяка от тях остава в дъската). Такава редица се определя от избора кои [tex]7[/tex] от общо [tex]14[/tex] хода са „надясно“:
[tex]\binom{14}{7}=3432[/tex]