Estoy tratando de resolver esta pregunta de The Book of Proof, y la resolví de una manera diferente a la del autor. La pregunta es la siguiente:
¿Cuántas listas de longitud 6 se pueden hacer a partir de los símbolos si se permite la repetición y la lista está en orden alfabético? (Ej. BBCEGG, pero no BBBAGG).
Mi solución
Como queremos que esto esté en orden alfabético, debemos pensar en cuál es la letra inicial. Si la letra inicial es entonces somos libres de elegir tantas veces después de eso. si elegimos ser nuestra primera carta que nunca podremos elegir en esa lista.
Usando "estrellas y barras", digamos que elegimos ser nuestra primera letra, entonces tenemos más puntos de nuestra selección de símbolos. Así, tenemos estrellas y barras, .
Usando la misma idea para elegir siendo la primera letra, tenemos más lugares para llenar, pero no podemos elegir . Esto lleva a la consecuencia de perder una barra. Entonces tenemos estrellas y ahora barras que conducen a
Continuando con esto eligiendo la primera letra de a obtenemos:
Solución de los autores:
Cualquier lista de este tipo corresponde a un conjunto múltiple de 6 elementos hecho a partir de los símbolos . Por ejemplo, la lista AACDDG corresponde al multiconjunto . Por lo tanto, el número de listas es igual al número de conjuntos múltiples, que es .
Mi pregunta:
¿Es mi solución una forma correcta de usar estrellas y barras?
La forma en que el autor lo resolvió, ¿cómo se puede hacer cumplir la idea de que las listas están en orden alfabético sin decirlo explícitamente?
Lo que estás haciendo a partir de la segunda letra es lo mismo que lo que hace el autor a partir de la primera letra. Cuando arreglas la primera letra para que sea y luego aplique estrellas y barras para el resto letras, esencialmente está contando el número de ocurrencias de cada alfabeto de y en letras. Una vez que elija el número de ocurrencias, sus posiciones se fijan en orden alfabético .
Puedes hacer lo mismo empezando por la primera letra. Necesitas letras del alfabeto y con la repetición, cuente el número de ocurrencias de cada uno de ellos. Si el número de veces que ocurren se indica con las letras minúsculas correspondientes, entonces está buscando una solución para,
dónde y son enteros no negativos.
Y eso viene dado por
esta lista de 6 elementos que puede estar formada por el conjunto {A,B,C,D,E,F,G}, se llama multiconjunto, por lo que el número de multiconjuntos de 6 elementos es el número de composición débil de 6 en 7 partes, y ese es el número de soluciones de esta ecuación . tenga en cuenta que la solución (3,2,1,0,0,0,0) significa que elegimos 3 A y 2 B y 1 c, por lo que este conjunto múltiple es AAABBC
como decimos, el número de multiconjuntos de 6 elementos es el número de composición débil de 6 en 7 partes, por lo que es
peterporque