0

Factoradic method can be used to get $k$-th lexicographic permutation of $n$-elements.

The factoradic method is described here: https://en.wikipedia.org/wiki/Factorial_number_system#Permutations.

Could you please kindly provide the proof that this method gives the $k$-th permutation.

I have described the method from Wikipedia below.

There are two steps to get the $k$-th permutation:

Step-1. Convert $k$ to factorial number system.

Eg: to get $2982$nd permutation of $\{0,1,2,3,4,5,6\}$ convert $2892$ to factorial number system. This gives

$2892 = 4:0:4:1:0:0:0_!$ $(\because 2892 = 4 \times 6! + 0\times 5! + 4 \times 4! + 1 \times 3! + 0 \times 2! + 0 \times 1! + 0 \times 0!)$

Step-2: Get $k$-th permutation from the above representation in factorial number system using the method described below.

We start with the following initial state and transfer elements from source to the permutation array in a order directed by the digits of $k$ represented in factorial number system.

Initial state

  • Permutation array: $\{\}$ // Initially it is empty.
  • Source : $\{0,1,2,3,4,5,6\}$. // Lexicographically lowest permutation.
  • $k$, here $2892$ = $4:0:4:1:0:0:0_!$.

Zeroth transfer

First (most significant) digit of $k$ in factorial number system is $4$. So transfer $4$-th element from the source to the permutation array. Now we state is as follows:

  • Permutation array: $\{4\}$ // Initially it is empty.
  • Source : $\{0,1,2,3,5,6\}$. // Lexicographically lowest permutation.
  • $k$, here $2892$ = $4:0:4:1:0:0:0_!$.

First transfer

Next digit of $k$ is $0$, so transfer zeroth element of source. The state becomes

  • Permutation array: $\{4,0\}$ // Initially it is empty.
  • Source : $\{1,2,3,5,6\}$. // Lexicographically lowest permutation.
  • $k$, here $2892$ = $4:0:4:1:0:0:0_!$.

Second transfer

Next digit of $k$ is $4$. Transfer $4$-th element of the source.

  • Permutation array: $\{4,0,6\}$ // Initially it is empty.
  • Source : $\{1,2,3,5\}$. // Lexicographically lowest permutation.
  • $k$, here $2892$ = $4:0:4:1:0:0:0_!$.

$\cdots$ and so on give the permutation ${4,0,6,2,1,3,5}$.

Source: https://en.wikipedia.org/wiki/Factorial_number_system#Permutations

Update

After going through the comments and this Wikipedia page (https://en.wikipedia.org/wiki/Lehmer_code), I understand that the second step in the above procedure is just decoding Lehemer code to its corresponding permutation. So, the most significant part for me is step-1. Therefore my question condenses to the following question:

Prove that the digits of $k$ in factoradiac system gives the Lehmer code for the $k$-th permutation.

Ramasamy Kandasamy
  • 523
  • 3
  • 13
  • 1
    Look at the very thorough presentation here. – Jean Marie May 16 '22 at 07:40
  • Depending on what intermediate results that are acceptable to you, an alternate demonstration would be by induction. If you are choosing $k$ digits from ${0,1,2,\cdots, (n-1)}$, where $k < n$, you can let $f(k)$ denote the enumeration of possible constructible numbers. Clearly, $f(1) = n$. Assume that $\displaystyle f(k) = \frac{n!}{(n-k)!}.$ For any such $k$ digit number, $k$ of the $n$ digits has been used. So, there will be $(n-k)$ choices for the next digit, when constructing a satisfying # with $(k+1)$ digits. So, $~\displaystyle f(k+1) = f(k) \times (n-k) = \frac{n!}{(n-k-1)!}.$ – user2661923 May 16 '22 at 07:50
  • @Jean Marie Thank you very much! I think I am one step closer to the answer to my question. I understand how a permutation can be encoded by Lehmer code. And, I think when $k$ is written in factoradic system, it gives the Lehmer code for $k$-th permutation. However, I still do not understand how to prove this last part. I appreciate any help! – Ramasamy Kandasamy May 16 '22 at 08:17

0 Answers0