Matematyka.pl

Jak wykazać indukcyjnie że \(\displaystyle{ n!}\) to jest ilość permutacji bez powtórzeń zbioru \(\displaystyle{ n}\) elementowego? Da się to zrobić bez indukcji ?

Próbowałeś zrobic dowód indukcyjny? Permutacja to inaczej ustawienie wyrazów w ciąg.

Zachęcam.

a4karo pisze:Próbowałeś zrobic dowód indukcyjny? Permutacja to inaczej ustawienie wyrazów w ciąg.

Zachęcam.

Nie zauważyłem że Pan odpowiedział! A zachęcony zostałem zatem dowód mój umieszczam. Myślałem nad nim trochę a z prostoty zasady indukcji matematycznej nie umiem zauważyć czy coś źle mogłem wykazać.
Zatem proszę o zerknięcie i ewentualną radę.

Dowód :
Chcemy wykazać że \(\displaystyle{ n!}\) jest ilością permutacji bez powtórzeń zbioru \(\displaystyle{ n}\)-elementowego.
Dla \(\displaystyle{ n=1}\) otrzymujemy że \(\displaystyle{ 1!=1}\) co w istocie jest prawdą.

Zatem załóżmy że tak samo jest dla dowolnego \(\displaystyle{ n}\),\(\displaystyle{ n!}\) jest ilością permutacji bez powtórzeń okreśłonego zbioru.

Chcemy wykazać że z prawdziwości założenia wynika iż \(\displaystyle{ n!(n+1)}\) jest ilością permutacji bez powtórzeń zbioru \(\displaystyle{ (n+1)}\)-elementowego.
I teraz haczyk bo nie będzie żadnych nierówności ani podzielności.
Wskażmy konstrukcję,a raczej algorytm jak można utworzyć wszystkie owe permutacje korzystając z założenia.
Podzielmy zbiór \(\displaystyle{ n+1}\)-elementowy na dwa podzbiory : \(\displaystyle{ N}\) który zawiera elementów \(\displaystyle{ n}\) i \(\displaystyle{ A}\) który ma \(\displaystyle{ 1}\) element. Postępujemy następująco,ze zbioru \(\displaystyle{ N}\) podmieniamy jeden element z elementem ze zbioru \(\displaystyle{ A}\) i w ten sposób otrzymujemy \(\displaystyle{ n! * n}\) permutacji. Czyli mamy \(\displaystyle{ n!}\) permutacji zbioru \(\displaystyle{ A}\)(wynika to z założenia) i dodatkowych \(\displaystyle{ n*n!}\)() permutacji wynikających z podmieniania elementów zbiorów \(\displaystyle{ N}\) i \(\displaystyle{ A}\).
Zatem operując na powyższych zbiorach otrzymujemy że wszystkich permutacji jest \(\displaystyle{ n! + n*n!=(n+1)!}\).

Czy moje rozumowanie jest poprawne? Nie jestem pewien czy mogę tak rozłączyć zbiory, w końcu permutację zliczam tylko w zbiorze \(\displaystyle{ N}\) operując ciągle na \(\displaystyle{ n}\) elementach. Nie wiem czy nie ucieka mi gdzieś to że powinienem na końcu dodać te zbiory i otrzymać jeden zbiór z \(\displaystyle{ n+1}\) elementami który byłby ostatnią brakującą permutacją.

dowod nie jest do konca poprawny: jak w zbiorze \(\displaystyle{ N}\) podmienisz jeden element to nadal uzyskasz permutację \(\displaystyle{ n}\) elementów, a nie permutacje \(\displaystyle{ n+1}\) elementów.

Zastanów się nad tą konstrukcją, bo łatwo ją zmodyfikować tak, aby otrzymać poprawny dowód.

To może tak !
Niech w zbiorze \(\displaystyle{ N}\) będzie \(\displaystyle{ n+1}\) elementów. Dla ułatwienia niech mają indeksy od \(\displaystyle{ 1}\) do \(\displaystyle{ n+1}\).
Permutujemy pierwsze \(\displaystyle{ n}\) elementów czyli te o indeksach \(\displaystyle{ 1,2,3....n}\). Takich permutacji jest \(\displaystyle{ n!}\) co wynika z założenia. Czyli uzyskuję \(\displaystyle{ n!}\) permutacji zbioru \(\displaystyle{ n+1}\)-elementowego.
Teraz w moim zbiorze podmieniam indeks \(\displaystyle{ n+1}\) czyli z każdym po kolei i uzyskuję \(\displaystyle{ n \cdot n!}\) permutacji różnych od stanu początkowego. Ostatecznie sumując wszystkie permutacje mam ich \(\displaystyle{ n!+n \cdot n!=(n+1)!}\).

Wydaje mi się że teraz jest dobrze.

Jak byś napisał na czym polega to "podmienienie", to byłoby jasne.

Początkowy układ wygląda tak : \(\displaystyle{ a_{1},a_{2},.....,a_{n},a_{n+1}}\). Obliczam ilość permutacji pierwszych \(\displaystyle{ n}\) elementów.. Jest ich \(\displaystyle{ n!}\) co wynika z założenia indukcyjnego.

Teraz nasz układ wyglądałby tak :
\(\displaystyle{ a_{n+1},a_{2},.....,a_{n},a_{1}}\) i znów obliczam ilość permutacji pierwszych \(\displaystyle{ n}\) elementów. Jest ich oczywiście \(\displaystyle{ n!}\). Kolejny układ to :
\(\displaystyle{ a_{1},a_{n+1},.....,a_{n},a_{2}}\), znów \(\displaystyle{ n!}\) permutacji. I mogę takich układów uzyskać \(\displaystyle{ n}\).
Czyli sumując wszystkie permutacje łącznie z początkowym układem mamy \(\displaystyle{ n! + n \cdot n!=(n+1)!}\).
Czyli to co chcemy uzyskać.

OK

Udało się , super. Dziękuję za pomoc !