Osapermutatsioonid

Osapermutatsioonid tähistavad järjestatud valikuid n-elementse hulga osa kohta. Olgu X = {x1, x2, ..., xn} ning 0 ≤ k ≤ n. Kui valida ja järjestada k erinevat elementi X-st nii, et kordamist ei toimu, tekib k-osapermutatsioon. Arv nPk = n!/(n−k)!, ehk n(n−1)…(n−k+1), on osapermutatsiooni arv. Kui k = n, on tegemist täispermutatsiooniga ning nPn = n!. Kui k = 0, tekib tühi järjestus ja nP0 = 1.

Omadused ja seosed. Nagu öeldud, järjekord on oluline, seega nPk erineb nii binomiaalsetest kui ka täieste permutatsioonidest. Rekursiivselt on nPk = n · (n−1)P(k−1) ja P(n,k)=0, kui k>n. Valem nPk = n!/(n−k)! ühendab osapermutatsioonide arvu factoriali kaudu.

Koguarv kõigi osapermutatsioonide jaoks, kui arvestada kõiki k väärtuseid 0..n, on ∑_{k=0}^n nPk = n! ∑_{j=0}^n 1/j!, mis on lähedane väärtusele floor(e·n!). Näiteks n=3 puhul summa on 16. Kasutusalad hõlmavad tõenäosuslikke ja kombinatoorilisi probleeme, kus oluline on valida osa elementidest ja määrata nende järjestus, näiteks järjestatud näidustuste kogumid või asendita valimiste modelleerimine.