Challenging interesting combinatorics problem
A company has 4 employees ranked from 1 to 4 according to experience. CEO wants to pay them salary from ranging 1 to 5 euros but only integers. To be fair with salaries, CEO wants to avoid this situation: there are three employees X, Y and Z such that X has higher rank than Y, Y has higher rank than Z, but Y is paid more than X while Z is paid more than Y. That would be unfair and must be avoided. In how many ways can the CEO still pay them?
Example:when there were 3 employees and they were paid up to 3€ each day, there were very few combinations to do this. Valid combinations starting with (1,1,1), (1,1,2) all the way to (3,3,3) were allowed. Only combination not allowed was (1,2,3). In this case, best ranked employee would get 1€, second one would get 2€ and the last one would get 3€. That would clearly break the fairness principle. So, in the early day, CEO concluded, there were 3^3 - 1 = 26 valid salary combinations