Juego firmado

El número de subconjuntos con signo de un conjunto finito dado de${\displaystyle n}$elementos es${\displaystyle 3^{n}}$, una potencia de tres , porque hay tres opciones para cada elemento: puede estar ausente del subconjunto, presente con signo positivo o presente con signo negativo. ^{[ 5 ]} Por la misma razón, el número de subconjuntos con signo de cardinalidad${\displaystyle r}$es

${\displaystyle 2^{r}{\binom {n}{r}},}$

y sumando estos obtenemos un ejemplo del teorema del binomio ,

${\displaystyle \sum _{r}2^{r}{\binom {n}{r}}=3^{n}.}$

Un análogo del teorema de Erdős-Ko-Rado sobre la intersección de familias de conjuntos también se cumple para conjuntos con signos. La intersección de dos conjuntos con signos se define como el conjunto con signos de elementos que pertenecen a ambos y tienen el mismo signo en ambos. Según este teorema, para cualquier colección de subconjuntos con signos de un conjunto,${\displaystyle n}$-conjunto de elementos, todos con cardinalidad${\displaystyle r}$y todos los pares que tienen una intersección no vacía, el número de subconjuntos con signo en la colección es como máximo

${\displaystyle 2^{r-1}{\binom {n-1}{r-1}}.}$

Por ejemplo, una familia intersecante de este tamaño se puede obtener eligiendo el signo de un único elemento fijo y tomando la familia como todos los subconjuntos con signo de cardinalidad${\displaystyle r}$que contienen este elemento con este signo. Para${\displaystyle r\leq n/2}$Este teorema se deduce inmediatamente del teorema de Erdős-Ko-Rado sin signo, ya que las versiones sin signo de los subconjuntos forman una familia que se interseca y cada conjunto sin signo puede corresponder a como máximo${\displaystyle 2^{r-1}}$conjuntos con signo. Sin embargo, para valores mayores de${\displaystyle r}$Se necesita una prueba diferente. ^{[ 3 ]}