Claim: There may be only one sorted alignment in decreasing/increasing order such as
X1, X2, X3,...... when X1, X2, X3 are distinct numbers
PROOF IS DONE FOR DECREASING ORDER ONLY. SIMILARLY IT MAY BE PROVEN FOR INCREASING ORDER
Proof:
X1, X2, X3,...... is decreasing. We call this as order 1
Say there is any other order as order 2 which is a different permutation than order 1.
Say the difference in order 2 starts only after t-th element of order 1. That means till t-th element both the sequence are same.
let's write the orders again.
X1, X2, X3,......,X(t), X(t+1).... order 1 (decreasing)
X1, X2, X3,.......,X(t) ,Y(t+1),....,X( t+1).... order 2
Here X(t+1) is not uqual to Y(t+1) as we assumed.
Notice that X(t+1) must be somewhere after Y(t+1) in order 2, because both the orders are chosen from same set of elements.
But Y(t+1) was somewhere after X(t+1) in order 1. So X(t+1)>Y(t+1)
That means oder 2 violates decreasing order. So the proof is complete.
X1, X2, X3,...... when X1, X2, X3 are distinct numbers
PROOF IS DONE FOR DECREASING ORDER ONLY. SIMILARLY IT MAY BE PROVEN FOR INCREASING ORDER
Proof:
X1, X2, X3,...... is decreasing. We call this as order 1
Say there is any other order as order 2 which is a different permutation than order 1.
Say the difference in order 2 starts only after t-th element of order 1. That means till t-th element both the sequence are same.
let's write the orders again.
X1, X2, X3,......,X(t), X(t+1).... order 1 (decreasing)
X1, X2, X3,.......,X(t) ,Y(t+1),....,X( t+1).... order 2
Here X(t+1) is not uqual to Y(t+1) as we assumed.
Notice that X(t+1) must be somewhere after Y(t+1) in order 2, because both the orders are chosen from same set of elements.
But Y(t+1) was somewhere after X(t+1) in order 1. So X(t+1)>Y(t+1)
That means oder 2 violates decreasing order. So the proof is complete.