What's the mathematical model for this matrix.

Question

I need to find the mathematical model for the relationship between number of columns and all possible number of combinations when including two elements, one is not repeating and the other repeats from one to all columns, below an example of columns equals to 4: suppose that I have the matrix as below:

y = [x r 0 0; 
     x 0 r 0; 
     x 0 0 r; 
     x r r 0;  
     x r r 0;
     x r 0 r; 
     x 0 r r; 
     x r r r; 
     0 x r 0; ......etc],

we should have 28 possible combinations.

It means that I have two elements, one of them 'x' is not increasing, and the second which is 'r' is either one or more. my question what's the mathematical model which specify the number of possible combination? For example, for the above matrix, we have four columns, and the possible permutation is 28. what's the relationship between 28 and 4 columns? suppose also we have 3 columns or 5 columns, can we calculate the possible number of permutation using such mathematical model?

Thank you

Answer 1

Suppose there are $n$ columns (so in the example, $n = 4$).

Now consider what happens if we have $n - 1$ places where we can put an 'r' or not put an 'r', the only constraint being we must put at least one 'r' in one of the places. Without that constraint, we could simply choose independently between two choices for each space, put an 'r' there or not, which gives us $2^{n-1}$ ways to put (or not put) 'r's. But the constraint rules out one way, the one where we put no 'r' in any space, so there are actually only $2^{n-1} - 1$ choices about what to do with the $n - 1$ spaces.

Getting back to the original problem, on any single row we have $n$ places to put the 'x'. Since we must put it somewhere on the row, there are $n$ choices for that placement. For each of those choices, we have to choose what to do with the remaining $n - 1$ spaces in that row; there are $2^{n-1} - 1$ possible choices for those spaces.

Therefore the total number of different ways to fill a row is $n (2^{n - 1} - 1).$ For example, if $n = 4$ then there are $4(2^3 - 1) = 28$ ways. If $n = 3$ there are $3(2^2 - 1) = 9$ ways.