Method of distinguished element

In the mathematical field of enumerative combinatorics, identities are sometimes established by arguments that rely on singling out one "distinguished element" of a set.

Let ${\displaystyle {\mathcal {A}}}$ be a family of subsets of the set ${\displaystyle A}$ and let ${\displaystyle x\in A}$ be a distinguished element of set ${\displaystyle A}$. Then suppose there is a predicate${\displaystyle P(X,x)}$ that relates a subset ${\displaystyle X\subsetequ A}$ to ${\displaystyle x}$. Denote ${\displaystyle {\mathcal {A}}(x)}$ to be the set of subsets ${\displaystyle X}$ from ${\displaystyle {\mathcal {A}}}$ for which ${\displaystyle P(X,x)}$ is true and ${\displaystyle {\mathcal {A}}-x}$ to be the set of subsets ${\displaystyle X}$ from ${\displaystyle {\mathcal {A}}}$ for which ${\displaystyle P(X,x)}$ is false, Then ${\displaystyle {\mathcal {A}}(x)}$ and ${\displaystyle {\mathcal {A}}-x}$ are disjoint sets, so by the method of summation, the cardinalities are additive^[1]

${\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 divide and conquer algorithm. In combinatorics, this allows for the construction of recurrence relations. Examples are in the next section.

• The binomial coefficient${\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 Pascal's triangle—states that:

${\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 ${\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 ${\displaystyle {n \choose k}}$.

• The number of subsets of any size-n set is 2ⁿ.

Demostración: Usamos inducción matemática . La base de la inducción es la veracidad de esta proposición en el caso n  =  0. El conjunto vacío tiene 0 elementos y 1 subconjunto, y 2 ⁰  =  1. La hipótesis de inducción es la proposición en el caso n ; la usamos para probar el caso n  +  1. En un conjunto de tamaño ( n  +  1), escojamos un elemento distinguido. Cada subconjunto contiene o no el elemento distinguido. Si un subconjunto contiene el elemento distinguido, entonces sus elementos restantes se eligen entre los otros n elementos. Por la hipótesis de inducción, el número de maneras de hacer eso es 2 ⁿ . Si un subconjunto no contiene el elemento distinguido, entonces es un subconjunto del conjunto de todos los elementos no distinguidos. Por la hipótesis de inducción, el número de tales subconjuntos es 2 ⁿ . Finalmente, la lista completa de subconjuntos de nuestro conjunto de tamaño ( n  +  1) contiene 2 ⁿ  +  2 ⁿ  =  2 ^{n + 1} elementos.

• Sea B _n el n -ésimo número de Bell , es decir, el número de particiones de un conjunto de n elementos. Sea C _n el número total de "partes" (o "bloques", como suelen llamarlos los combinatorialistas) entre todas las particiones de ese conjunto. Por ejemplo, las particiones del conjunto de tamaño 3 { a , b , c } se pueden escribir así:  

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

Vemos 5 particiones, que contienen 10 bloques, por lo que B ₃  =  5 y C ₃  =  10. Una identidad establece:

${\displaystyle B_{n}+C_{n}=B_{n+1}.}$

Demostración: En un conjunto de tamaño ( n  +  1), elijamos un elemento distinguido. En cada partición de nuestro conjunto de tamaño ( n  + 1), o bien el elemento distinguido es un "singleton", es decir, el conjunto que contiene solo el elemento distinguido es uno de los bloques, o bien el elemento distinguido pertenece a un bloque mayor. Si el elemento distinguido es un singleton, entonces su eliminación deja una partición del conjunto que contiene los n elementos no distinguidos. Hay B _n maneras de hacer esto. Si el elemento distinguido pertenece a un bloque mayor, entonces su eliminación deja un bloque en una partición del conjunto que contiene los n elementos no distinguidos. Hay C _n tales bloques. 

• Principios combinatorios
• Prueba combinatoria