Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
It does not hurt if you had to type in permutation instead of perm. Reading that several times makes me feel weird! –  user21436 Mar 14 '12 at 8:15
    
You should check the following link: en.wikipedia.org/wiki/Derangement –  Dennis Gulko Mar 14 '12 at 8:19
    
And perhaps more relevantly this one: en.wikipedia.org/wiki/Rencontres_numbers, which is linked to from the one Dennis mentioned. –  Tara B Mar 14 '12 at 10:30
    
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? –  Marc van Leeuwen Mar 14 '12 at 10:41
    
Thanks @Arturo Magidin. I will typeset fully in future. –  Enjoys Math Mar 14 '12 at 23:20

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
2  
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$.) –  Tara B Mar 14 '12 at 10:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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