Kombinatoryka ala: Na ile sposobów można posadzić na ławie n małżeństw, tak aby żaden mąż nie siedział obok swojej żony?

PW: Usadźmy na początek same kobiety. Można to zrobić na n! sposobów. Dowolnie wybranego mężczyznę można do nich dosadzić na (n+1) sposobów (przed pierwszą, po pierwszej, po drugiej, ..., po n−tej). Warunek zadania będzie spełniony, gdy nie zajmie on miejsca przed− ani po swojej małżonce, można to więc uczynić na (n+1) − 2 = (n−1) sposobów. Na ławie siedzi teraz jedna osoba więcej, następny mężczyzna może więc zająć jedno z (n+2) − 2 = n miejsc. Kontynuując to postępowanie widzimy, że każdy następny mężczyzna ma o jedno więcej miejsce do wyboru niż jego poprzednik, jeżeli chce spełnić warunek zadania. Wygląda na to, że wszystkich sposobów usadzenia n małżeństw w sposób podany w zadaniu jest n!(n−1)n(n+1)...(2n−2) = (2n−2)!n(n−1). Milu, powiedz że tym razem nie bredzę.

anulaa: moze ta odp ktos jeszcze potwierdzic?

5-latek: Tak to wlasnie potem jest . Mąż nie siedzi obok swojeje żony a potem sie dziwią że sa nieślubne dzieci

PW: anulaa, weryfikuj własnym rozumem. Każdy może się pomylić, dlatego nie dam sobie łba uciąć za swoją propozycję. Weryfikacja może polegać na: − prześledzeniu rozumowania i potwierdzeniu bądź zaprzeczeniu logiki wywodu (szczególnie zwrócić uwagę, czy w opisany sposób nie liczymy wielokrotnie bądź nie pomijamy niektórych permutacji, − znalezieniu kontrprzykładu − na przykład "ręcznie" wypisujesz wszystkie możliwości dla n=3 czy n=4 i mówisz − lipa, wzór nie daje poprawnego wyniku, albo − dla tych n wzór sprawdza się, − napisaniu programu, który policzy to dla naturalnych n w zakresie możliwym dla komputera i porówna ze wzorem. Pytanie "może tę odpowiedź ktoś potwierdzić" jest naiwne − a jak Ci potwierdzą jeszcze dwie osoby, to uwierzysz? Prawdy naukowej nie ustala się przez głosowanie. Nie chcę, żebyś moją wypowiedź rozumiała jako arogancję, "wymądrzanie się" pewnego siebie faceta. Wcale nie jestem pewien tego co zaproponowałem, dlatego zachęcam Cię do samodzielnej weryfikacji. Będę zadowolony, jeżeli dojdziesz do wniosku, że się mylę

Trivial: PW, mogę zweryfikować symulacją.

PW: Tak myślałem, że się odezwiesz , świetnie.

pomocnik: Z treści zadania nie wynika, co rozumiemy przez "sposób posadzenia na ławie", tj. czy ma znaczenia, gdzie jest początek, a gdzie koniec ławy, czy przez sposób usadzenia rozumiemy, kto jest naszym sąsiadem. Co do sposobu PW, mam wątpliwości. Przypuśćmy, że mamy 2 małżeństwa (ze wzoru PW wychodzą 4 możliwości?), jedno K₁,M₁ oraz drugie K₂, M₂. Jeżeli zakładam, że ława ma początek i koniec, to otrzymuje możliwości: K₁,M₂,M₁,K₂ K₁,K₂,M₁,M₂ M₁,M₂,K₁,K₂ M₁,K₂,K₁,M₂ K₂,M₁,M₂,K₁ itd. (już mam 5). Dobrze rozumuje? A może ława jest okrągła?

Trivial: PW, to za chwilkę napiszę.

Trivial: Dla dwóch małżeństw wychodzi mi 8.

Trivial: [Maz 1,Maz 2,Zona 1,Zona 2] [Zona 1,Maz 2,Maz 1,Zona 2] [Zona 2,Zona 1,Maz 2,Maz 1] [Maz 2,Zona 1,Zona 2,Maz 1] [Zona 2,Maz 1,Maz 2,Zona 1] [Maz 2,Maz 1,Zona 2,Zona 1] [Maz 1,Zona 2,Zona 1,Maz 2] [Zona 1,Zona 2,Maz 1,Maz 2]

Trivial: Tutaj program: http://ideone.com/XTXIC5

PW: Jestem zadowolony, nareszcie ktoś wykonał proste sprawdzenie, a nie głosowanie. Pewnie zaraz dojdziemy, co było źle w propozycji z 20:18 z 24 kwietnia (niektóre permutacje nie były liczone?).

Trivial: PW, Twoim sposobem uzyskujemy: (1) Ż₁Ż₂ → Ż₁Ż₂M₁ → Ż₁Ż₂M₁M₂ lub M₂Ż₁Ż₂M₁ (2) Ż₂Ż₁ → M₁Ż₂Ż₁ → M₁Ż₂Ż₁M₂ lub M₂M₁Ż₂Ż₁ A gdzie sytuacja: Ż₂M₁M₂Ż₁, której nie można uzyskać dodając mężów pojedynczo (w pierwszym korku naruszony zostanie warunek zadania)?

Trivial: w pierwszym kroku ..

PW: O, tu trafiłeś w sedno, dziękuję. Chyba się nie da poprawić tego mojego sposobu, za dużo byłoby "chyba że". Trzeba pomyśleć nad innym, pewnie jest prosty, ale ja nie uczyłem się matematyki dyskretnej i nie wiem w tej chwili jak do tego podejść.

Trivial: PW, a może wystarczy pomnożyć przez 2? (Ewentualnie 2ⁿ⁻¹?)

PW: Nie wiem, w tej chwili mam pustkę w głowie. Ale jak znam siebie, dzisiaj spać nie będę, dlatego wołam : Mila, ratuj!

th: Trivial moglbys obliczyc ile dla trzech par?

Trivial: n 1 2 3 4 5 a_n 0 8 240 13824 1263360

Mila: Znalazłam wzór, wyniki jak u Triviala, ale nie umiem wytłumaczyć. Myślę. PW, nie martw się, młode orły znają teorię i ujawnią się.

PW: Wymyśliłem taki rekurencyjny wzór, który bierze się z dokładania (k+1) pary do już siedzących k par. Dobre ustawienie (k+1) par uzyskamy: − dokładając do dobrego ustawienia k par dwoje następnych na dowolnych z 2k+1 miejsc − dokładając dwoje następnych do takiego ustawienia k par, w którym małżonkowie dokładnie jednej z par sąsiadują ze sobą (można to uczynić na 2!•2k = 4k sposobów), − dokładając dwoje następnych do takiego ustawienia k par, w którym małżonkowie dokładnie 2 par sąsiadują ze sobą w swoich parach. Wzór ma postać: L₀(k+1) = 2k(2k+1)L₀(k) + 4kL₁(k) + 2L₂(k), gdzie L₀(k) oznacza liczbę poprawnych ustawień dla k małżeństw, L₁(k) oznacza liczbę takich ustawień k małżeństw, w których dokładnie jedno sąsiaduje ze sobą L₂(k) oznacza liczbę ustawień k małżeństw, w których małżonkowie dokładnie 2 par sąsiadują ze sobą w swoich parach. Dla k=3 otrzymamy L₀(3) = 4•5•L₀(2) + 4•2•L₁(2) + 2•L₂(2) = 20•8 + 8•8 + 2•8 = 240. L₁(2) i L₂(2) liczyłem "na boku". Na razie się zgadza z wyliczeniami Triviala, dla n= 4 nie mam siły liczyć "ręcznie", może ktoś się pokusi. Gdyby popracować trochę nad tymi L₁(k) i L₂(k), to mielibyśmy jawny wzór.