Analytical formula for the number of patterns by using combinations?

[Sahil_John]

A 4×3 matrix which has all elements empty, now I select any two consecutive elements until all elements are selected. I assign an index number (1 to 12) to the matrix element, in one row there are only 1,2,3 elements and 3 & 4 are not consecutive.

for example, if I select index 1 & 2 of the matrix, I get the first pattern. if I select 2 & 3 of the matrix, I get the second pattern, likewise 4 & 5, and so on. So, for the first-time selection of 2 consecutive elements, there is an 8 pattern (as shown in first_PIC).

Now, I have 8 patterns in which the first pattern has 1 & 2 index elements are fixed. now from this first pattern again I select 2 consecutive elements, I get 6 patterns (9 to 14 as shown in first_PIC). This process is repeated until all the possible patterns are created.

In the figure, I created manually 80 patterns for two consecutive elements but if I increase the size of the matrix, I cannot compute the number of patterns manually. I need an analytical formula for finding the total number of patterns. I attached a figure for the explanation. If anything you need to know let me know. Can anyone help me? Thank you

 

[berkeman]

Welcome to PF.

I attached a figure for the explanation.

I don't see any attachments. Maybe try again? Thanks.

 

[Sahil_John]

Please find the attachement. Thank you

 

[pbuk]

I am afraid your description is impossible to understand, and the attached image is difficult to read, but from combining them I think you mean this:

1. M is a 4 x 3 matrix.
2. Each element of M is either 0 or 1.
3. Each row of M may contain all 0s, or one pair of elements in adjacent columns may equal 1.

[CODE title="Matrix examples"]
Valid Valid Invalid
0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 1 1
0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0
[/CODE]

How many solutions are there for M?

If my description is right then you have miscounted and there are $3 \times 3 \times 3 \times 3 = 81$ solutions. Can you see why? Can you use this knowledge to find a solution for an $m \times n$ matrix?

If you reply to this message you can see how I have used CODE formatting to easily show the examples, and $\LaTeX$ formatting to show mathematical expressions nicely.

 

[Sahil_John]

Dear Sir, your description is right. But, in your example there are only two valid patterns then it should be 2 x 2 x 2 x 2 = 16. I understand it 3 is 4 times because of the number of rows. But how comes 3?

 

[pbuk]

Dear Sir, your description is right. But, in your example there are only two valid patterns then it should be 2 x 2 x 2 x 2 = 16. I understand it 3 is 4 times because of the number of rows. But how comes 3?

There are 3 valid patterns in each row:
[CODE title="Row examples"]
0 0 0 Valid: no elements selected.
1 1 0 Valid: 1st and 2nd element selected.
0 1 1 Valid: 2nd and 3rd element selected.
1 0 0 Invalid: unpaired element selected.
1 0 1 Invalid: selected elements are not adjacent.
1 1 1 Invalid: unpaired element selected.
[/CODE]

 

[Sahil_John]

Dear Sir, Thank you for your explanation; I got it. One more question if I take two different numbers 1 and (1,1). Is it possible to compute the total number of patterns? Thank you so much for being so supportive.

 

[pbuk]

If I take two different numbers 1 and (1,1).

I don't understand what you mean.

 

[Sahil_John]

As in my previous example, I took (1,1) pairs all the time. Same as if I take "a" and (b,b) pair. for example, in (0,0,0) if I select "a" and (b,b) pair, i get two patterns (a,b,b) and (b,b,a).

 

[pbuk]

If there are 4 rows each with 2 valid patterns then there is a total of $2^4 = 16$ patterns.

 

[Sahil_John]

It means I can take any different number of pairs or single elements. If the Number of valid patterns (let a) and the number of rows (let b), then total patterns is a to the power b (a^b). Is it correct? Thank you, Sir

 

[pbuk]

Yes, that is correct

 

[Sahil_John]

Dear Sir, pbuk, I am grateful to you for solving my problem. Thank you