Número de cadenas, cuando cada carácter debe aparecer incluso veces

Question

Estaba leyendo esta pregunta en programadores.StackExchange y quería probar un enfoque combinatorio para resolver el siguiente problema:

Dejemos que $S=\{A,B,C,D\}$ sea un conjunto de caracteres y $n$ un natural positivo, encontrar el número de cadenas de longitud $n$ compuesto por caracteres en $S$ de tal manera que cada carácter ocurra incluso veces.

He intentado resolverlo por mi cuenta pero estoy atascado y agradecería una pista para resolver este tipo de problemas. Además, hay preguntas similares en este sitio para no exactamente el mismo problema, pero no he encontrado una respuesta que podría ayudarme.

Intento actual

En primer lugar, cuando $n$ es impar, el resultado debe ser cero. Una cadena que satisfaga la propiedad deseada tendría necesariamente una longitud par, como permutación de la concatenación de subcadenas de longitudes pares (siendo cada subcadena un carácter de $S$ repetirad veces pares).

Ahora, supongamos que $n$ está en paz.

Si tenemos un mapeo $c$ de $S$ a $\mathbb{N}$ asignando el número de apariciones de cada carácter (por ejemplo $c_A=0, c_B=2, c_C=4, c_D=0$ ), entonces el número de cadenas $N(c)$ que podemos producir con este mapeo sería una k-permutación de caracteres, ya que elegimos una cadena de tamaño $n$ con $c_A$ veces $A$ , $c_B$ veces $B$ etc..:

$$N(c) = \frac{n!}{c_A! c_B! c_C! c_D!}$$

Además, puedo evaluar el número de tales mapeos $c$ : esto equivale a encontrar el número de cadenas en las que los caracteres aparecen en orden con ocurrencias variables. Por ejemplo, con $n=4$ :

$$\begin{array}{c|cccc} & c_A & c_B & c_C &c_D \\ \hline AAAA & 4 & 0 & 0 & 0 \\ AABB & 2 & 2 & 0 & 0 \\ AACC & 2 & 0 & 2 & 0 \\ \dots\\ \end{array} $$

El número de cadenas de tamaño $n$ con un número par de cada carácter es exactamente igual al número de cadenas de tamaño $k=n/2$ con caracteres simples (imagina que AA, BB, CC, DD son caracteres). Así, el número de mapeos es el número de combinaciones de caracteres de $S$ con repetición, como los siguientes con $k=2$ :

AA AB AC AD
BB BC BD
CC CD
DD

Eso se da como $k$ -combinación de 4 elementos:

$$ N_{mapping}(k) = \binom{|S|+k-1}{k} = \binom {3+k}{k}$$

Aquí es donde estoy atascado. Quería combinar este número de mapeos con el número de permutaciones computadas por cada mapeo, previamente, pero no puedo ( $N(c)$ depende de los valores reales del mapeo $c$ ). Además, estoy seguro de que hay un enfoque más directo, pero no sé cómo proceder. Gracias por cualquier ayuda que me puedan proporcionar.

Answer 1

Dejemos que $m=|S|$ sea el número de caracteres distintos, y sea $a_n$ sea el número de cadenas en $S^n$ teniendo un número par de cada carácter en $S$ . Sea

$$g(x)=\sum_{n\ge 0}\frac{a_n}{n!}x^n$$

sea la función generadora exponencial (feg) para $\langle a_n:n\in\Bbb N\rangle$ . (El egf es necesario porque el orden de los caracteres es importante.) El egf para la secuencia dada por $$a_n=\begin{cases}0,&\text{if }n\text{ is odd}\\1,&\text{if }n\text{ is even}\end{cases}$$ es

$$\sum_{n\ge 0}\frac1{(2n)!}x^{2n}=\frac12(e^x+e^{-x})\;,$$

así que

$$g(x)=\left(\sum_{n\ge 0}\frac1{(2n)!}x^{2n}\right)^m=\frac1{2^m}(e^x+e^{-x})^m\;.$$

Ahora

$$\begin{align*} (e^x+e^{-x})^m&=\sum_{k=0}^m\binom{m}ke^{kx}e^{-(m-k)x}\\\\ &=\sum_{k=0}^m\binom{m}ke^{(2k-m)x}\\\\ &=\sum_{k=0}^m\binom{m}k\sum_{n\ge 0}\frac{(2k-m)^n}{n!}x^n\\\\ &=\sum_{n\ge 0}\frac1{n!}\left(\sum_{k=0}^m\binom{m}k(2k-m)^n\right)x^n\;, \end{align*}$$

así que

$$a_n=\frac1{2^m}\sum_{k=0}^m\binom{m}k(2k-m)^n\;.\tag{1}$$

Tenga en cuenta que $2(m-k)-m=m-2k=-(2k-m)$ Así que $(1)$ es de hecho $0$ cuando $n$ es impar. Cuando $n$ es par y positivo podemos reescribir $(1)$ como

$$a_n=\frac1{2^{m-1}}\sum_{k=0}^{\lfloor m/2\rfloor}\binom{m}k(m-2k)^n\;.$$

Por ejemplo, si $m=4$ entonces

$$\begin{align*} a_{2n}&=\frac18\left(\binom40(4-0)^{2n}+\binom41(4-2)^{2n}+\binom42(4-4)^{2n}\right)\\\\ &=\frac18\left(4^{2n}+4\cdot2^{2n}\right)\\\\ &=\frac18\left(4^{2n}+4^{n+1}\right)\\\\ &=2\cdot4^{n-1}\left(4^{n-1}+1\right)\;. \end{align*}$$

Answer 2

A este problema se le pueden aplicar funciones generadoras. Sin embargo, como el orden de las letras en una cadena es importante, las funciones generadoras exponenciales son adecuadas (no las ordinarias). Así, supongamos que el alfabeto $S$ tiene $m$ cartas y dejar que $a_n$ sea el número de cadenas de longitud $n$ sobre el alfabeto $S$ con un número par de cada letra. Sea $g(x)=\sum_{n\ge0}\frac{a_n}{n!}x^n$ sea la función generadora exponencial de $\langle a_n:n\ge0\rangle$ . Entonces, $$g(x)=\left(\sum_{n\textrm{ even}}\frac{x^n}{n!}\right)^m=\left(\frac{e^x+e^{-x}}2\right)^m.$$

En el caso de $m=4$ , $g(x)=\frac1{16}(e^{4x}+4e^{2x}+6+4e^{-2x}+e^{-4x})$ . Entonces, $a_n=\left[\frac{x^n}{n!}\right]g(x)$ y si $n$ está en paz, $a_n=\frac{n!}{16}\left(\frac{2\cdot4^n}{n!}+\frac{8\cdot2^n}{n!}\right)=\frac18(4^n+4\cdot2^n)$ . En particular, $a_4=40$ .

Nota: según la forma de la solución de $a_n$ Sospecho que hay un argumento combinatorio directo (pero no lo conozco).

Answer 3

Como sugiere Rus May al final de su respuesta, existe una solución combinatoria. A partir de ahora, suponer que $n$ está en paz.

Dejemos que $S$ sea el conjunto de palabras de longitud $n$ donde el número de $A$ más el número de $B$ es par. En consecuencia, para cada palabra de $S$ también tenemos $\#C's+\#D's$ está en paz. En primer lugar, afirmo $S$ representa exactamente la mitad de las palabras en $\{A,B,C,D\}^n$ Es decir, $|S|=4^n/2$ . De hecho, si se toma una palabra en $S$ y cambiar la primera letra de acuerdo con la regla de abajo, entonces se obtiene una palabra que no está en $S$ : $$ A\leftrightarrow C,\qquad B\leftrightarrow D $$ Esta correspondencia entre $S$ y su complemento es una biyección.

Ahora, entre las palabras de $S$ contaremos el número de palabras en las que todas las letras son iguales. Lo hacemos en varios casos:

• Dejemos que $S_{c,d}$ sea el conjunto de palabras en $S$ que consisten únicamente en las letras $C$ y $D$ . En exactamente la mitad de estas palabras, tanto $C$ y $D$ aparecen uniformemente (¿por qué?). Por lo tanto, hay $2^{n-1}$ todo-incluso las palabras en $S_{c,d}$ .

• Del mismo modo, dejar que $S_{a,b}$ sea el conjunto de palabras en $S$ hecho de $A$ y $B$ solo, hay $2^{n-1}$ todo-incluso las palabras en $S_{a,b}$ .

• Sólo quedan las palabras que tienen al menos una $A$ o $B$ y al menos una vez $C$ o $D$ . Afirmo que exactamente una cuarta parte de estas palabras tienen todas las letras que aparecen uniformemente. De hecho, podemos dividir estas palabras en grupos de cuatro, en los que exactamente una palabra de cada grupo tiene todas las letras que aparecen uniformemente. El grupo que contiene $w$ consiste en...

  • $w$ sí mismo.
  • La palabra formada al encontrar la primera ocurrencia de $A$ o $B$ en $w$ y sustituirla por la otra letra ( $B$ o $A$ ). Llama a esta nueva palabra $T_{a,b}(w)$ , donde $T$ significa "toggle".
  • La palabra $T_{c,d}(w)$ donde en lugar de ello, se alterna la primera $C$ o $D$ .
  • La palabra $T_{c,d}(T_{a,b}(w))$ , donde se alterna $A/B$ y $C/D$ .

  Dado que hay $4^n/2-2^{n-1}-2^{n-1}$ palabras en $|S-S_{a,b}-S_{c,d}|$ y exactamente una cuarta parte de ellas son válidas, el número de palabras válidas en este grupo es $$\frac{4^n/2-2^{n-1}-2^{n-1}}4=\tfrac18(4^n-4\cdot 2^n)$$

Sumando todo esto, el número de palabras pares es $2^{n-1}+2^{n-1}+\tfrac18(4^n-4\cdot 2^n)=\frac18(4^n+4\cdot 2^{n})$ .