8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gd1035 Nov 24 '18 at 20:05
  • 1
    $\begingroup$ @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. $\endgroup$ – faefr Nov 24 '18 at 20:08
  • $\begingroup$ @faefr I've taken the liberty of rephrasing your interesting question. If I got it wrong, sorry, and just roll back the edit. $\endgroup$ – Ethan Bolker Nov 24 '18 at 20:27
  • $\begingroup$ @EthanBolker Thank you. I think your formulation is much better! $\endgroup$ – faefr Nov 24 '18 at 20:30
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – faefr Nov 24 '18 at 20:39
  • 1
    $\begingroup$ I don't understand your notation. Shouldn't it be: $\sum_{k \in K} (k)_x y!$? $\endgroup$ – faefr Nov 24 '18 at 21:07
  • $\begingroup$ Yes it should be that, I forgot to put { and } around the $k \in K$ $\endgroup$ – Vincent Nov 24 '18 at 21:09
  • $\begingroup$ 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? $\endgroup$ – faefr Nov 24 '18 at 21:48
  • $\begingroup$ you are right, I'll edit... $\endgroup$ – Vincent Nov 26 '18 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.