I want to write a formula for $n!$.

$n!$ is the number of permutation functions on the set $\{1,\ldots,n\}$.

Let's define a "true k-permutation" on $\{1,\ldots,n\}$ as a permutation that is identity on exactly $n-k$ elements, i.e., if $\phi$ is a $k$-permutation then $\phi(i) = i$ only on $n-k$ elements.

This seems like an elementary object yet I don't know what you call such perms (That is my question).

Notice that the relation $\phi$ is a true $k$-permutation partitions the group of permutations on $\{1,\ldots,n\}$.

So there is a formula for $n!$ involving counting of true $k$-perms. The one I have involves sum partitions of $k$ and disjoint compositions of cycles. But there's probably other ways to count them.

But this has to have been done already, so I would appreciate it if someone could post a link.

  • 2
    $\begingroup$ It does not hurt if you had to type in permutation instead of perm. Reading that several times makes me feel weird! $\endgroup$ – user21436 Mar 14 '12 at 8:15
  • $\begingroup$ You should check the following link: en.wikipedia.org/wiki/Derangement $\endgroup$ – Dennis Gulko Mar 14 '12 at 8:19
  • $\begingroup$ And perhaps more relevantly this one: en.wikipedia.org/wiki/Rencontres_numbers, which is linked to from the one Dennis mentioned. $\endgroup$ – Tara B Mar 14 '12 at 10:30
  • $\begingroup$ Your first sentence is puzzling. Surely you know a formula for $n!$ that doesn't require counting the permutations with $n-k$ fixed points (which is the usual way to designate your "true $k$ permutations") separately? $\endgroup$ – Marc van Leeuwen Mar 14 '12 at 10:41
  • $\begingroup$ Thanks @Arturo Magidin. I will typeset fully in future. $\endgroup$ – BananaCats Category Theory App Mar 14 '12 at 23:20

A permutation which leaves no element fixed (what you call a "true $n$-permutation") is called a derangement. I know of no common term for "true $k$-permutations" in general.

  • 2
    $\begingroup$ Well, probably they are usually just called permutations with support size $k$. (The support of a permutation $\sigma$ is the set of points moved by $\sigma$.) $\endgroup$ – Tara B Mar 14 '12 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.