[Kombinatoryka] Tożsamości kombinatoryczne

[justynian]

Zależy mi na dowodach czysto kombinatorycznych czy jak kto woli na bajkach do :
a) \(\displaystyle{ \frac{ (2n)!}{2^n} =n! \prod_{i=1}^{n}(2i-1)}\)
b) \(\displaystyle{ {2n \choose n} n!=2^n \prod_{i=1}^{n}(2i-1)}\)

[Marcinek665]

No to akurat miałem na jednym konkursie, więc mogę opowiedzieć te bajki:

a) Chcemy ustawić \(\displaystyle{ 2n}\) dzieci w \(\displaystyle{ n}\) ławkach. Zrobimy to na \(\displaystyle{ 2}\) sposoby. \(\displaystyle{ 1}\) będzie polegał na tym, że weźmiemy sobie \(\displaystyle{ 2n}\) dzieci i będziemy ich mieszali na wszystkie możliwe sposoby, których jest \(\displaystyle{ (2n)!}\). Możliwości jest za dużo, bo nie uwzględniliśmy sadzania ich w ławkach. Każdy dzieciak może usiąść w obrębie jednej pary na \(\displaystyle{ 2}\) sposoby (po prawej lub lewej), więc n par może siąść na \(\displaystyle{ 2^{n}}\) sposobów. Dlatego też ilość sposobów wyniesie \(\displaystyle{ \frac{(2n)!}{2^{n}}}\).

Drugi sposób: dzieci nie są dobrane w pary. Bierzemy pierwsze lepsze z brzegu dziecko i wybieramy mu parę (jednego z \(\displaystyle{ 2n-1}\) uczniów), później wybieramy kolejnego dzieciaka i wybieramy mu parę (jednego z \(\displaystyle{ 2n-3}\) uczniów) itp aż wybieramy ostatniego i wybieramy mu parę (został jeden uczeń, więc na \(\displaystyle{ 1}\) sposób). Mamy więc \(\displaystyle{ \prod_{i=1}^{n}(2i-1)}\) sposobów. Spermutujmy jeszcze ławki i dostaniemy \(\displaystyle{ n! \prod_{i=1}^{n}(2i-1)}\), czego należało dowieść.

b) Są wyścigi, jest \(\displaystyle{ 2n}\)uczestników, nie ma remisów. Chcemy zobaczyć, na ile sposobów można dobrać uczestników ze sobą (po \(\displaystyle{ 2}\)) i zanotować, kto wygra. Z jednej strony wybieramy podzbiór n elementowy ze zbioru 2n elementowego którzy będą wygrani. Robimy to na \(\displaystyle{ {2n \choose n}}\) sposobów. Potem w pozostałych n uczestnikach wybieramy na n! sposobów osobę do pary z wygraną. W efekcie \(\displaystyle{ {2n \choose n} n!}\) i mamy lewą.

Z drugiej strony możemy już na samym początku ludzi połączyć w pary. Z przykładu a) wiemy, że to zrobimy na prod_{i=1}^{n}(2i-1) sposobów. Jeszcze tylko wybrać z każdego zbioru zwycięzce (w każdej parze na 2 sposoby, a par jest n, więc \(\displaystyle{ 2^n}\)) i mamy \(\displaystyle{ 2^n \prod_{i=1}^{n}(2i-1)}\) co kończy dowód.

[wally]

To może ja poprawię to trochę:
a)
Przy drugim sposobie ustawiamy te dzieci w szereg, no i teraz bierzemy pierwsze od lewej i wybieramy mu do pary, później wybieramy pierwsze od lewej spośród niewybranych itd.
Załóżmy, że wybraliśmy dwa razy tą samą parę, \(\displaystyle{ (A,B)}\) i \(\displaystyle{ (B,A)}\), jednak jeżeli \(\displaystyle{ A}\) stoi na początku na lewo od \(\displaystyle{ B}\) to nie możemy go dobrać do \(\displaystyle{ B}\) ponieważ \(\displaystyle{ B}\) będzie pierwszym niewybranym od lewej.

[justynian]

Co do tego co napisał marcinek w a) czy jeśli bierzemy bachora pierwszego lepszego to nie wybieramy go na 2n sposobów ? tz. oczywiście tożsamość musi zachodzić ale jak uzasadnić że w ten sposób obierzemy wszystkie możliwe usadzenia w ławkach bo gdy pierwszego nie wybieramy na 2n sposobów to to chyba takie oczywiste nie jest...

[Marcinek665]

Najpierw zakładamy, że żadne dziecko nie jest w parze. Więc jeśli weźmiemy pierwszego lepszego bachora, to będzie go można sparować z dowolnym innym dzieciakiem, a tych dzieciaków będzie po odjęciu jego samego \(\displaystyle{ 2n-1}\). Potem bierzemy kolejnego dzieciaka i łączymy z innym (w dowolny sposób), czyli wybieramy mu kolegę z grona \(\displaystyle{ 2n-3}\) osób. Dlatego nie jest chyba konieczne kombinowanie z tym, co napisał Wally

[wally]

No dobra, to jeszcze jaśniej:
Każdemu dzieciakowi przypisujemy numer od \(\displaystyle{ 1}\) do \(\displaystyle{ 2n}\). Jak łączymy te dzieci w pary w ławkach to kolejność numerków nie ma znaczenia, a więc zawsze możemy założyć że para jest uporządkowana rosnąco.
Teraz działamy rekurencyjnie:
- wybieramy dzieciaka z najmniejszym numerem, spośród niewybranych
- dobieramy mu partnera do ławki
Tak więc pierwszy dzieciak jest zdefiniowany jednoznacznie, a nie na \(\displaystyle{ 2n}\) sposobów.
To że, każde przyporządkowanie jest różne, wytłumaczyłem wcześniej.
To że, każde wystąpi jest oczywiste. Weźmy dowolne przydzielenie w pary, tym algorytmem możemy wybrać odpowiedniego partnera do \(\displaystyle{ 1}\) i później do kolejnego najmniejszego niewybranego i indukcyjnie dla wszystkich. Potem mnożymy przez \(\displaystyle{ n!}\) bo kolejność ławek ma znaczenie.
Jak napiszę jeszcze jaśniej, to litery będą białe...

[justynian]

Wally chyba ostatnim postem dopiął sprawę zupełności dowodu