Relación de recurrencia para el número de permutaciones con restricciones de una combinación de símbolos

Question

Supongamos que tenemos $m+n$ símbolos que $m$ son idénticos y $n$ son distintos. Se requiere encontrar el número de permutaciones de estos $m+n$ símbolos de manera que no haya dos símbolos idénticos juntos. He intentado resolverlo con la ayuda de una relación de recurrencia. Mi razonamiento es el siguiente:

Si $f(m,n)$ es el número requerido de permutaciones las siguientes cosas son obvias : $$f(1,1)=2$$ $$f(1,n)=(n+1)!$$ y condiciones de base similares. Ahora, en el caso general, el primer símbolo puede ser uno de los siguientes $m$ símbolos idénticos o puede ser uno de los $n$ Esto significa que tenemos la siguiente relación de recurrencia $$f(m,n)=n{f(m-1,n-1)+nf(m,n-1)}$$ . En particular, ¿cuál es el valor de $f(4,6)$

¿Es correcto mi razonamiento y, por tanto, la relación de recurrencia anterior? Agradecería enormemente cualquier ayuda.

Answer 1

Sí, tu relación de recurrencia parece correcta. Debe especificar que $f(1, 0) = 1$ en su caso base, sin embargo.

Como nota al margen, es posible que quieras mostrar eso, en general, $$f(m, n) = \binom{n + 1}{m}\times n!$$

Pistas para obtener la fórmula general -

1. ¿De cuántas maneras se puede organizar $n$ ¿puntos distintos?
2. Tenga en cuenta que la organización de $n$ crea artículos $n + 1$ nuevos puntos (es decir, en los extremos y entre cada dos elementos). ¿De cuántas maneras se puede elegir $m$ ¿puntos?
3. ¿De cuántas maneras se puede organizar $m$ ¿artículos idénticos?