2
$\begingroup$

1. Consider a uniformly random permutation of the set $\{1, 2, . . . , 77\}$. Define the event $A =$ “in the permutation, both $8$ and $4$ are to the left of $3$”.

What is Pr(A)?

Answer: $1/3$

I am trying to understand why this the answer and the question somewhat. I can understand that the possibilities for the permutation would be

$8-4-3$ and,
$4-8-3$.

Since there are $2$ such permutations, we have $Pr(A) = \frac{2}{3!} = 1/3$.

Why are we dividing by $3!$ in $\frac{2}{3!}$ ?
The set has $77$ elements, so shouldn't the denominator be $77!$? When I read this question, there would be $1$ spot in the random $77$-element permutation where there is a $3$, then everything to the left of that would contain an $8$ and $3$, but they don't necessairly have to be next to eachother as long as they are to the left of $3$. Since it's a random permutation of $77$ elements, what if $3$ lands as the first element? $8$ and $4$ would have no where to go.

2. Let $n \ge 2$ be an integer. Consider permutations $a_i,a_2,...,a_n$ of the set $\{1,2,..., n\}$ for which $a_1 < a_2$.

How many such permutations are there?

Answer: $\frac{n!}{2}$

Here is my intuition. I would like to know how to arrive to this answer. The first two elements can be

$(1,k), 2 \le k \le 6 \implies$ 5 ways, or
$(2,k), 3 \le k \le 6 \implies$ 4 ways, or
$(3,k), 4 \le k \le 6 \implies$ 3 ways, or
$(4,k), 5 \le k \le 6 \implies$ 2 ways, or
$(5,6) \implies$ 1 way.

This comes out to $5!$, but $5!$ also counts the pairs the other way around, so we divide by $2$ to get

$\frac{5!}{2} = \frac{(n-1)}{2}$

Why is it $\frac{n!}{2}$?

$\endgroup$
  • 2
    $\begingroup$ For the first question, you could indeed choose to have the denominator be $77!$ at which point your numerator should count how many permutations of all 77 elements satisfy your desired condition. By first picking the three positions occupied by $8,4,3$ and then picking where everything else is, and then picking which order $8,4,3$ appear in, we arrive at an answer of $\frac{\binom{77}{3}\cdot 2\cdot 74!}{77!}$ which simplifies quite nicely to $\frac{1}{3}$, agreeing with our earlier method. $\endgroup$ – JMoravitz Apr 21 '18 at 20:25
  • 1
    $\begingroup$ The main point to take away from this is... although you can choose to have a very descriptive sample space, you do not need to have an overly descriptive sample space. So long as whatever collection of outcomes you have in your sample space are equally likely to occur and the event you wish to find the probability of can be expressed as a set of outcomes from the sample space, then you may use a more efficient smaller sample space & counting methods to proceed and the fewer things in the sample space the easier the arithmetic becomes (though it may become conceptually more difficult). $\endgroup$ – JMoravitz Apr 21 '18 at 20:30
  • 1
    $\begingroup$ The same idea can be used for the second problem. Letting our sample space consist of information only about $a_i$ and $a_2$, we should find that there are $n\cdot (n-1)$ possible equally likely outcomes, $\binom{n}{2}$ of which have $a_i$ less than $a_2$, giving us that it occurs with probability $\frac{1}{2}$, implying that half of the permutations have this property, i.e. $\frac{n!}{2}$ such permutations have this property. $\endgroup$ – JMoravitz Apr 21 '18 at 20:35
  • 1
    $\begingroup$ Sometimes problems are designed specifically so that numbers get very large but simplify nicely precisely to encourage pen-and-paper approaches. Other times they may be designed to have very large numbers because seeing it in an unsimplified form gives insight as to the thought process behind the answer and the unsimplified form is far more useful of an answer than a simplified form. A good question in my opinion is always answerable without a calculator. $\endgroup$ – JMoravitz Apr 21 '18 at 20:43
  • 2
    $\begingroup$ Choose the value for $a_1$. You have $n$ choices. Choose the value for $a_2$. You have $(n-1)$ choices. Apply multiplication principle of counting to see there are $n(n-1)$ possible. Compare this to having chosen both of the values for $a_1$ and $a_2$ simultaneously and remembering that there is only one way to order the cards in ascending order to get there are $\binom{n}{2}$ ways to select the values for $a_1,a_2$ where $a_1<a_2$. Taking the ratio simplifies to $\frac{1}{2}$. $\endgroup$ – JMoravitz Apr 21 '18 at 21:18
1
$\begingroup$

For question 1, you uniformly draw a permutation of the numbers $\{1,2,\ldots,77\}$. As you write, the order of the numbers $3$, $4$, and $8$ in this permutation will be one of the following $3!$ options. $$3, 4, 8$$ $$3, 8, 4$$ $$4, 3, 8$$ $$4, 8, 3$$ $$8, 3, 4$$ $$8, 4, 3$$ As our choice is uniform, each possibility is equally likely, and since exactly two of them has both $8$ and $4$ to the left of $3$, you get $P(A) = \frac{2}{3!} = \frac{1}{3}$.

For question 2, it looks like you are not counting the permutations correctly. For instance, if $n=6$, and if $a_1$ occupies the $5$th position, then $a_2$ has to occupy the $6$th position - but there is not just one permutation that fulfills this, there are $4!$, since the first four positions can be permuted at will.

The answer is $\frac{n!}{2}$, because in any of the $n!$ permutations of $\{1,2,\ldots,n\}$, we have either $a_1<a_2$ or $a_2<a_1$, and because of uniformity, exactly half of them will have $a_1<a_2$.

$\endgroup$
1
$\begingroup$

Yes, there are 77 numbers in the set so 77! permutations- but that is not at all relevant! Instead look at "3", "4", and "8". There are 3!= 6 permutations of those 3 numbers only. We can list them: 348, 384, 438, 483, 834, and 843. In two of them, 483 and 843, a proportion of 1/3, have "4 and 8 before 3". In all 77! of the permutations, all possible permutations of "348" also appear with "3 and 4 appear before 3" in 1/3 of them.

$\endgroup$
  • $\begingroup$ This makes much more sense now. Thank you for clearing up the first question! $\endgroup$ – udpcon Apr 21 '18 at 20:40

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.