¿Por qué es importante estudiar combinatoria?

Question

Estaba discutiendo con mi amigo Sayan Mukherjee sobre por qué tenemos que estudiar combinatoria que, hay que reconocerlo, no es nuestra asignatura favorita porque vemos muy poca motivación para ello (no digo que no exista motivación para estudiarla, es sólo que yo no la he encontrado).

Estos son algunos de los "usos" de la combinatoria que se nos ocurren:

1. Contar: el número de formas en que podemos realizar una secuencia finita de operaciones y cómo se pueden organizar o seleccionar los objetos. Por ejemplo, el número de formas en que podemos seleccionar $k$ impar y elementos pares del conjunto $S=\{1,2,\dots, 2n\}$ para que en la sección puedan aparecer como máximo 3 elementos Impares consecutivos.

2. Dibujar biyecciones - El clásico Problema de estrellas y barras nos proporciona ideas clave para contar el número de soluciones integrales de ecuaciones de la forma $x_1+x_2+\dots x_n=k$ .

3. El Los siete puentes de Königsberg que me cautivó de niño.

Me he abstenido de mencionar las recursiones y las funciones generadoras, ya que las veo más como herramientas.

Pero estoy buscando más motivación; contar, como se describe en los problemas parece ser la punta del iceberg y apreciaré más ejemplos en los que la combinatoria y la teoría de grafos pueden ser herramientas poderosas. ¿Podemos tener una lista de usos de la combinatoria? No estoy buscando aplicaciones a la industria, sólo matemáticas puras.

No es imprescindible que las respuestas se ajusten al nivel de la escuela secundaria; ¡sin duda, será divertido volver a consultar la información adicional!

Answer 1

Tal y como se solicitó, aquí hay una lista de aplicaciones de la combinatoria a otros temas de las matemáticas puras.

• El recuento se utiliza ampliamente en la demostración original del teorema de Chebyshev, que puede encontrar en el capítulo 5 de (la versión online gratuita de) este libro . El teorema de Chebyshev es la primera parte del teorema de los números primos, un resultado profundo de la teoría analítica de los números.

• En teoría de grupos, el principio de encasillamiento se utiliza para demostrar que cada elemento de un grupo finito tiene un orden. Se podría argumentar que la prueba de que todo dominio integral finito es un campo se deriva de una lógica similar.

• Demostración del teorema del punto fijo de Brouwer mediante el principio de casillero y El lema de Sperner se da aquí .

• ACTUALIZACIÓN: Graphs in Finite Group Theory. Conozco varios ejemplos en los que los gráficos aparecen en la teoría de grupos finitos: gráficos primos , gráficos de grado de carácter y gráficos de desplazamiento . Los gráficos primos (sobre los que he escrito varias respuestas de MSE, por ejemplo $[1]$ , $[2]$ ) se refieren al conjunto de órdenes de elementos en un grupo finito, los gráficos de grados de caracteres tienen que ver con los grados de los caracteres irreducibles de un grupo, y los gráficos de conmutación ilustran qué elementos conmutan con qué otros elementos. $$$$ La mayoría de las veces, la aplicación de la teoría de grafos a la teoría de grupos finitos es lingüística - es decir, estos grafos surgen naturalmente de cuestiones de teoría de grupos que se formulan mejor utilizando el lenguaje de la teoría de grafos. En otras palabras, no es habitual ver teoremas de la teoría de grafos que se utilicen para resolver problemas de la teoría de grupos finitos, incluso cuando dichos grafos son objeto de investigación. A veces, sin embargo, la teoría de grafos también puede aplicarse de forma más directa, como puede verse en este documento de la mía, por ejemplo.

Answer 2

Podríamos preguntarnos: ¿Qué importancia tiene la "importancia"? :)

Pero para una respuesta general más seria a las preocupaciones que quizás subyacen a su pregunta, vale la pena leer esta maravillosa pieza de Sir Timothy Gowers en el que habla de dos culturas o estilos de matemáticas, la resolución de problemas frente a la construcción de teorías, ejemplificadas, según parece a primera vista, por ejemplo, por los combinadores frente a los teóricos de topos (este último es mi ejemplo). Gowers pasa a defender el interés y la importancia matemática de la combinatoria, y trata explícitamente de "contrarrestar la sugerencia de que el tema de la combinatoria tiene muy poca estructura y no consiste más que en un gran número de problemas".

Answer 3

Todo el mundo moderno se basa en algoritmos combinatorios. Si quieres hacer un programa más rápido, necesitas combinatoria. Si quieres entender la programación moderna, necesitas la combinatoria. Sin la combinatoria, algunos programas que ahora tardan una fracción de segundo necesitarían semanas.

Comunicaciones por teléfono móvil -- Códigos de corrección de errores, optimizaciones wavelet y fourier.
Programación de juegos -- optimización de polígonos
Este sitio web -- jerarquías de comentarios

En cualquier lugar en el que haya un centenar de datos o más, que es prácticamente cualquier sitio, tienda, programa, lugar o proyecto, es probable que se utilice algún tipo de mejora combinatoria. Especialmente en los programas. Si es rápido, hay combinatoria ayudando.

Answer 4

Otra aplicación importante de la combinatoria es la teoría de la representación, las funciones simétricas y el estudio de variedades con muchas simetrías (grassmanianos, variedades bandera, variedades tóricas, variedades simétricas, variedades esféricas).

En general, los objetos con suficientes simetrías suelen poder describirse mediante datos discretos (a menudo finitos). La combinatoria entra en juego para parametrizar los datos y, en general, porque las relaciones entre los objetos suelen describirse en términos de combinatoria de los datos.

Como ejemplo sencillo, suponga que quiere estudiar $k$ -subespacios dimensionales de un $n$ -espacio vectorial de dimensiones $V$ . Una forma de entender dicho subespacio $W$ es considerar una "bandera" de $V$ que es una secuencia de subespacios $$0 = V_0 \subset V_1 \subset \dots \subset V_i \subset \dots \subset V_n = V,$$ con $\dim(V_i) = i$ . Se pueden dividir los diferentes subespacios $W$ basado en la secuencia de números débilmente creciente $$0 = \dim(W \cap V_0) \leq \dim(W \cap V_1) \leq \dots \leq \dim(W \cap V_i) \leq \dots \leq \dim(W \cap V_n) = k,$$ con la restricción de que en cada etapa la dimensión sólo puede subir 1 o permanecer igual. Una forma equivalente de describir la posición de $W$ relativa a la bandera es dar una secuencia de longitud $n$ que consiste en $k$ 1 y $n-k$ 0's, con un $1$ que se produce en el $i$ -a la posición exacta cuando $\dim(W \cap V_i) > \dim(W \cap V_{i-1})$ .

Una simple observación es que el número de "celdas" diferentes en que se han dividido los subespacios es igual a $n \choose k$ ya que esto cuenta el número de tales cadenas de 0's y 1's. Esto es sólo el principio de una rica interacción entre combinatoria y geometría. La moraleja es que si quieres estudiar un objeto con simetrías, es muy probable que encuentres alguna combinatoria interesante por el camino.

Answer 5

Has omitido las estadísticas. Si se trata de conjuntos finitos de eventos posibles, muchas cuestiones estadísticas se reducen a la combinatoria. Si, por ejemplo, tienes $n$ variables aleatorias $X_n$ con dominios finitos, y queremos encontrar la distribución de $X_1+\ldots+X-n$ Hay que averiguar de qué manera los posibles resultados de $X_1,\ldots,X_n$ puede sumar un valor específico.

Mucha de la combinatoria de la escuela secundaria se hace con estas aplicaciones en mente, es decir, el infame

Tú eliges fulano de tal muchos objetos de una urna que contiene esto y aquello ¿cuál es la probabilidad de que haya escogido objetos con alguna-propiedad-de-selección