# Permutation of array.

Let $$E$$ be the set of the first $$x$$ even numbers and $$O$$ the set of the first $$y$$ odd numbers.

(1) How many permutations are there of the set $$E \cup O$$? I think that's just $$(x+y)!$$.

(2) How many permutations are there such that the last element of $$E$$ appears at an odd position?

Examples.

$$[1,2,3,4,5]$$ doesn't count since $$4$$ occurs at position $$4$$.

$$[4,1,2]$$ counts since $$2$$ is at position $$3$$.

$$[2,1,5,3]$$ counts since $$2$$ is at position $$1$$.

Original post:

Suppose we have an array of length z. Which consists of x different even numbers and y different odd numbers. So $$x \in [2_1,4_2,6_3 \dots (2n)_x]$$ and $$y \in [1_1,3_2,5_3 \dots (2n+1)_y]$$

So z = x+y.

We also know that x => 1 always applies.

1st question: How many different arrays of length z there are. That should be exactly $$z!$$ many or?

2nd question: How many different arrays are there so that the last even number in the array is on an odd index. (The array in this example starts with index 1)

Examples:

1) [1,2,3,4,5] This array has length 5. The last even number in the array is 4 and has index 4 in the array, so we don't count such an array.

2) [52,3,14]. The last even number in this array is 14 and has index 3. So such an array counts towards it.

3) [52,3,5,7]. The last even number in this array is 52 and has index 1. So such an array counts towards it.

• For your first question, shouldn't there be an endless amount of ways to create an array of length $z$ with $x\geq1$ even numbers and $y=z-x$ odd numbers? For example, take $z=3$, then we can take the arrays $[1,3,2],[1,3,4],[1,3,6],[1,3,8],\cdots$ which is an endless list of arrays of length 3 with at least one even number. – gd1035 Nov 24 '18 at 20:05
• @gd1035 You're right. I have expressed myself unclearly. Meaning that the set from which x comes and the set from which y comes is fixed. I edited my post. I hope now its clear what i mean. – faefr Nov 24 '18 at 20:08
• @faefr I've taken the liberty of rephrasing your interesting question. If I got it wrong, sorry, and just roll back the edit. – Ethan Bolker Nov 24 '18 at 20:27
• @EthanBolker Thank you. I think your formulation is much better! – faefr Nov 24 '18 at 20:30

Ok after reading the comment I believe you want to count (in your first question) arrays of length $$z$$ whose entries are the first $$x$$ even numbers and the first $$y$$ odd numbers, in some order, for some $$x, y$$ that add up to $$z$$.

Now for each value of $$x$$ the set of available numbers is fixed, and the number of orders in which these numbers can be written is indeed $$z!$$ as you write. However, picking a different value of $$x$$ we get a different set of numbers and hence another $$z!$$ arrays. If we exclude the cases where $$x = 0$$ or $$y = 0$$ there are $$(z-1)z!$$ different arrays: each of the $$z - 1$$ possibilities for $$x$$ (1, 2, \ldots, z-1) yields $$z!$$ arrays. I'll illustrate this for $$z = 5$$.

$$x = 1$$ gives the set $$\{2, 3, 5, 7, 9\}$$ which gives rise to 120 arrays

$$x = 2$$ gives the set $$\{2, 4, 3, 5, 7\}$$ which gives rise to another 120 arrays

$$x = 3$$ gives the set $$\{2, 4, 6, 3, 5\}$$ which gives rise to another 120 arrays

$$x = 4$$ gives the set $$\{2, 4, 6, 8, 3\}$$ which gives rise to another 120 arrays

So for $$z = 5$$ we have $$(z-1)z! = 480$$ different arrays. If we do allow arrays in which all numbers are even or all numbers are odd $$x = 0$$ and $$x = z$$ are added to the team and the total number of arrays becomes $$(z+1)z! = (z+1)!$$

If you can tell me whether I understood the question correctly, I will edit in the answer to the second question.

EDIT: the edit of your question appeared while I typed this. Obviously the editor interpreted your question 1 in a different way from what I did. For that version of the question your answer $$(x + y)!$$ is of course correct.

EDIT 2: I'll type the answer to question 2 in the interpretation of the edited post. To get to the answer in my original interpretation you can simply multiply with $$z-1$$, as was the case with question 1 as well.

So... Let $$(a)_b$$ denote the product of $$b$$ subsequent descending numbers starting at $$a$$, so $$(10)_3 = 10 \cdot 9 \cdot 8$$, $$n! = (n)_n$$ etc. This will simplify notation down the road.

The last even number must occur in position $$x$$ or higher. If $$x$$ and $$y$$ are both even there are $$y/2$$ odd numbered position that satisfy this constraint: positions $$x+1, x + 3, \ldots, x + (y-1)$$. If $$x$$ is even and $$y$$ is odd there are $$(y+1)/2$$ odd numbered positions available for the last even number: $$x + 1, x+3, \ldots, x+y$$. If $$x$$ is odd and $$y$$ is even there are $$y/2 + 1$$ available spots: $$x, x+2, \ldots, x+y$$ and when $$x$$ is odd and $$y$$ is odd there are $$(y+1)/2$$ available spots. Anyway: let's call the set of possible positions of the last even number $$K$$.

For each number $$k \in K$$ we can count the number of possible permutations where the last even number lands in $$k$$ as follows.

EDIT 3: the following sentences have changed.

There are $$x$$ even numbers that can be the 'last' one, i.e. end up in position $$k$$. Then there are $$x-1$$ even numbers that are somehow distributed over positions $$1, \ldots, k-1$$. This means that number 2 can choose from $$k-1$$ positions, after which number $$4$$ has $$k-2$$ positions left to choose from etc, yielding $$(k-1)_{x-1}$$ possibilities for the non-last even numbers. The $$y$$ odd numbers can then be put in the $$y$$ remaining spots in each of the conceivable $$y!$$ orders. The end result is hence:

$$\sum_{k\in K} x (k-1)_{x-1} y!$$

different arrays. I don't think this sum can be simplified much further, but someone might prove me wrong.

• Thank you for your effort! It is very difficult for me to write in English, so the confusion - sorry. I meant that every element from $E$ and $O$ must appear in the array exactly once. – faefr Nov 24 '18 at 20:39
• I don't understand your notation. Shouldn't it be: $\sum_{k \in K} (k)_x y!$? – faefr Nov 24 '18 at 21:07
• Yes it should be that, I forgot to put { and } around the $k \in K$ – Vincent Nov 24 '18 at 21:09
• For example, we have x∈{2,4} and y∈{1}. Than K=3 and with the formula we get $(3)_2∗1! = 6$ But there are only 4 possible Arrays [2,1,4], ,[4,1,2], [1,2,4] and [1,4,2] or? – faefr Nov 24 '18 at 21:48
• you are right, I'll edit... – Vincent Nov 26 '18 at 7:59