3
$\begingroup$

How many permutations do the numbers $1, 2, 3,\dots,n$ have,

a) in which there is exactly one occurrence of a number being greater than the adjacent number on the right of it?

b) in which there are exactly two occurrences of a number being greater than the adjacent number on the right of it?

$\endgroup$
  • $\begingroup$ Sorry for not posting, where I got stuck with the problem, but I happen to know the solution....and I don't think it is sensible to post a problem with an answer, so I'll only post the solution if noone answers in the next month $\endgroup$ – user327929 Apr 15 '16 at 19:25
  • 2
    $\begingroup$ a) Pick any subset of $k$ numbers except $\{1,2,\dots,k\}$. Put that subset first in order of increasing size, followed by the remaining numbers in order of increasing size. Hence the number of permutations is $\sum_{k=1}^{n-1}({n\choose k}-1)=2^n-n-1$. $\endgroup$ – almagest Apr 15 '16 at 19:25
  • $\begingroup$ b) I haven't checked carefully, but following the same idea, the number of perms should be $\sum_{h=1}^{n-2}({n\choose h}-1)\sum_{k=1}^{n-h-1}({n-h\choose k}-1))=2\cdot3^n-(n+6)2^n+n^2+3n+4)/2$ $\endgroup$ – almagest Apr 15 '16 at 19:36
  • $\begingroup$ @almagest your answer for a) seems correct, and while your answer for b) is on the right track, there seems to be a problem. When selecting the numbers for the first subset, it is not enough that they are not all less than all the remaining numbers. They also must not all be less than all the numbers in subset 2. This makes things a bit more complicated. $\endgroup$ – browngreen Apr 15 '16 at 19:54
  • $\begingroup$ @browngreen Call three subsets A,B,C. So we put the elements of A in increasing order, then the elements of B in increasing order, then the remaining elements in increasing order. If A has $h$ elements, they can be anything except the $h$ smallest. Having picked any particular A, if B has $k$ elements they can be anything except the $k$ smallest of the remaining elements (whatever they may be). $\endgroup$ – almagest Apr 15 '16 at 20:03
3
$\begingroup$

a) As mentioned by @algamest, in order to get a desired permutation, you would divide the numbers into two subsets of sizes $k$ and $n-k$, where $k$ can be any integer from $1$ to $n-1$, and list each subset in increasing order. For each size $k$, there are $n\choose k$ possible subsets. However, one of them won't work, namely the subset ($1,2,..,k$).

Therefore, the total number of permutations is $$\sum_{k=1}^{n-1}({n\choose k}-1)=(\sum_{k=1}^{n-1}{n\choose k})-(n-1)$$ In general, it can be shown that $\sum_{k=1}^{n-1}{n\choose k}=2^n-2$ so the solution can be simplified to $$2^n-1-n$$

b) Here we will need to divide the numbers into 3 subsets of sizes $k$, $j$, and $n-j-k$, where $k$ can be any integer from $1$ to $n-2$, and $j$ can be any integer from $1$ to $n-k-1$. Again, we would list the three subsets in order, each in increasing order. For each size $k$ and $j$, there are ${n\choose k}{n-k\choose j}$ possible combinations of subsets.

Here, however, it is a bit more complicated to calculate the number of subset combinations that won't work. There are two possible reasons that a collection of subsets wouldn't work. Either the values in subset 1 are all less than all the values in subset 2, or the values in subset 2 are all less than all the values in subset 3.

Let's first look at the first case. For each possible set of values for $j,k$, there are ${n\choose j+k}$ combinations of which numbers are included in the first two subsets. For each of these combinations, there is one way of splitting that won't work. So we must remove ${n\choose j+k}$ possibilities.

Now let's look at the second case. For each possible set of values for $j,k$, there are ${n\choose k}$ combinations of which numbers are included in the last two subsets, and again for each of these combinations, there is one split up that won't work. So we must remove ${n\choose k}$ possibilities.

We now must consider the cases that have both problems and have been subtracted twice, and therefore must be added once back in. For each possible set of values for $j,k$ there is only one way to have both problems (smallest $k$ numbers in first set, next smallest numbers in second set).

Putting this together, for each possible set of values for $j,k$ we must add $-{n\choose j+k}-{n\choose k}+1$. This gives us a permutation total of $$\sum_{k=1}^{n-2}\sum_{j=1}^{n-k-1}({n\choose k}{n-k\choose j}-{n\choose j+k}-{n\choose k}+1)$$

$\endgroup$
  • $\begingroup$ +1 There must be a slip somewhere because the answer to a) is $2^n-(n+1)$. One can easily see that by a direct combinatorial argument. Take a string of As and B's length $n$. There are $2^n$ such strings. If we exclude the $n+1$ cases where there are either no As, no Bs or all the As come first, then there is an obvious bijection with the required permutations. For example, AABABBA corresponds to $1247356$ (the A's mark the numbers in the first increasing sequence and the B's the numbers in the second). $\endgroup$ – almagest Apr 16 '16 at 13:04
  • $\begingroup$ @almagest Thank you, I corrected the mistake. $\endgroup$ – browngreen Apr 17 '16 at 9:04
3
$\begingroup$

The Eulerian number $\left\langle n\atop m\right\rangle$ is the number of permutations of $[n]$ with $m$ ascents; this is clearly the same as the number of permutations of $[n]$ with $m$ descents. Thus, we want $\left\langle n\atop 1\right\rangle$ for the first problem and $\left\langle n\atop 2\right\rangle$ for the second. The Eulerian numbers satisfy the recurrence

$$\left\langle n\atop m\right\rangle=(n-m)\left\langle {n-1}\atop {m-1}\right\rangle+(m+1)\left\langle {n-1}\atop m\right\rangle\;,$$

with initial values $\left\langle 0\atop 0\right\rangle=1$, $\left\langle 0\atop m\right\rangle=0$ if $m>0$, and $\left\langle n\atop m\right\rangle=0$ if $m<0$. From this (or by other means) it is not hard to determine that

$$\left\langle n\atop 1\right\rangle=2^n-n-1\tag{1}$$

and thence that

$$\left\langle n\atop 2\right\rangle=3^n-(n+1)2^n+\frac{n(n+1)}2\;;\tag{2}$$

the resulting sequences are OEIS A000295 and OEIS A000460, respectively.

The derivation of $(2)$ from $(1)$ is quite tedious; verifying it from the recurrence, on the other hand, is straightforward.

To derive the recurrence, let $\pi=p_1p_2\ldots p_{n-1}$ be any permutation of $[n-1]$. By inserting $n$ into any of the $n$ available slots, we can generate $n$ permutations of $n$. Suppose that we insert $n$ after $p_k$. The number of descents remains unchanged if $k=n-1$, or if $p_k>p_{k+1}$; otherwise it increases by $1$. Thus, the permutations of $[n]$ with $k$ descents arise in two ways:

  • from permutations $p_1p_2\ldots p_{n-1}$ of $[n-1]$ with $m$ descents, by placing $n$ at the end or after some $p_k$ such that $p_k>p_{k+1}$, and
  • from permutations $p_1p_2\ldots p_{n-1}$ of $[n-1]$ with $m-1$ descents, by placing $n$ at the beginning or after some $p_k$ such that $p_k<p_{k+1}$.

There are $\left\langle {n-1}\atop m\right\rangle$ permutations of $[n-1]$ with $m$ descents, and in each there are $m+1$ places to insert the $n$ produce a permutation of $[n]$ with $m$ descents, so the first case accounts for $(m+1)\left\langle {n-1}\atop m\right\rangle$ of the permutation of $[n]$ with $m$ descents.

There are $\left\langle {n-1}\atop {m-1}\right\rangle$ permutations of $[n-1]$ with $m-1$ descents, and in each there are $n-m$ places to insert the $n$ produce a permutation of $[n]$ with $m$ descents, so the second case accounts for $(n-m)\left\langle {n-1}\atop {m-1}\right\rangle$ of the permutation of $[n]$ with $m$ descents. Combining the two cases yields the recurrence.

$\endgroup$

Your Answer

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