Double proof about permutations.

>>>> Proof by Mathematical induction <<<<<

About this evident fact:
According the standard convention for reading
numbers in every positional number system: Decomposing
the numbers as linear combinations of powers for a given
radix, the concatenation in ascending order for the first
digits in the given radix always assigns the smallest
possible value.

Convention: When reading numbers from left to right,
each digit have associated a power of a given radix.
The exponents for those powers are distributed in
descending order from left to right. So a number
written in base r whose representation is written
for example as "123bca" in the base r=16 (hexadecimal)
will have assigned the following value in decimal (base-10):

"23bca"
---> ( 2 )*r^4 + ( 3 )*r^3 + ( b )*r^2 + ( c )*r^1 + ( a )*r^0
---> 146378 (decimal)

Now it will be observed in the further that for each
case that the smallest possible k-digits permutation
( k < r ) for the first k digits in base r is the
concatenation in ascending order of those digits.

k=1.
Trivial since there is 1 and only 1 one-digit permutation: {"1"}

k=2.
The two permutations are: {"12","21"}

The possible assignations are also two:

"12" <---> ( 1 )*r^1 + ( 2 )*r^0

"21" <---> ( 2 )*r^1 + ( 1 )*r^0

Subtracting these assignations:

"21 -12"  <--> (2-1)*r^1 + (1-2)*r^0 = 1*r^1 - 1*r^0 = (r-1)

"21" is greater than "12" by a difference of (r-1),
then for two-digits permutations, "12" or the concatenation
of the first two digits have assigned always the smallest
possible value regardless the radix.

k=3. There are six (3!) possible assignations, but we only
are interested in compare the concatenation of the first 3
digits with the other five remaining permutations so there
will be 5 differences to be checked:

Assignations:

"123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
"132" <---> ( 1 )*r^2 + ( 3 )*r^1 + ( 2 )*r^0
"213" <---> ( 2 )*r^2 + ( 1 )*r^1 + ( 3 )*r^0
"231" <---> ( 2 )*r^2 + ( 3 )*r^1 + ( 1 )*r^0
"312" <---> ( 3 )*r^2 + ( 1 )*r^1 + ( 2 )*r^0
"321" <---> ( 3 )*r^2 + ( 2 )*r^1 + ( 1 )*r^0

Differences:

"132" <---> ( 1 )*r^2 + ( 3 )*r^1 + ( 2 )*r^0
"123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
----------------------------------------------
( 0 )*r^2 + ( 1 )*r^1 + ( -1 )*r^0

Or: (r-1)

"213" <---> ( 2 )*r^2 + ( 1 )*r^1 + ( 3 )*r^0
"123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
----------------------------------------------
( 1 )*r^2 + ( -1 )*r^1 + ( 0 )*r^0

Or: r^2-r = r*(r-1)

Also: 10*(r-1) if we remember that 10 represents
the base.

"231" <---> ( 2 )*r^2 + ( 3 )*r^1 + ( 1 )*r^0
"123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
----------------------------------------------
( 1 )*r^2 + ( 1 )*r^1 + ( -2 )*r^0

Or: (r+1)*(r-1)+(r-1) = (r+2)*(r-1)

"312" <---> ( 3 )*r^2 + ( 1 )*r^1 + ( 2 )*r^0
"123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
----------------------------------------------
( 2 )*r^2 + ( -1 )*r^1 + ( -1 )*r^0

Or: (2*r+1)*(r-1)

"321" <---> ( 3 )*r^2 + ( 2 )*r^1 + ( 1 )*r^0
"123" <---> ( 1 )*r^2 + ( 2 )*r^1 + ( 3 )*r^0
----------------------------------------------
( 2 )*r^2 + ( 0 )*r^1 + ( -2 )*r^0

Or: 2*(r+1)*(r-1)

In general for k>3:

Let be c_i and c_(i+1) two digits inside the
concatenation in ascending order for the first N
digits of base-r (N <= r, 0<=i<=(N-1) ),
then both c_i and c_(i+1) ranges in 0..(N-1),
and if "i" is the corresponding count index
from left to right, then clearly: c_i < c_(i+1).

According to the previous description the
first digit at the left c_0 have associated
the power r^(N-1) and the last digit most at
right c_(N-1) have associated the power r^0.
This additional comment is unnecessary in the
present proof but it illustrates that while
the coefficients increases by 1 from left to
right, the exponents does exactly the opposite,
decreases by 1 from left to right. So in the
ascending order concatenation, two adjacent
digits are represented in general by:

s0= c_i*r^j + c_(i+1)*r^(j-1)

Relative to the (base-10) value assigned to a permutation.

Now if the coefficients are commuted, we will have:

s1= c_(i+1)*r^j + c_i*r^(j-1)

And subtracting (s1-s0):

(s1-s0)= c_(i+1)*r^j + c_i*r^(j-1) +(-1)*( c_i*r^j + c_(i+1)*r^(j-1) )
   = ( c_(i+1) - c_i )*r^j + ( c_i - c_(i+1) )*r^(j-1)
   = ( c_(i+1) - c_i )*r^j -- ( c_(i+1) - c_i )*r^(j-1)
   = ( c_(i+1) - c_i )*r^(j-1+1) -- ( c_(i+1) - c_i )*r^(j-1)
   = ( c_(i+1) - c_i )*r^(j-1)*r -- ( c_(i+1) - c_i )*r^(j-1)
   = ( ( c_(i+1) - c_i )*r^(j-1) )*(r-1)

(**Note: Some minus signs were duplicated for readability)

There is obtained a positive multiple of (r-1)
like in the particular cases studied before.

So, continuing this process for k=4, k=5, ...
and so on "ad infinitum", if it were provided
that (k<r), then the mentioned concatenation
in ascending order for the first digits in
base-r will be found to be always the smallest
possible permutation without repetition built
using k digits.

Also notice the following interesting property
about each one of the studied differences:
All of them are multiples of (r-1).

(END)