Кто может перечислить больше строк из заданных алфавитов?
Это вопрос, который задал один из участников, но он был отклонен, поскольку он не продемонстрировал своей попытки решить его. Он добавил, что позже голоса против были отозваны. Я ответил на вопрос, но по какой-то причине OP быстро удалил пост, поэтому я не смог добавить никаких комментариев. Решая проблему, я обнаружил кое-что интересное, о чем мне хотелось получить представление, и по этой причине я публикую это с дополнительными подробностями.
Вопрос: Человек$1$ перечисляет все возможные строки длины $2x$, так что каждая буква является одной из $A, B$, и каждая строка содержит одинаковое количество $A's$ и $B's$.
Человек $2$ перечисляет все возможные строки длины $x$, так что каждая буква является одной из $A, B, C, D$ и каждая строка содержит одинаковое количество $A's$ и $B's$ ($A = B = 0$ или же $C = 0$, $D = 0$ разрешается).
Мое решение:
Человек $1$:
Количество строк длины$2x$ из равного количества $A$ и $B$ ($x$ каждый) $ = M(2x) = \dfrac {(2x)!}{x!x!}$, ($x \in \mathbb {Z+}$)
Человек $2$:
мы можем начать с $A = B = 0$. Каждый алфавит в строке может иметь значение$C$ или же $D$ независимо.
$N(0) = 2^x$
За $A = B = 1, N(1) = {^x}P_2 \times 2^{x-2}$
За $A = B = 2, N(2) = \dfrac {{^x}P_4}{2!2!} \times 2^{x-4}$
За $A = B = k, 2k \le x, N(k) = \dfrac {{^x}P_{2k}}{k!k!} \times 2^{x-2k}$
Сказать, $n = \left\lfloor\dfrac{x}{2}\right\rfloor$, где $n$ - наибольшее целое число, меньшее или равное $\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}$
Я проверил и заметил $M(2x) = N(x)$ за $2 \le x \le 5$.
Итак, у меня вопрос, происходит ли это только для меньших значений $x$ или верно то, что ниже?
$\sum \limits_{k = 0}^{n} \dfrac {{^x}P_{2k}}{k!k!} \times 2^{x-2k} = \dfrac {(2x)!}{x!x!}$, где $n$ - наибольшее целое число, меньшее или равное $\dfrac{x}{2}$.
Если это правда, поделитесь, пожалуйста, некоторыми ссылками или подсказками, как мне продолжить доказательство.
Ответы
Вы можете определить взаимное соответствие между ними. Возьмите строку длины$2x$и разбейте его на пары букв. Заменить$AA$ с участием $A$, $BB$ с участием $B$, $AB$ с участием $C$ и $BA$ с участием $D$. Вы создаете соответствующую строку длины$x$ с равным количеством $A$s и $B$с.