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

[inveidar]

По колко начина седем момчета и пет момичета могат да седнат на пейка така, че никои две момичета да не са едно до друго?
По колко начина същите момичета и момчета могат да седнат около кръгла маса така, че никои две момичета да не са едно до друго?

[pal702004]

1. Петте момичета разделят пейката на 6 зони. Във всяка зона да седнат $x_i$ момчета.
$x_1+x_2+\cdots+x_6=7$

Като $x_1$ и $x_6$ може да са нули (крайните зони), но останалите трябва да са цели положителни. Можем да положим
$x_1^{'}=x_1+1,\;x_6^{'}=x_6+1$
и да получим
$x_1^{'}+x_2+\cdots+x_5+x_6^{'}=9$ вече за естествени числа.

Броят на решенията на горното уравнение в естествени числа, т.нар. "композиции на числото 9 с дължина 6" са $C_8^5=56$

Това ако децата не са именувани. Ако са - трябва да умножим по $7!5!$

Другата е аналогична, момичетата разделят кръга на 5 зони, във всяка от които трябва да има поне едно момче.
И пак дали децата са именувани, дали столовете са номерирани...

[inveidar]

За пейката е вярно. По принцип хората винаги са различни. Виж, ако задачата беше: "Дванадесет деца седят на пейка. Трябват ни пет деца, които да свършат някаква работа, като никой две от петте не седят едно до друго. Колко такива различни петорки можем да изберем?". Тогава отговорът е 56.
Би ли казал, все пак, отговорът за кръглата маса? Столовете не са различими, не са номерирани и имаме само маса и столове. Нищо друго не ни интересува.

[pal702004]

Ами добре. За да не се чудим къде е началото на кръглото, приемаме че броенето започва винаги от Марийка и броим винаги по часовниковата стрелка - само различията в този списък смятаме различни начини.
Тогава режем кръга от Марийка и става като с пейката. Само че Марийка е в началото, заедно с другите момичета я разделя на 5 зони, във всяка от които да трябва да има поне едно момче.
$C_6^4=15$
Марийка вече е избрана, значи $\times 4!7!$

[inveidar]

Добре. За кръглата маса. Дванадесет рицара са разположени около кръглата маса. Всеки е враг със съседите си. По колко начина можем да изберем 5 рицара, които не враждуват помежду си, т.е никой двама не седящи един до друг. Задачата идентична ли е с момичетата и момчетата?

[inveidar]

Добре. За кръглата маса. Дванадесет рицара са разположени около кръглата маса. Всеки е враг със съседите си и с никой от останалите. По колко начина можем да изберем 5 рицара, които не враждуват помежду си, т.е никой двама не седящи един до друг. Задачата идентична ли е с момичетата и момчетата?

[pal702004]

Ами не е. Щеше да е идентична, ако столовете бяха номерирани, а децата - неименувани. Т.е, един от вариентите е: момичетата са на столове 1,3,5,7,9.
Поне аз така разбирам задачата за рицарите.

[inveidar]

Добре. Ето такава задача:
Имаме седем бели и пет черни мъниста. Колко различни герданчета можем да направим от тези мъниста така, че черните да не са едно до друго и на герданчето да няма празно място? Белите са неразличими и черните - също.