Перестановка графов массива

Question

Предположим, у нас есть массив длины z.Который состоит из х разных четных чисел и у разных нечетных чисел.

Итак, z = x + y.

Мы также знаем, что x => 1 всегда применяется.

1-й вопрос: Сколько существует различных массивов длины z?Это должно быть точно z!много или?

2-й вопрос: Сколько существует различных массивов, чтобы последнее четное число в массиве имело нечетный индекс.(Массив в этом примере начинается с индекса 1)

Примеры:

1) [1,2,3,4,5] Этот массив имеет длину 5. Последнее четное число вмассив равен 4 и имеет индекс 4 в массиве, поэтому мы не считаем такой массив.

2) [52,3,14].Последнее четное число в этом массиве равно 14 и имеет индекс 3. Таким образом, такой массив имеет значение для него.

3) [52,3,5,7].Последнее четное число в этом массиве равно 52 и имеет индекс 1. Таким образом, такой массив имеет значение для него.

Я просто не нахожу хорошего подхода к этой проблеме.В частности, мне было бы интересно решение с динамическим программированием.

Answer 1

Чтобы ответить на второй вопрос, нам нужно взглянуть только на перестановки четных / нечетных последовательностей:

eee…eeeooo…ooo
`--,--´`--,--´
   x      y

Количество из них, где последний e находится в нечетной позиции, будет тольконужно умножить на число перестановок среди четных чисел (x!) и количество перестановок среди нечетных чисел.

Итак, теперь давайте перечислим e / o перестановок:

???????eooo…ooo
`--,--´ `--,--´
  i-1     z-i

Для некоторых i в качестве индекса последнего четного числа существует много чисел, которые начинаются с последовательности i-1 цифр, состоящих из x-1 четного и y - (z-i) = i-x нечетногономера.Вы должны быть в состоянии i s в цикле, проверить, является ли x-1 >= 0 && i-x >= 0 && i-x <= y (действительным вообще) и является ли i нечетным, затем суммировать для каждого из этих

(i-1)! / (x-1)! / (i-x)!

Answer 2

По первому вопросу: есть z!массивы, если в массиве нет повторяющихся чисел.Формула следующая: n! / ((N1!) (n2!) (n3!) ... (nz!)), Где n1 - количество разпервое число в массиве повторяется, n2 - количество повторений второго числа .. и т. д.