Problema general de recuento. No estoy seguro de cómo proceder.

Question

El Sr. Popular tiene siete amigos. Quiere contar el número de maneras en que puede invitar a un subconjunto diferente de 3 de sus amigos a cenar en 7 noches seguidas, siempre que cada pareja de amigos esté junta sólo para 1 cena.

He intentado dividir este problema en otros más pequeños. Esto es lo que tengo hasta ahora: He creado una tabla para mostrar una posible colección de sus triples s.t. no 2 amigos están emparejados más de una vez.

$$ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix} $$

No parece que pueda utilizar el comando de LaTeX "\bordermatrix", así que por favor tenga paciencia conmigo mientras explico lo que significa la matriz. Las columnas deben estar etiquetadas del 1 al 7 (representando cada tarde). Las filas las he etiquetado como $a, b, c, d, e, f, g$ (amigos). A " $1$ " sólo significa que están seleccionados. Así que la primera noche (primera columna), los amigos $a, b,$ y $c$ están cenando con el Sr. Popular.

Así que si pudiera averiguar cuántas colecciones hay, entonces podría multiplicarlo por $7!$ donde 7 son los arreglos de 1 colección. No creo que deba intentar averiguar a mano cuántas colecciones diferentes hay, pero por lo demás estoy atascado. Así que lo que piense en la respuesta debería ser

$$ (\text{number of collections}) \cdot 7! $$

Answer 1

Está buscando el número de Sistemas triples Steiner sobre 7 elementos en los que los vértices se etiquetan como invitados y los triángulos se ordenan como tardes.

Hasta el isomorfismo, sólo hay 1 sistema triple de Steiner de orden 7. A partir de él, podemos generar $7!^2$ (no necesariamente distintos) esquemas de invitación (permutando los invitados y permutando el orden de las veladas). Este sistema triple de Steiner tiene un grupo de automorfismo de orden 168, por lo que hay $7!^2/168=30 \cdot 7!$ posibles esquemas de invitación.

He generado los 30 posibles esquemas de invitación no equivalentes utilizando GAP . Este es el resultado:

1: 123 145 167 246 257 347 356 
2: 123 145 167 247 256 346 357 
3: 123 146 157 245 267 347 356 
4: 123 146 157 247 256 345 367 
5: 123 147 156 245 267 346 357 
6: 123 147 156 246 257 345 367 
7: 124 135 167 236 257 347 456 
8: 124 135 167 237 256 346 457 
9: 124 136 157 235 267 347 456 
10: 124 136 157 237 256 345 467 
11: 124 137 156 235 267 346 457 
12: 124 137 156 236 257 345 467 
13: 125 134 167 236 247 357 456 
14: 125 134 167 237 246 356 457 
15: 125 136 147 234 267 357 456 
16: 125 136 147 237 246 345 567 
17: 125 137 146 234 267 356 457 
18: 125 137 146 236 247 345 567 
19: 126 134 157 235 247 367 456 
20: 126 134 157 237 245 356 467 
21: 126 135 147 234 257 367 456 
22: 126 135 147 237 245 346 567 
23: 126 137 145 234 257 356 467 
24: 126 137 145 235 247 346 567 
25: 127 134 156 235 246 367 457 
26: 127 134 156 236 245 357 467 
27: 127 135 146 234 256 367 457 
28: 127 135 146 236 245 347 567 
29: 127 136 145 234 256 357 467 
30: 127 136 145 235 246 347 567

Los demás esquemas de invitación pueden generarse a partir de éstos permutando el orden de las veladas.

Answer 2

Para complementar la respuesta de @DouglasSStones, "el" plano proyectivo de orden 7 (siete puntos y siete "líneas" de tres puntos cada una) se conoce como el plano de Fano :

Podemos esbozar un argumento de por qué este "diseño en bloque" es único hasta el isomorfismo (mapas que preservan las líneas y la incidencia). Dados siete puntos, pedimos bloques ("líneas") que contengan tres puntos cada uno, que cualquier par de puntos determine una línea (existe un único bloque que contiene ese par) y que dos líneas cualesquiera se crucen exactamente en un punto.

De ello se deduce que dos bloques distintos son disjuntos o comparten exactamente un punto. Si sumamos el número de puntos de todas las líneas, obtenemos el triple de líneas. Pero cada punto pertenece a tres líneas, ya que al eliminar ese punto de las líneas incidente divide los seis puntos restantes en tres pares disjuntos. Por lo tanto, tres veces el número de líneas también cuenta cada punto tres veces, lo que demuestra que el número de líneas es igual al número de puntos: siete.

Dado que un punto dado $X$ pertenece a sólo tres líneas, hay exactamente cuatro bloques que se saltan el punto $X$ . Para dicho punto $X$ fija tres líneas que se encuentren $X$ y dos puntos más, digamos $\{X,A_1,A_2\}$ , $\{X,B_1,B_2\}$ , $\{X,C_1,C_2\}$ . Tenemos que demostrar los seis puntos distintos de $X$ puede organizarse en cuatro bloques esencialmente de una sola manera, es decir, hasta un reetiquetado de puntos.

Cada uno de esos cuatro bloques contiene un punto (no $X$ ) de cada una de esas tres líneas. Intercambie los subíndices de las etiquetas según sea necesario para que $\{A_1,B_1,C_1\}$ es uno de ellos. Como este último bloque debe encontrarse con cada uno de los otros tres bloques finales en exactamente $\{A_1,B_2,C_2\}$ , $\{A_2,B_1,C_2\}$ , $\{A_2,B_2,C_1\}$ .

Este esquema también explica que el grupo de automorfismo sea de orden 168. Podemos mapear el punto $X$ a un punto $Y$ en el plano de Fano de siete maneras. Las tres líneas que se encuentran $X$ pueden asignarse a las tres líneas respectivas que se reúnen $Y$ en $6 = 3!$ formas. Por último, si elegimos una de las cuatro líneas que no cumplen $Y$ ser la imagen de $\{A_1,B_1,C_1\}$ el resto de la correspondencia es forzada. Por lo tanto, se obtiene $7\cdot 6\cdot 4 = 168$ posibles automorfismos.