Definíció: Egy n elemû H halmaz sorbaállítása egy s:{1,2,...,n} -> H bijekció.

Az s sorbaállítás lényegében egy ``szereposztás'': az elsõ (1), második (2), haramadik (3), ... szerepeket kiosztjuk a H halmaz elemeinek úgy, hogy mindenki pontosan egy szerepet kapjon. Az elsõ, második, ... szerepeket pozícióknak is gondolhatjuk. Így pozíciók és objektumok közötti bijekció egy sorbaállítás. Hogy a pozíciókra mint egy egyenesen (tornasorban) lévõ pozíciókra gondolunk nem szükségszerû. Ha 1,2,3... egy teremben szétszórt székek számai (nevei), akkor a megfelelõ bijekció egy ültetésrend, amit szintén gondolhatunk ``sorbaállításnak''.

Jelölés: Egy H halmaz sorbaállítasainak halmazát s(H)-val jelöljük.

Jelölés: Az n elemû halmaz sorbaállításainak (vagy permutációinak) számát s_n-nel jelöljük.

Tétel: s_n=n.s_n-1.

Megjegyzés: A rekurzió azt mondja meg, hogy ha az n elemû H halmaz egy n-1 elemû H' halmaz elemeibõl és egy s új elembõl áll, akkor H' sorbaállításainak számának n-szerese adja meg H sorbaállításainak számát. Igazából H sorbaállításait generálni fogjuk úgy, hogy H' minden sorbaállításából H-nak n sorbaállítása keletkezik. Továbbá természetesen minden H-beli sorbaállítást pontosan egyszer állítunk elõ.

Bizonyítás (generálás): A H' egy s sorbaállításából és egy {1,2,...,n} pozíció halmaz egy i elemébõl úgy nyerünk H egy sorbaállítását, hogy az u új elemet beszúrjuk az s sorba úgy, hogy az u elem az i-edik legyen. Ezzel egy ß:s(H')×{1,2,...,n}->s(H) ``beszúrás'' leképzést definiáltunk, amelyrõl könnyen belátható, hogy bijekció. Ez az állítást igazolja.

Tétel: s_n=n!=1.2 ... (n-1).n

Megjegyzés: 0!=1, 1!=1.

Egy n elemû halmaz sorbaállításainak n! számára vonatkozó aszimptotikát a Stirling-formula adja meg.

A formula elnevezését James Stirling (1692-1770) matematikusról kapta.