Permutacje

18.11.2009 - Marcin Oczeretko
Trudność

    Z permutacjami spotykamy się dość często w informatyce, jak również i w codziennym życiu, choć czasem nawet nie zdajemy sobie z tego sprawy. Jeśli pragniesz dowiedzieć się, co kryje się za pojęciem permutacji i nieco sformalizować swoje intuicyjne do niego podejście, zapraszam do lektury poniższego artykułu.

    W ramach wprowadzenia zajmijmy się najpierw dość prostą grą. Chyba prawie każdy grał choć raz w Scrabble (niektórzy nawet twierdzą, że w większosci domów znajduje się pudełko z tą grą). Zasady nie są skomplikowane - w trakcie rozgrywki każdy z graczy dysponuje zestawem siedmiu płytek z nadrukowanymi nań literami i stara się ułożyć z nich jakieś słowo oraz dopasować je do płytek leżących już na planszy. Rozpatrzmy nieco uproszczoną wersję tej gry - mamy siedem płytek i musimy zbudować z nich wszystkich sensowny wyraz. Załóżmy, że posiadamy taki zestaw:

Nasz zestaw płytek

    Niektórzy być może zauważyli już, że możemy ułożyć za pomocą tych płytek wyraz MLECZNY. Ci, którym się to nie udało, nie muszą się zbytnio martwić. Wszystkich możliwych ustawień jest bardzo dużo, nic więc dziwnego, że jeden konkretny układ gdzieś nam umknął. Dla spokoju ducha policzmy jednak ile różnych wyrazów można ułożyć z tych siedmiu literek.

   

Literkę rozpoczynającą wyraz możemy wybrać na siedem sposobów, gdyż tyle płytek mamy do dyspozycji.

Drugą pozycję uzupełniamy na jeden z sześciu sposobów (możemy przecież wybrać dowolną płytkę poza tą, która już jest na stojaku).

Trzecią płytkę wybieramy spośród pięciu, itd.

    Widać już zatem, że wybierając i-tą literkę, mamy do wyboru $ 7-(i-1)=8-i $ płytek, bowiem $ (i-1) $ wykorzystaliśmy już wcześniej. Za każdym razem otrzymujemy inny wyraz, więc wszystkich układów jest: $ 7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1=5040 $. Jeśli więc nie zauważyłeś, że z CELMNYZ można ułożyć słowo MLECZNY, to pominąłeś jedną z 5040 kombinacji. Nie ma więc szczególnych powodów, by się tym faktem przejmować. Nietrudno pokazać, że gdybyśmy mieli $ n $ rozróżnialnych płytek, to ilość różnych ich ustawień jest równa $ n\cdot(n-1)\cdot\ldots\cdot2\cdot1 = n! $ (przez $ n! $, czyli "n silnia", oznaczamy iloczyn  wszystkich liczb naturalnych od $ 1 $ do $ n $).


4.333335
Twoja ocena: Brak Ocena: 4.3 (9 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com