Sin la condición de cuádruples, ¡habría 15! ≈ 1.3 billones de arreglos (el término matemático es permutaciones ). Con la condición de cuádruples, habrá muchos menos.
¿Cuántos cuádruples hay? 15 personas en 4 asientos tendrían [matemática] \ frac {15!} {(15-4)!} = 15 \ cdot 14 \ cdot 13 \ cdot 12 = 32,760 [/ matemática] arreglos.
Con la regla única de cuádruples vigente, ¿cuántos arreglos de asientos hay para 5 asientos? Cualquier disposición dada de cinco personas sentadas incluye dos cuádruples: (abcd) e y a (bcde) . Por lo tanto, cada disposición de cinco representa dos de las permutaciones cuádruples. Por lo tanto, hay percepciones [matemáticas] \ frac {32,760} {2} = 16,380 [/ matemáticas] para 5 personas sentadas.
- ¿Qué significa limitado como sufijo para una empresa?
- ¿Qué debo comenzar primero con estructuras de datos y algoritmos o inteligencia artificial de aprendizaje automático?
- ¿Qué es un algoritmo para el reemplazo de página (memoria virtual) LRU y FIFO?
- ¿Deep Blue fue un algoritmo o una IA o ambos?
- ¿Por qué debería aprender algoritmos antes de entrar en la programación?
¿Qué pasa si hay seis personas sentadas? Cada combinación elimina tres cuádruples de nuestra lista, por lo que hay
[matemáticas] \ frac {32,760} {3} = 10,920 [/ matemáticas]
Permutaciones válidas para seis personas sentadas.
La fórmula parece ser:
[matemáticas] a = \ frac {\ frac {p!} {(ps)!}} {p-s + 1} [/ matemáticas]
donde [math] p [/ math] es el número de personas, [math] s [/ math] es el número de asientos en una sub-disposición única (en nuestro caso, en un cuádruple), y [math] a [ / math] es el número de arreglos de asientos completos. La fórmula se puede simplificar:
[matemáticas] a = \ frac {p!} {(ps)! (p-s + 1)} [/ matemáticas]
[matemáticas] a = \ frac {p!} {(p-s + 1)!} [/ matemáticas]
Por supuesto, [matemática] p [/ matemática] debe ser mayor que [matemática] s [/ matemática] o la ecuación no es beneficiosa porque la regla de sub-disposición / cuádruples no tendría sentido.
Así, con 15 personas y 4 asientos en cada cuádruple:
[matemáticas] a = \ frac {15!} {(15-4 + 1)!} [/ matemáticas]
[matemáticas] a = \ frac {15!} {12!} [/ matemáticas]
[matemáticas] a = 15 \ cdot 14 \ cdot 13 [/ matemáticas]
[matemáticas] a = 2,730 [/ matemáticas]
Te dije que sería mucho menos de 1.3 billones.
Esta es una figura de límite superior; Algunos de estos 2.730 conjuntos podrían no funcionar realmente. No he podido pensar en una forma de determinar el límite inferior. Vea los comentarios para más detalles.
