Na ile sposobów możne usiąść...

[break123pl]

Na ile sposobów 5 rozróżnialnych osób może usiąść na 27 ustawionych w jednym rzędzie krzesłach, tak aby między dwiema osobami były zawsze co najmniej dwa wolne krzesła?
odp.: \(\displaystyle{ 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 = 1395360}\).

Proszę o przystępne wytłumaczenie zadania.

[Rafsaf]

Pomysł jest standardowy: "przyklejamy" \(\displaystyle{ 2}\) wolne krzesła do każdej osoby w tym sensie że te \(\displaystyle{ 2}\) wolne krzesła są pod nią.

Wtedy możemy permutować nowe elementy bez obaw że będą siedzieć przy sobie.

Czyli mając \(\displaystyle{ 5}\) osób doklejając do nich po \(\displaystyle{ 2}\) krzesła mamy rozmieścić \(\displaystyle{ 5}\) nowych elementów wśród 17 miejsc, ale zauważ że nie jesteśmy w stanie rozumując w ten sposób dostać sytuacji w której ktoś siedzi na samym dole(bo przynajmniej \(\displaystyle{ 2}\) krzesła na dole będą puste), równoważnie nigdy nie będzie tak, że licząc od góry będzie \(\displaystyle{ 14}\) ani \(\displaystyle{ 13}\) krzeseł pustych więc przyjmujemy że rozmieszczamy nowe \(\displaystyle{ 5}\) elementów wśród \(\displaystyle{ 19}\) miejsc, gdzie sytuacja że któryś jest na miejscu np. \(\displaystyle{ 19}\) odpowiada temu, że osoba siedzi na samym dole a dwa krzesła "pod nią" ktoś przestawił na sam przód

[break123pl]

zrozumiano, dziękuję

[arek1357]

Za szybko podeszliście do tematu, w tym zadaniu same permutacje to za mało ponieważ najpierw wybieramy miejsca na których siadają ludzie, a potem tych ludzi permutujemy, lecz dokonując wyboru musimy użyć raczej kombinacji, ale sprawa nie jest tak natychmiastowa...
A tu jest od razu pomnożone i przypadki wewnętrzne z brzegowymi się mieszają i powtarzają....
(Zawsze tego typu zadania staram się najpierw robić na piechotę dla małych przykładów)

Dość fajne zadanko ale pod warunkiem, że rozpatrzymy przypadek ogólny a więc:

\(\displaystyle{ n}\)- siadających i \(\displaystyle{ k}\) miejsc, przyszła mi do głowy rekurencja, ale na początku rozpatruję taki problem, że siadający ludzie są nierozróżnialni...
Doprowadziło mnie to do następującego równania w poniższy sposób:

Dołożę wzór rekurencyjny:

\(\displaystyle{ n}\)- ilość osób,\(\displaystyle{ k}\)- ilość miejsc

niech:

\(\displaystyle{ a(n,k)}\) - oznacza ilość możliwości, że na \(\displaystyle{ k}\) miejscach siedzi \(\displaystyle{ n}\) osób zgodnie z warunkami zadania...

zauważmy, że (warunki brzegowe):

\(\displaystyle{ a(n,s)=0 , s<0}\)

\(\displaystyle{ a(n,0)=0}\)

\(\displaystyle{ a(n,1)=0 , n \ge 2}\)

\(\displaystyle{ a(1,k)=k, k \ge 1}\)

łatwo też wyliczyć, że:

\(\displaystyle{ a(2,k)= \frac{\left( k-2\right)\left( k-3\right) }{2}}\)

Teraz przejdźmy do rekurencji

\(\displaystyle{ 1,0,0|,a(n-2,k-6),|0,0,1}\) - oznacza, że na pierwszym i ostatnim miejscu ktoś siedzi , a zajmowane miejsca są: od czwartego i do \(\displaystyle{ n-4}\) miejsca

i dalej:

\(\displaystyle{ 1,0,0|,a(n-2,k-7),0,|0,1,0}\)

\(\displaystyle{ 0,1,0|,0,a(n-2,k-7),|0,0,1}\)

\(\displaystyle{ 0,0,1|,0,0,a(n-2,k-8),|0,0,1}\)

\(\displaystyle{ 1,0,0|,a(n-2,k-8),0,0,|1,0,0}\)

\(\displaystyle{ 0,1,0|,0,a(n-2,k-8),0,|0,1,0}\)

\(\displaystyle{ 0,1,0|0,a(n-2,k-9),0,0|1,0,0}\)

\(\displaystyle{ 0,0,1|0,0,a(n-2,k-9),0|0,1,0}\)

\(\displaystyle{ 0,0,1|0,0,a(n-2,k-10),0,0|1,0,0}\)

Kreska pionowa oznacza "głębokość" rekurencji, (do kreski jest granica rekurencji)...

Mając wszystkie możliwości, możemy te przypadki zsumować:

\(\displaystyle{ a(n,k)=a(n-2,k-6)+2a(n-2,k-7)+3a(n-2,k-8)+2a(n-2,k-9)+a(n-2,k-10)+2a(n-1,k-6)+2a(n-1,k-7)+2a(n-1,k-8)+a(n,k-6)}\)

Oczywiście powinniśmy założyć, że:

\(\displaystyle{ n \ge 3 , k \ge 6}\)

A teraz jeżeli zechcemy założyć, że ludzie siadający są rozróżnialni to wystarczy pomnożyć to przez \(\displaystyle{ n!}\)

I otrzymamy wzór:

\(\displaystyle{ a(n,k) \cdot n!}\)

Sorki musiałem dołożyć jeszcze kilka przypadków po protu wszystkich nie wypisałem zapominając sobie za co przepraszam...

[Rafsaf]

Wczoraj po napisaniu posta przed snem pomyślałem, że napisałem brednie, ale już nie poprawiałem bo szczerze mówiąc i tak nie wiedziałem jak. Nie do końca chwytam Twoje rozumowanie, tzn rekurencja na początku ok(ideologicznie), ale takich to jeszcze nie widziałem choć jej rozwiązanie wygląda w miarę przekonywująco

Tak czy siak dzięki za sprostowanie.

[kerajs]

Inaczej.
Ustawiam \(\displaystyle{ 5}\) osób na \(\displaystyle{ 5!}\) sposobów
między każde dwie osoby wstawiam po dwa krzesła (razem \(\displaystyle{ (5-1) \cdot 2=8}\) krzeseł).
Pozostałe krzesła (jest ich \(\displaystyle{ 27-5-(5-1) \cdot 2=14}\)) mogę wstawiać przed pierwszą osobę, za ostatnią osobę i dostawiać do czterech stojących już par. Ilość podziałów tych (14) krzeseł jest równoważna z ilością rozwiązań równania \(\displaystyle{ x_1+x_2+x_3+x_4+x_5+x_6=14}\) w liczbach naturalnych czyli \(\displaystyle{ {14+6-1 \choose 6-1}}\)
Stąd ilość usadzeń spełniających warunki zadania to: \(\displaystyle{ 5! \cdot {14+6-1 \choose 6-1}= \frac{19!}{14!}}\)

Uogólniając, wystarczy wstawić \(\displaystyle{ n}\) za \(\displaystyle{ 5}\) i \(\displaystyle{ k}\) za \(\displaystyle{ 27}\).