Six ways to display the 24 Permutations of 1, 2, 3, 4.

Type Chess-Board Tableaux Line & Cycle  Tree Caterpillar
A

[1]
*    
 *   
  *  
    *
123 4
     
123 4
     
Line
1-2-3-4
Cycle
(1)(2)(3)(4)
  *   
1
  2   
  3   
  4   
 
1234^^^^
 
B

[2]
*    
 *   
    *
  *  
123  
4    
123  
4    
Line
1-2-4-3
Cycle
(1)(2)(3,4)
  *   
 1 
 2   
 3  4  
      
 
124^3^^^
 
C

[3]
*    
  *  
 *   
    *
124  
3    
124  
3    
Line
1-3-2-4
Cycle
(1)(2,3)(4)
  *   
 1 
 2 3  
 4    
      
 
13^24^^^
 
C

[4]
*    
  *  
    *
 *   
124  
3    
123  
4    
Line
1-3-4-2
Cycle
(1)(2,3,4)
  *   
 1 
2  3  
    4  
      
 
134^^2^^
 
C

[5]
*    
    *
 *   
  *  
123  
4    
124  
3    
Line
1-4-2-3
Cycle
(1)(2,4,3)
  *   
 1 
 2 4  
 3    
      
 
14^23^^^
 
D

[6]
 *   
*    
  *  
    *
134  
2    
134  
2    
Line
2-1-3-4
Cycle
(1,2)(3)(4)
  *   
1  2  
 3   
 4    
      
 
2^134^^^
 
D

[7]
 *   
  *  
    *
*    
134  
2    
123  
4    
Line
2-3-4-1
Cycle
(1,2,3,4)
  *   
 1  2
   3  
    4  
      
 
234^^^1^
 
D

[8]
  *  
*    
 *   
    *
124  
3  
134  
2    
Line
3-1-2-4
Cycle
(1,3,2)(4)
  *   
1  3  
 2   
 4    
      
 
3^124^^^
 
D

[9]
    *
*    
 *   
   * 
123  
4    
134  
2    
Line
4-1-2-3
Cycle
(1,4,3,2)
  *   
1  4  
 2   
 3    
      
 
4^123^^^
 
E

[10]
*    
    *
  *  
 *   
121 2
3 3  
4 4  
     
Line
1-4-3-2
Cycle
(1)(2,4)(3)
  *   
 1  
 23 4  
     
      
 
14^3^2^^
 
F

[11]
 *  
*   
   *
  * 
13   
24   
13   
24   
Line
2-1-4-3
Cycle
(1,2)(3,4)
  *   
 1  2  
34   
      
      
 
2^14^3^^
 
F

[12]
 *   
    *
  *  
*    
131 2
2 3  
4 4  
     
Line
2-4-3-1
Cycle
(1,2,4)(3)
  *   
 1  2  
   3 4
     
      
 
24^3^^1^
 
F

[13]
  *  
*    
    *
 *   
121 3
342 4
     
     
Line
3-1-4-2
Cycle
(1,3,4,2)
  *   
 1  3  
24   
      
      
 
3^14^2^^
 
F

[14]
    *
*    
  *  
 *   
121 3
3 2  
4 4  
     
Line
4-1-3-2
Cycle
(1,4,2)(3)
  *   
 1  4  
23   
      
      
 
4^13^2^^
 
G

[15]
 *   
  *  
*    
    *
134  
2    
124  
3    
Line
2-3-1-4
Cycle
(1,2,3)(4)
  *   
1  2
 4  3  
      
      
 
23^^14^^
 
G

[16]
  *  
    *
*    
 *   
121 2
343 4
     
     
Line
3-4-1-2
Cycle
(1,3)(2,4)
  *   
13
 2 4  
      
      
 
34^^12^^
 
G

[17]
 *   
    *
*    
  *  
13   
24   
12   
34   
Line
2-4-1-3
Cycle
(1,2,4,3)
  *   
12  
 34  
      
      
 
24^^13^^
 
H

[18]
  *  
 *   
*    
    *
141 4
2 2  
3 3  
     
Line
3-2-1-4
Cycle
(1,3)(2)(4)
  *   
1 2  3
4    
     
      
 
3^2^14^^
 
H

[19]
  *  
 *   
    *
*    
141 3
2 2  
3 4  
     
Line
3-2-4-1
Cycle
(1,3,4)(2)
  *   
12 3
 4  
      
      
 
3^24^^1^
 
H

[20]
  *  
    *
 *   
*    
141 2
2 3  
3 4  
     
Line
3-4-2-1
Cycle
(1,3,2,4)
  *   
1 2   3
     4
     
      
 
34^^2^1^
 
H

[21]
    *
 *   
*    
  *  
131 4
2 2  
4 3  
     
Line
4-2-1-3
Cycle
(1,4,3)(2)
  *   
1 2  4
3    
     
      
 
4^2^13^^
 
H

[22]
    *
 *   
  *  
*    
131 3
2 2  
4 4  
     
Line
4-2-3-1
Cycle
(1,4)(2)(3)
  *   
1 2  4
 3  
      
      
 
4^23^^1^
 
H

[23]
    *
  *  
*    
 *   
121 4
3 2  
4 3  
     
Line
4-3-1-2
Cycle
(1,4,2,3)
  *   
1 3  4
2    
     
      
 
4^3^12^^
 
I

[24]
    *
  *  
 *   
*    
1 1  
2 2  
3 3  
4 4  
Line
4-3-2-1
Cycle
(1,4)(2,3)
  *   
12 3 4
     
     
     
 
4^3^2^1^
 

The type of the permutation is the type of the unlabeled rooted tree it is associated with. Labeled rooted trees are of the same type if they are equal under branch rotation. In our example there are nine types (A,B,..,I), 1+1+3+4+1+4+3+6+1 = 24 = 4!. This is a refinement of the factorial numbers.

See also Frank Ruskey's page.

Die Raupe frisst sich nimmersatt entlang des Umrisses des Baums, beginnend rechts von der Wurzel und einen Knoten stets dann verschlingend, wenn sie an ihm auf der rechten Seite vorbeigleitet.

previous Back to the Homepage of Factorial Algorithms.