Contar elementos en potencia cartesiana con pluralidad + limitaciones patrón

Question

Problema: tengo un alfabeto con n=8 letras (decir $X=\{A, B, C, D, E, F, G, H\}$). Estoy buscando palabras con m=24 letras, con tres limitaciones:

1. letra de $A$ es el de mayoría relativa (en $ABCAAFFHABCAAFFHABCAAFFH$ donde $A$ aparece 9 veces, es decir, más que todas las otras cartas) (podríamos utilizar la "pluralidad" de este concepto).
2. una letra en una posición fija (dos casos: $A$ o de otra letra)
3. el patrón general de la $p$ es fijo (por el patrón, me refiero a $ABCAFHABCAFHABCAFH$ para el ejemplo anterior, es decir, el orden, sin el número de letras) (vamos a definir $p_A$ el número de $A$'s en el patrón. Aquí, $p_A=6$. También vamos a definir $p_{A1}$ el número de $A$'s en el primer intervalo en el patrón. Aquí, $p_{A1}=1$.)

Ejemplo sencillo: con $X=\{A, B, C\}$$n=8$. La pregunta es: ¿cuántos de ocho de la carta de las palabras con un $A$ en la tercera posición (relativa) de la mayoría de $A$'s y el patrón de $BABCA$? Y ¿cuántos tienen un (relativo) de la mayoría de $B$'s?

Solución para el ejemplo sencillo:

1. El fijo $A$ no puede estar en el segundo $A$-intervalo en el patrón: $A$ es la última carta en el patrón, y por lo que la fija $A$ puede ser seguido por otros $A$'s y el patrón no se puede reproducir. Aún así, en casos generales, la fijación de $A$ podría ser en diferentes intervalos.

2. Una vez que hemos decidido que $A$ se encuentra en el primer intervalo, se itera $k$, el número de $A$-letras de la palabra. Debe haber al menos uno en cada intervalo de tiempo, por lo tanto, al menos dos en este ejemplo.

   1. Con $k=2$$k=3$, no hay ningún posible resultado, ya que habría $k$ $A$'s letras y $k-1$ otras letras ( $B$ $C$ ). Ya que hay sólo tres letras, no podemos hacer que un 8 letras de la palabra ($2+1*2, 3+2*2 \leq 8$).

   2. Con $k=4$, el 7 resultados posibles son:

      • $BAAABBCA$
      • $BAAABCCA$
      • $BAABBCAA$
      • $BAABCCAA$
      • $BBABCAAA$
      • $BBAABCAA$
      • $BBAAABCA$
   3. Con $k=5$, hay 3 resultados posibles:
      • $BAAAABCA$
      • $BAAABCAA$
      • $BAABCAAA$

No hay posibilidades de con $k=6$ (no hay espacio para reproducir el patrón: 8 cartas en total, menos del 6 $A$'s, 2 espacios restantes, pero 3 no$A$ sucesos ocurridos en el patrón).

Así, en total, hay 10 posibilidades para este ejemplo sencillo.

¿Cómo puedo empezar a resolver este problema a través de la analítica de la combinatoria? Estoy buscando una expresión general para cualquier modelo.

Respuesta tentativa:

Sólo la restricción (1): Mayoría

La solución es $$\left[\frac{x^{m}}{m!}\right]\sum_{k\ge0} \frac{x^k}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{n-1}$$ A partir de aquí.

Sólo las restricciones (1) y (2): en la Mayoría + Una letra fija

Si fijamos un $A$, la solución es: $$\left[\frac{x^{m-1}}{(m-1)!}\a la derecha] \sum_{k\ge0} \frac{x^{k-1}}{(k-1)!}\izquierda(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{n-1}$$

Si lo arreglamos de otra letra, la solución es: $$\left[\frac{x^{m-1}}{(m-1)!}\a la derecha] \sum_{k\ge0} \frac{x^{k}}{k!}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-1}}{(k-1)!}\right)^{n-2}\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k-2}}{(k-2)!}\right)$$

A partir de aquí.

Todas las restricciones (intento de), caso en el que un $A$ es fijo

1. Fijar el intervalo para el fijo $A$. Número de posibilidades: $$p_A$$
2. Recorrer $k-1$, el número de no determinada $A$'s. Número de posibilidades: $$[t^{m-1}]p_A\sum_{k\ge0} [(k-1)\times A][(k-1)\times \text{other letters}]$$

3. Para cada número posible $k-1$ $A$'s, distribuirlos en los intervalos de $A$'s en el modelo, es decir, distribuir $k-1$ restante de bolas en $p_A$ de las urnas, con una urna ya que contiene un $A$. Todos los demás deben contener al menos un $A$. Número de posibilidades: $$p_A[t^{m-1}]\sum_{k\ge0} (t+t^2+t^3+...)^{p_A-1}(1+t+t^2+...)[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} t^{p_A-1}(1+t^1+t^2+...)^{p_A-1}\frac{t}{1-t}[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} t^{p_A-1}(\frac{t}{1-t})^{p_A-1}\frac{t}{1-t}[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} t^{p_A-1}(\frac{t}{1-t})^{p_A}[(k-1)\times \text{other letters}]=p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}[(k-1)\times \text{other letters}]$$

4. Para cada no-$A$ carta, distribuir más de uno y hasta a $k-1$ veces cada letra en cada intervalo de tiempo. El número de posibilidades (un desarrollo similar se puede encontrar aquí):

\begin{align*}\text{possibilities} & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}\prod_{x\in X, x\neq A} (t+t^2+...+t^{k-1})^{p_x} \\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}\prod_{x\in X, x\neq A} t^{p_x}(1+t+...+t^{k-2})^{p_x}\\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}}\prod_{x\in X, x\neq A} t^{p_x}(\frac{1-t^{k-1}}{1-t})^{p_x}\\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{2p_A-1}}{(1-t)^{p_A}} t^{\sum_{x\in X, x\neq A} p_x}(\frac{1-t^{k-1}}{1-t})^{\sum_{x\in X, x\neq A} p_x} \\ & = p_A[t^{m-1}]\sum_{k\ge0} \frac{t^{\sum_{x\in X, x\neq A} p_x + 2p_A-1}}{(1-t)^{\sum_{x\in X, x\neq A} p_x + p_A}} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x}\\ & = p_A[t^{m-1-\sum_{x\in X, x\neq A} p_x + 2p_A-1}]\sum_{k\ge0} \frac{1}{(1-t)^{\sum_{x\in X, x\neq A} p_x + p_A}} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x} \\ & = p_A[t^{m-1-\sum_{x\in X, x\neq A} p_x + 2p_A-1}]\sum_{k\ge0} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x}\sum_{j\ge 0} \binom{-\sum_{x\in X, x\neq A} p_x + p_A}{j} (-t)^j \\ & = p_A[t^{m-1-\sum_{x\in X, x\neq A} p_x + 2p_A-1}]\sum_{k\ge0} (1-t^{k-1})^{\sum_{x\in X, x\neq A} p_x}\sum_{j\ge 0} \binom{j-1 +\sum_{x\in X, x\neq A} p_x + p_A}{j} t^j\end{align*}

Desde que extraer los coeficientes de $x^{k-1}$, no va a ser $k-1$ no$A$ letras en los intervalos.

El resultado se aplica a la simple ejemplo ($p_A=2, m=8, n=3$):

$$2[t]\sum_{k=1}^8 (1-t^{k-1})^{3} \sum_{j\ge 0}\binom{5+j-1}{j} t^j$$

Answer 1

Se nos da $n$ letras y un patrón de $p$ hacer una $m$ letra de la palabra satisfacer cualquier combinación de las restricciones (1), (2), (3). Cada vez que se considere (1), os dejamos la letra de $A$ el (relativo) de la estricta mayoría. Deje $p_L$ el número de $L$'s en el patrón de $p$ (no es la palabra). Deje $L_i$ ser la ubicación de la $i$th ocurrencia de $L$$p$. Deje $e_k$ ser la exponencial de la función suma. Yo use corchetes $[x^k] \mathcal{f}$ precisamente para indicar el coeficiente de $x^k$ en el poder formal de la serie de $\mathcal{f}$. El compilado soluciones:

$\qquad$ (1) $\qquad$ $\left[\frac{x^{m}}{m!}\right]\sum_{k\ge0} \frac{x^k}{k!}\,(e_{k-1})^{n-1}$

$\qquad$ (2) $\qquad$ $n^{m-1} $

$\qquad$ (3) $\qquad$ ${ m-1 \choose \mid p\mid-1 } $

$\qquad$ (1,2)

$ \qquad \qquad \qquad \text{Fix } \qquad \left[\frac{x^{m-1}}{(m-1)!}\a la derecha] \sum_{k\ge0} \frac{x^{k-1}}{(k-1)!} \,(e_{k-1})^{n-1}$

$ \qquad \qquad \qquad \text{Fix } B \qquad \left[\frac{x^{m-1}}{(m-1)!}\a la derecha] \sum_{k\ge0} \frac{x^{k}}{k!} \; (e_{k-1})^{n-2} \,e_{k-2}$

$\qquad$ (1,3)

$ \qquad \qquad \qquad \left[ x^m \right] \sum_{a=p_A}^m {a-1 \choose p_A - 1} x^a \prod_{L\neq A} \sum_{i=p_L}^{a-1} {i - 1 \choose p_L - 1} x^i $

$\qquad$ (2,3)

$\qquad \qquad \qquad \text{Fix } L \text{ at } k \qquad \sum_{i=1}^{p_L} {k-1 \choose L_i-1} {m-k \choose |p| - L_i}$

$\qquad$ (1,2,3) ? $\tiny{\text{ see special case below}}\\$

---

Una vez que te das cuenta de (3) se obtiene (2,3) mediante la división de la secuencia [1..k][k..m] y poner el $i$th intervalo de $L$ en la posición $k$. Podemos resolver (1,3) por el uso ordinario de la generación de funciones.

(1,3)

$$ \begin{array} ( & \displaystyle \left[ x^m \right]_{\text{given (1)}} \sum_{a=1}^{m} x^a \left[ x^a \right] \left( x+x^2+\ldots \right)^{p_A} \prod_{L \neq A} \left( x + x^2 + \ldots \right)^{p_L} \\ = & \displaystyle \left[ x^m \right] \sum_{a=1}^{m} x^a \left[ x^a \right] \left( \frac{x}{1-x} \right)^{p_A} \prod_{L \neq A} \sum_{i=0}^{a-1} x^i \left[ x^i \right] \left( \frac{x}{1-x} \right)^{p_L} \\ = & \displaystyle \left[ x^m \right] \sum_{a=p_A}^m {a-1 \choose p_A - 1} x^a \prod_{L \neq a} \sum_{i=p_L}^{a-1} {i -1 \choose p_L - 1} x^i \\ \end{array} $$

Nota: el límite superior del exterior suma puede ser tomado como $m-|p|+p_A$ y el límite superior del interior de la suma puede ser tomado como $\min\{a-1, m-a-\mid \!p\! \mid+ \, p_A+p_L\}$.

---

La fórmula anterior no es muy útil desde un punto de vista computacional. Sin embargo, podemos encontrar una fórmula utilizable si añadimos otra restricción. Vamos a 3'de ser el caso especial de restricción 3 , donde no hay letra aparece más de una vez en $p$. Definir

$$ \begin{array} ( \mathcal{I}_{(\kappa,\mu,\eta)} & \displaystyle = \left[ x^{\eta} \right] \left( x + \ldots + x^{\mu-1} \right)^{\kappa} \\ & \displaystyle = \sum_{i=0}^{ \min\left\{\kappa, \left\lfloor \frac{\eta-\kappa}{\mu} \right\rfloor \right\}} (-1)^i {\kappa \choose i} {\eta - 1 - i\,\mu \choose \kappa-1} \end{array} $$

Combinatoria me gusta pensar en esto como el número entero de soluciones a $\sum_{i=1}^{\kappa} x_i = \eta $ donde $1 \leq x_i < \mu$. La razón por la que defina $\mathcal{I}$ es debido a que podemos enmarcar el problema en esos términos. Por ejemplo, (3) = $\mathcal{I}_{(\mid p \mid, m, m)}$. Por último, vamos a $\pi_L$ denotar la posición de $L$$p$. Entonces tenemos

$\qquad$ (1,3') $$ \begin{align} & \left[ x^m \right] \sum_{a=1}^{m} x^{a} \, (x + \ldots + x^{a-1})^{\mid p \mid-1} \\ & = \sum_{a = 1}^m \mathcal{I}_{\left(\mid p \mid - 1,\; a,\; m - a \right)} \end{align} $$

$\qquad$ (1,2,3')

$$ \begin{array} ( & \text{Fix } A \text{ at } k & \; & \displaystyle \sum_{a = 1}^m \sum_{\ell = 1}^{a} \mathcal{I}_{\left( \pi_A - 1, \; a , \; k - \ell \right)} \; \mathcal{I}_{\left( \mid p \mid - \pi_A, \; a, \; m - k - a + \ell \right)} \\ & \text{Fix } B \text{ at } k, \; \pi_B < \pi_A & \; & \displaystyle \sum_{a = 1}^m \sum_{b = 1}^{a - 1} \sum_{\ell = 1}^{b} \mathcal{I}_{\left( \pi_B - 1, \; a , \; k - \ell \right)} \; \mathcal{I}_{\left( \mid p \mid - \pi_B - 1, \; a, \; m - k - a - b + \ell \right)} \\ & \text{Fix } B \text{ at } k, \; \pi_B > \pi_A & \; & \displaystyle \sum_{a = 1}^m \sum_{b = 1}^{a - 1} \sum_{\ell = 1}^{b} \mathcal{I}_{\left( \pi_B - 2, \; a , \; k - a - \ell \right)} \; \mathcal{I}_{\left( \mid p \mid - \pi_B , \; a , \; m - k - b + \ell \right)} \\ & \\ \end{array} $$

Tenga en cuenta que yo uso las variables $a,b$ para especificar el número de $A$'s y $B$'s en la secuencia final. Cuando la fijación de la carta de $L$$k$, $\ell$ iterar especifica el número de $L$'s a la izquierda de la posición $k$ (inclusive). Por último, observe cómo (1,3) se reduce a (1,3') al $p_L = 1$ todos los $L$$p$.