Group Abstract Group Abstract

Message Boards Message Boards

Hidden symmetry in permutation space

Attachments:
POSTED BY: David Vasholz
3 Replies

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: EDITORIAL BOARD

Thank you for your very helpful reply!

POSTED BY: David Vasholz

The value of unioncheck[n] can be derived as $\frac{n^n}{n!}-1$.

$p_0$, The value of the first permutation (i.e. Range[n]) is given by

$$p_0 = 1+ \underset{i=0}{\overset{n-1}{\sum }}i n^{n-i-1} $$ while the $p_{n!}$, the value of the last permutation (i.e. Reverse@Range[n]) is given by $$p_{n!} = 1+ \underset{i=0}{\overset{n-1}{\sum }}i n^i$$

The sum of the two is given by $$ p_0 + p_{n!} = \underset{i=0}{\overset{n-1}{\sum }}i \left(n^i+n^{-i+n-1}\right)+2 \\ = n^n+1$$ The sum of the first and last values of reflocs[n] is $r = (n!+1) \frac{n^n}{n!} $, so therefore the value of unioncheck[n] is given by $$r- ( p_0 + p_{n!} )= (n!+1) \frac{n^n}{n!} - ( n^n+1 )= \boxed{\frac{n^n}{n!} - 1}$$

Table[n^n/n! - 1,{n,7}]
(*{0, 1, 7/2, 29/3, 601/24, 319/5, 116929/720}*)

You may also be interested in the fact that the position of a permutation perm of Range[n] in Tuples[Range[n],n] is given exactly by 1+FromDigits[perm -1,n] :

Flatten@Table[permlocs[n], {n, 5}] == 
 Flatten@Table[
   1 + FromDigits[# - 1, n] & /@ Permutations[Range@n], {n, 5}]
(*True*)

See also OEIS sequences A134640, A058128 and A062813

POSTED BY: David Trimas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard