contributing permutation matrices

This idea is taken from the paper of Herbert S. Wilf
Write out all permutations and see how many contribute to the mobius function. Their number is equal to the number of ordered factorizations of n, or perfect partitions of n.
 
1              
               
0 1            
1 0            
               
0 0 1          
0 1 0          
1 0 0          
               
0 0 0 1        
1 0 0 0        
0 0 1 0        
0 1 0 0        
               
0 0 0 1        
0 1 0 0        
0 0 1 0        
1 0 0 0        
               
0 0 0 0 1      
0 1 0 0 0      
0 0 1 0 0      
0 0 0 1 0      
1 0 0 0 0      
               
0 0 0 0 0 1    
1 0 0 0 0 0    
0 0 1 0 0 0    
0 0 0 1 0 0    
0 0 0 0 1 0    
0 1 0 0 0 0    
               
0 0 0 0 0 1    
0 1 0 0 0 0    
1 0 0 0 0 0    
0 0 0 1 0 0    
0 0 0 0 1 0    
0 0 1 0 0 0    
               
0 0 0 0 0 1    
0 1 0 0 0 0    
0 0 1 0 0 0    
0 0 0 1 0 0    
0 0 0 0 1 0    
1 0 0 0 0 0    
               
0 0 0 0 0 0 1  
0 1 0 0 0 0 0  
0 0 1 0 0 0 0  
0 0 0 1 0 0 0  
0 0 0 0 1 0 0  
0 0 0 0 0 1 0  
1 0 0 0 0 0 0  
               
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
               
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
               
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
               
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0

Mats Granvik, email mats.granvik(at)abo.fi

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.