Quem pode listar mais strings de determinados alfabetos?

Aug 19 2020

Esta é uma pergunta que foi feita por um dos membros, mas foi rejeitada porque ele não mostrou sua tentativa de resolvê-la. Ele acrescentou isso mais tarde e os votos negativos foram retirados. Eu respondi a pergunta, mas por algum motivo, OP excluiu a postagem rapidamente depois disso, então não pude adicionar nenhum comentário. Enquanto estava resolvendo o problema, encontrei algo interessante sobre o qual queria alguns insights e é por isso que estou postando com detalhes adicionais.

Questão: Pessoa$1$ lista todas as sequências de comprimento possíveis $2x$, de modo que cada letra é uma de $A, B$, e cada string contém o mesmo número de $A's$ e $B's$.

Pessoa $2$ lista todas as sequências de comprimento possíveis $x$, de modo que cada letra é uma de $A, B, C, D$ e cada string contém o mesmo número de $A's$ e $B's$ ($A = B = 0$ ou $C = 0$, $D = 0$ são autorizadas).

Minha solução:

Pessoa $1$:
Número de strings de comprimento$2x$ de igual número de $A$ e $B$ ($x$ cada) $ = M(2x) = \dfrac {(2x)!}{x!x!}$, ($x \in \mathbb {Z+}$)

Pessoa $2$:

nós podemos começar de $A = B = 0$. Cada alfabeto na string pode ter um valor de$C$ ou $D$ independentemente.

$N(0) = 2^x$

Para $A = B = 1, N(1) = {^x}P_2 \times 2^{x-2}$

Para $A = B = 2, N(2) = \dfrac {{^x}P_4}{2!2!} \times 2^{x-4}$

Para $A = B = k, 2k \le x, N(k) = \dfrac {{^x}P_{2k}}{k!k!} \times 2^{x-2k}$

Dizer, $n = \left\lfloor\dfrac{x}{2}\right\rfloor$, Onde $n$ é o maior número inteiro menor ou igual a $\dfrac{x}{2}$.

$N(x) = \sum \limits_{k = 0}^{n}N(k) = \sum \limits_{k = 0}^{n} \dfrac {{^x}P_{2k}}{k!k!} \times 2^{x-2k}$

Eu verifiquei e percebi $M(2x) = N(x)$ para $2 \le x \le 5$.

Então, a pergunta que eu tenho, isso só está acontecendo para valores menores de $x$ ou o que está abaixo é verdade?

$\sum \limits_{k = 0}^{n} \dfrac {{^x}P_{2k}}{k!k!} \times 2^{x-2k} = \dfrac {(2x)!}{x!x!}$, Onde $n$ é o maior número inteiro menor ou igual a $\dfrac{x}{2}$.

Se for verdade, compartilhe algumas referências ou dica sobre como devo proceder com a prova.

Respostas

3 RossMillikan Aug 19 2020 at 14:06

Você pode definir uma bijeção entre os dois. Pegue uma corda de comprimento$2x$e dividi-lo em pares de letras. Substituir$AA$ com $A$, $BB$ com $B$, $AB$ com $C$ e $BA$ com $D$. Você cria uma string correspondente de comprimento$x$ com um número igual de $A$areia $B$s.