0

If $n$ is an integer, how many permutations are less than, equal to and greater than $n$?

For example if $n=24335$, $43325\gt n$, $23345\lt n$, etc...

JMP
  • 21,771
  • The question is NOT clear to me enough – Empty Jul 29 '15 at 06:06
  • @S.Panja-1729; which bit is confusing? – JMP Jul 29 '15 at 06:07
  • How many permutations of $n$ are $<n$ means ? – Empty Jul 29 '15 at 06:08
  • In this sense a permutation of $n$ appears to be a permutations of the digits of $n$... – Mose Wintner Jul 29 '15 at 06:09
  • Your question is somewhat ill-posed. There is no way to know without looking at where $n$ appears in a sorted list of all the permutations of its digits. – Mose Wintner Jul 29 '15 at 06:12
  • @MoseWintner; consider 123 132 213 231 312 321, can you say 231 is 4th, so 3 less than, 1 equal and 2 greater? – JMP Jul 29 '15 at 06:16
  • This depends on what $n$ is and I can see no way other than brute force of finding the number of permutations of its digits that are less than $n$. For example if $n=55555$ there $5! = 120$ permutations of its digits but they are all $55555$ so none is less than n – Warren Hill Jul 29 '15 at 06:28

2 Answers2

1

Interesting puzzle. You could figure it out recursively:

  1. Start two variables ($b=0$ for bigger and $s=0$ for smaller).
  2. Add all the permutations that have a bigger (smaller) initial digit to $b$ ($s$).
  3. Remove the initial digit and go back to 2.

At some point you have 1 digit left which has only one permutation (equal).

This is basically just a restatement of your problem rather than a solution, but maybe it will help lead to something greater...

Dr Xorile
  • 1,407
1

Let $L(n), E(n), G(n)$ be the number of permutations less than, equal to, or greater than $n$, respectively. Suppose the digits of $n$ are $d_1 d_2 \ldots d_m$ (in the usual order, most significant at the left).

I'll start with the case where all the digits are distinct. Then $E(n) = 1$. A permutation $d_1' d_2' \ldots d_m' < d_1 d_2 \ldots d_m$ iff for some $k = 1 \ldots m-1$, $d_i' = d_i$ for all $i < k$ while $d_k' < d_k$. Let $R_k$ be the number of $i > k$ with $d_i < d_k$. Then the number of permutations with $d_i' = d_i$ for all $i < k$ and $d_k' < d_k$ is $R(k)(m-k)!$, so that $L(n) = \sum_{k=1}^{m-1} R_k (m-k)!$, and $G(n) = m! - 1 - L(n)$. So for example with $n = 231$, $R_1 = 1$, $R_2 = 1$, and $L(231) = 1 \times 2! + 1 \times 1! = 3$.

EDIT: Mistake deleted.

Robert Israel
  • 448,999