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

AI Thread Summary
The discussion revolves around finding an analytical formula for counting patterns in a 4x3 matrix where elements can be selected in pairs. Initially, eight patterns can be formed by selecting two consecutive elements, leading to further selections that generate additional patterns. The participants clarify the counting method, noting that valid patterns depend on the arrangement of selected elements, with a total of 81 solutions identified for the matrix configuration. The final consensus is that if there are 'a' valid patterns per row and 'b' rows, the total number of patterns can be calculated as a^b. The conversation concludes with gratitude for the assistance provided in solving the problem.
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