Method of distinguished element

<h2 id="definition">Definition</h2>
Let 
 
 
 
 
 
 A
 
 
 
 
 {\displaystyle {\mathcal {A}}}
 
 be a <a href="/facts/Family_of_sets/WbYof7lP">family of subsets</a> of the set 
 
 
 
 A
 
 
 {\displaystyle A}
 
 and let 
 
 
 
 x
 ∈
 A
 
 
 {\displaystyle x\in A}
 
 be a distinguished element of set 
 
 
 
 A
 
 
 {\displaystyle A}
 
. Then suppose there is a <a href="/facts/Predicate_(mathematical_logic)/5WazAvKF">predicate</a> 
 
 
 
 P
 (
 X
 ,
 x
 )
 
 
 {\displaystyle P(X,x)}
 
 that relates a subset 
 
 
 
 X
 ⊆
 A
 
 
 {\displaystyle X\subseteq A}
 
 to 
 
 
 
 x
 
 
 {\displaystyle x}
 
. Denote 
 
 
 
 
 
 A
 
 
 (
 x
 )
 
 
 {\displaystyle {\mathcal {A}}(x)}
 
 to be the set of subsets 
 
 
 
 X
 
 
 {\displaystyle X}
 
 from 
 
 
 
 
 
 A
 
 
 
 
 {\displaystyle {\mathcal {A}}}
 
 for which 
 
 
 
 P
 (
 X
 ,
 x
 )
 
 
 {\displaystyle P(X,x)}
 
 is true and 
 
 
 
 
 
 A
 
 
 −
 x
 
 
 {\displaystyle {\mathcal {A}}-x}
 
 to be the set of subsets 
 
 
 
 X
 
 
 {\displaystyle X}
 
 from 
 
 
 
 
 
 A
 
 
 
 
 {\displaystyle {\mathcal {A}}}
 
 for which 
 
 
 
 P
 (
 X
 ,
 x
 )
 
 
 {\displaystyle P(X,x)}
 
 is false, Then 
 
 
 
 
 
 A
 
 
 (
 x
 )
 
 
 {\displaystyle {\mathcal {A}}(x)}
 
 and 
 
 
 
 
 
 A
 
 
 −
 x
 
 
 {\displaystyle {\mathcal {A}}-x}
 
 are disjoint sets, so by the method of summation, the cardinalities are additive<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

|
        
        
          
            A
          
        
        
          |
        
        =
        
          |
        
        
          
            A
          
        
        (
        x
        )
        
          |
        
        +
        
          |
        
        
          
            A
          
        
        −
        x
        
          |
        
      
    
    {\displaystyle |{\mathcal {A}}|=|{\mathcal {A}}(x)|+|{\mathcal {A}}-x|}

Thus the distinguished element allows for a decomposition according to a predicate that is a simple form of a <a href="/facts/Divide_and_conquer_algorithm/pC1X7Ws7">divide and conquer algorithm</a>. In combinatorics, this allows for the construction of <a href="/facts/Recurrence_relation/JolXC71M">recurrence relations</a>. Examples are in the next section.

<h2 id="examples">Examples</h2>
<ul><li>The <a href="/facts/Binomial_coefficient/Tsx7eY5h">binomial coefficient</a> 
 
 
 
 
 
 
 (
 
 
 n
 k
 
 
 )
 
 
 
 
 
 {\displaystyle {n \choose k}}
 
 is the number of size-k subsets of a size-n set. A basic identity—one of whose consequences is that the binomial coefficients are precisely the numbers appearing in <a href="/facts/Pascal%27s_triangle/tb6BKXbc">Pascal's triangle</a>—states that:</li></ul>

(
            
            
              n
              
                k
                −
                1
              
            
            
              )
            
          
        
        +
        
          
            
              (
            
            
              n
              k
            
            
              )
            
          
        
        =
        
          
            
              (
            
            
              
                n
                +
                1
              
              k
            
            
              )
            
          
        
        .
      
    
    {\displaystyle {n \choose k-1}+{n \choose k}={n+1 \choose k}.}

Proof: In a size-(n + 1) set, choose one distinguished element. The set of all size-k subsets contains: (1) all size-k subsets that do contain the distinguished element, and (2) all size-k subsets that do not contain the distinguished element. If a size-k subset of a size-(n + 1) set does contain the distinguished element, then its other k − 1 elements are chosen from among the other n elements of our size-(n + 1) set. The number of ways to choose those is therefore 
 
 
 
 
 
 
 (
 
 
 n
 
 k
 −
 1
 
 
 
 )
 
 
 
 
 
 {\displaystyle {n \choose k-1}}
 
. If a size-k subset does not contain the distinguished element, then all of its k members are chosen from among the other n "non-distinguished" elements. The number of ways to choose those is therefore 
 
 
 
 
 
 
 (
 
 
 n
 k
 
 
 )
 
 
 
 
 
 {\displaystyle {n \choose k}}
 
.
<ul><li>The number of subsets of any size-n set is 2n.</li></ul>
Proof: We use <a href="/facts/Mathematical_induction/KxAPqNrH">mathematical induction</a>. The basis for induction is the truth of this proposition in case n = 0. The <a href="/facts/Empty_set/ffEk3eA6">empty set</a> has 0 members and 1 subset, and 20 = 1. The induction hypothesis is the proposition in case n; we use it to prove case n + 1. In a size-(n + 1) set, choose a distinguished element. Each subset either contains the distinguished element or does not. If a subset contains the distinguished element, then its remaining elements are chosen from among the other n elements. By the induction hypothesis, the number of ways to do that is 2n. If a subset does not contain the distinguished element, then it is a subset of the set of all non-distinguished elements. By the induction hypothesis, the number of such subsets is 2n. Finally, the whole list of subsets of our size-(n + 1) set contains 2n + 2n = 2n+1 elements.
<ul><li>Let Bn be the nth <a href="/facts/Bell_number/LXzHyaIF">Bell number</a>, i.e., the number of <a href="/facts/Partition_of_a_set/VeP9g8CA">partitions of a set</a> of n members. Let Cn be the total number of "parts" (or "blocks", as combinatorialists often call them) among all partitions of that set. For example, the partitions of the size-3 set {a, b, c} may be written thus:</li></ul>

a
                b
                c
              
            
            
              
                a
                
                  /
                
                b
                c
              
            
            
              
                b
                
                  /
                
                a
                c
              
            
            
              
                c
                
                  /
                
                a
                b
              
            
            
              
                a
                
                  /
                
                b
                
                  /
                
                c
              
            
          
        
      
    
    {\displaystyle {\begin{matrix}abc\\a/bc\\b/ac\\c/ab\\a/b/c\end{matrix}}}

We see 5 partitions, containing 10 blocks, so B3 = 5 and C3 = 10. An identity states:

B
          
            n
          
        
        +
        
          C
          
            n
          
        
        =
        
          B
          
            n
            +
            1
          
        
        .
      
    
    {\displaystyle B_{n}+C_{n}=B_{n+1}.}

Proof: In a size-(n + 1) set, choose a distinguished element. In each partition of our size-(n + 1) set, either the distinguished element is a "singleton", i.e., the set containing only the distinguished element is one of the blocks, or the distinguished element belongs to a larger block. If the distinguished element is a singleton, then deletion of the distinguished element leaves a partition of the set containing the n non-distinguished elements. There are Bn ways to do that. If the distinguished element belongs to a larger block, then its deletion leaves a block in a partition of the set containing the n non-distinguished elements. There are Cn such blocks.
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Combinatorial_principles/GxrX0smD">Combinatorial principles</a></li>
<li><a href="/facts/Combinatorial_proof/EmUsc3H1">Combinatorial proof</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Petkovšek, Marko; Tomaž Pisanski (November 2002). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers" (PDF). University of Ljubljana Preprint Series. 40 (837): 1–6. Retrieved 12 July 2013. <a href="http://www.imfm.si/preprinti/PDF/00837.pdf" target="_blank">http://www.imfm.si/preprinti/PDF/00837.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Method of distinguished element open-in-new

Method of distinguished element