I Analytical formula for the number of patterns by using combinations?

Sahil_John
Messages
7
Reaction score
1
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
 
Physics news on Phys.org
Welcome to PF. :smile:
Sahil_John said:
I attached a figure for the explanation.
I don't see any attachments. Maybe try again? Thanks.
 
Please find the attachement. Thank you
First_PIc.jpg
 
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.
 
Last edited:
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?
 
Sahil_John said:
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]
 
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.
 
Sahil_John said:
If I take two different numbers 1 and (1,1).
I don't understand what you mean.
 
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).
 
  • #10
If there are 4 rows each with 2 valid patterns then there is a total of ## 2^4 = 16 ## patterns.
 
  • #11
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
 
  • Like
Likes pbuk
  • #12
Yes, that is correct :biggrin:
 
  • #13
Dear Sir, pbuk, I am grateful to you for solving my problem. Thank you
 
Back
Top