Labelled enumeration theorem

In <a href="/facts/Combinatorics/k14xUoKT">combinatorial</a> mathematics, the labelled enumeration theorem is the counterpart of the <a href="/facts/P%25C3%25B3lya_enumeration_theorem/EBbxaxkz">Pólya enumeration theorem</a> for the labelled case, where we have a set of labelled objects given by an <a href="/facts/Exponential_generating_function/K7UVjnjL">exponential generating function</a> (EGF) g(z) which are being distributed into n slots and a permutation group G which permutes the slots, thus creating equivalence classes of configurations. There is a special re-labelling operation that re-labels the objects in the slots, assigning labels from 1 to k, where k is the total number of nodes, i.e. the sum of the number of nodes of the individual objects. The EGF 
 
 
 
 
 f
 
 n
 
 
 (
 z
 )
 
 
 {\displaystyle f_{n}(z)}
 
 of the number of different configurations under this re-labelling process is given by

f
          
            n
          
        
        (
        z
        )
        =
        
          
            
              g
              (
              z
              
                )
                
                  n
                
              
            
            
              
                |
              
              G
              
                |
              
            
          
        
        .
      
    
    {\displaystyle f_{n}(z)={\frac {g(z)^{n}}{|G|}}.}

In particular, if G is the <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a> of order n (hence, |G| = n!), the functions 
 
 
 
 
 f
 
 n
 
 
 (
 z
 )
 
 
 {\displaystyle f_{n}(z)}
 
 can be further combined into a single <a href="/facts/Generating_function/K7UVjnjL">generating function</a>:

F
        (
        z
        ,
        t
        )
        =
        
          ∑
          
            n
            =
            0
          
          
            ∞
          
        
        
          f
          
            n
          
        
        (
        z
        )
        
          t
          
            n
          
        
        =
        
          ∑
          
            n
            =
            0
          
          
            ∞
          
        
        
          
            
              g
              (
              z
              
                )
                
                  n
                
              
            
            
              n
              !
            
          
        
        
          t
          
            n
          
        
        =
        
          e
          
            g
            (
            z
            )
            t
          
        
      
    
    {\displaystyle F(z,t)=\sum _{n=0}^{\infty }f_{n}(z)t^{n}=\sum _{n=0}^{\infty }{\frac {g(z)^{n}}{n!}}t^{n}=e^{g(z)t}}

which is exponential w.r.t. the variable z and ordinary w.r.t. the variable t.

Labelled enumeration theorem open-in-new

Labelled enumeration theorem