Consider the set of $n = 4$ elements $\{0, 1, 2, 3\}$ that correspond to positions A, B, C, D. Now, I want to set certain restrictions on the numbers I can choose for each position so I have included inequalities. See Examples here:

Repetitions are allowed provided they do not contradict the inequality (as shown in the example).

Since there are 2 inequities used, $<$ and $\leq$, and 3 placements for them, there are a total of $2^3=8$ distinct patterns available. I have tried all $8$ and I noticed that any that make use of two $\leq$ and one $<$ (regardless of the order) make a table of 15 rows of permutations. If the inequality patterns have one $\leq$ and two $<$ (again, regardless of order) it makes a table of 5 rows of permutations. If there are three $<$ there is naturally only one permutation and if there are three $\leq$ it makes a table of 35 permutations.

I have been saying rows of permutations since the order matters (as dictated by the inequalities), but is this correct? The number of permutations in each table appears to come from combinations with repetitions: $C^R_{1,4}=1$, $C^R_{2,4}=5$, $C^R_{3,4}=15$ and $C^R_{4,4}=35$.

One clue might be the columns of these tables. For instance, the columns of any table of five permutations includes only two distinct elements from four (and includes repetitions). This is the same as combinations with repetitions: $C^R_{2,4}=5$. Similarly, any table of $15$ elements has in its columns only three distinct elements from four This is the same as $C^R_{3,4}=15$. My questions are:

  1. Are these row elements indeed permutations? If not, what is the correct term for them?
  2. Is my idea of counting the perms in each table using $C^R_{n,r}$ correct? If so, how can I show this is true in general?
  3. Is there a link between the inequality patterns (and the number , $n-1$, of them) and the number of perms in each table?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.