Cuestión de combinatoria y teoría de conjuntos

Question

Cuestión de combinatoria y teoría de conjuntos

Matemáticas
combinatoria
teoría elemental de conjuntos

slimqubit

Problema: Deja $A_n=\{ 1,2,...,n \}$ . Definimos el triplete ordenado $(A,B,C)$ tan bueno si $A \cup B \cup C = A_n$ y $\operatorname{card}(A \cap B \cap C)=2$ (entonces la intersección tiene exactamente $2$ elementos). Dejar $p_n$ sea el número de tales pares interesantes.

¿Existe una fórmula para $p_n$ , y si es así, es la fracción $\frac{p_{n+1}}{p_n}$ ¿constante?

Pregunta: Creé un algoritmo de retroceso muy simple que calculó $p_3=18$ , $p_4=216$ y $p_5=2160$ . No veo ninguna fórmula obvia para esto, ya que puede ser una progresión aritmética. Está claro que el número de intersecciones posibles $A \cap B \cap C$ es $n(n-1)/2$ . Entonces, la pregunta sigue siendo de cuántas maneras posibles podemos organizar tales conjuntos de manera que todos incluyan al menos una vez todos los elementos.

¿Alguien puede arrojar algo de luz sobre qué noción teórica me estoy olvidando y dar una pista para la solución? Cualquier ayuda sería apreciada.

Respuestas (1)

Cuestión de combinatoria y teoría de conjuntos

julio r · Answer 1

La respuesta es $p_n= 6^{n-2}{n\choose 2}$ .

Como notó, todas las posibles intersecciones de $A,B,C$ son los posibles subconjuntos de dos elementos de $\{1,...,n\}$ , que son ${n\choose 2} = n(n-1)/2$ .

Para distribuir el otro $n-2$ elementos que necesitamos para elegir si cada uno de ellos pertenece exclusivamente a

A, B, C,

$A,B,C,$ o para

A \cap B, A \cap C, B \cap C .

$A\cap B,A\cap C,B\cap C.$ Estas 6 posibilidades para cada uno de los restantes

n - 2

$n-2$ los elementos son todos disjuntos y cubren todos los casos posibles exactamente una vez, produciendo el otro factor

6^{n - 2}

$6^{n-2}$ .

Cuestión de combinatoria y teoría de conjuntos

slimqubit

Respuestas (1)

julio r

¿Cuántas permutaciones casi perfectas hay?

Una pregunta sobre un caso especial del principio de inclusión-exclusión

prueba combinatoria de identidad que involucra multiconjuntos

Seleccionar un elemento de cada uno de muchos conjuntos de modo que no haya dos elementos iguales.

t¿De cuántas maneras podemos dividir un conjunto S en dos subconjuntos bajo las siguientes restricciones?

Sea A={1,2,3,4,5,6,7,8,9,0,20,30,40,50}A={1,2,3,4,5,6,7,8 ,9,0,20,30,40,50}A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}. 1. ¿Cuántos subconjuntos de tamaño 2 hay? 2. ¿Cuántos subconjuntos hay en total?

Si A={x1,x2,x3,…,xn}A={x1,x2,x3,…,xn}A= \{ x_1 , x_2 , x_3 , \ldots , x_n \}. ¿Cuántos subconjuntos hay?

Encontrar el elemento N en una lista de todos los números posibles

número de formas de elegir conjuntos de números enteros

¿Cuál es el número mínimo de conjuntos tales que el producto de los elementos en cada uno de ellos sea menor que k?