Find number of elements combinations covered by a given set of element

[grigor]

Here is the problem I have faced recently that I cannot deal with yet and I need some help:

Given is the
- list of elements (numbered): e.g. [1,2,3,4,6,7,8]
- the count and size of groups, which can be used to cover the given set of numbers, e.g. groups with group size 2.
- I need to find the number of combinations of elements of given length, which can be covered by any placement of element groups
for example,

* if combination_length = 1, all possible combinations are covered: 1, 2, 3, 4, 5, 6, 7, 8 -> combs_count_covered = 8 (out of 28 possible)

* if combination_length = 2, the following combinations are covered: 12, 13, 14, 15, 16, 17, 18, 23, 24, 25, 26, 27, 28, 34, 35, 36, 37, 38, 45, 46, 47, 48, 56, 57, 58, 67, 68, 78 -> combs_count_covered = 28 (out of 28 possible)

* if combination_length = 3, the following combinations are covered: 123, 124, 125, 126, 127, 128, 134, 135, 136, 137, 138, ... -> combs_count_covered = 36 (out of 56 possible), one of the uncovered combinations is e.g., 147, which is not possible to cover with 2 groups, but possible with 3 groups of 2 elements, placed e.g. this way: 12-45-67

* if combination_length = 4, the following combinations are covered: 1234, 1245, 1256, 1267, ... -> combs_count_covered = 15 (out of 70 possible), one of the uncovered combinations is e.g., 1235, which is not possible to cover with 2 groups, but possible with 3 groups of 2 elements, placed e.g. this way: 12-34-56

* if combination_length = 5, coverage with 2 groups is not possible any more.

Of course, the most preferable option will be to get a universal formula, which will receive these parameters and return the number of combinations covered with this configuration, but any ideas are appreciated how to approach the problem.

In case of group_size = 1, group_count = n and group_size = n, group_count = 1, I have got the corresponding formulas, but in general case group_size = k, group_count = n I couldn't find yet such formula.

 

[Stephen Tashi]

It's best to call a set of things a "set" rather than calling it a "group" since "group" has technical definition in abstract algebra.

one of the uncovered combinations is e.g., 147, which is not possible to cover with 2 groups,

It isn't clear how you are defining "covered". {1,4,7} is a subset of the union of {1,4} with {4,7} and also a subset of the union of {1,4} with {7,8}.

Your question seems to involve the set of M integers {1,2,3,...} and other sets of ordered k-tuples of integers {g1,g2,..gk}, such that (as integers) 0 < g1 < g2 < ... < gk < M+1.

 

[grigor]

It is my fault I didn't explain what I mean by group. I didn't find more suitable term to call it the other way. So in my case group is the set of ordered k-tuples of integers {g1, g2,... gk} (just as you have mentioned), but tuples consist of sequential numbers, i.e., g1>0; g2=g1+1; g3=g2+1; g4=g3+1, etc. That means for example {1,2} and {4,5,6} are groups, but {1,3} and {3,5,6} are not. So in this sense it is not possible to cover the set {1,4,7} with 2 groups of length 2.

Hope this sheds light on uncertainties of my problem description.

 

[Stephen Tashi]

Let's see if I understand the problem.

We have a sequence A of M consecutive integers, beginning at A[1] = 1:
1,2,...M (example: M = 8 , A = 1,2,3,4,5,6,7,8 )

We have the set T consisting of all possible subsequences made from L_T consecutive terms of A. ( example L_T = 3 , subsequences such as {1,2,3}...(3,4.5),..,{4,5,6}.) I'm going to call the elements of T "tiles" instead of "groups"

We have the set S consisting of all possible subsequences of A that have length L_S. ( example L_S = 4, subsequences like {1,2,3,4} , {1,3,7,8) ,...{4,5,7,8} ).

We say that an element s of S can be "covered" by K elements ("tiles') of T if there exist K tiles in T such that the union of their sets of terms contains the terms of s as a subset.

Let C be the subset of elements of S that can be covered by K tiles of T.

Find the cardinality of C given M, L_T, L_S, K.


If this problem relates to practical problem it might be helpful to describe that problem since someone might know about mathematical approaches to it.

 

[grigor]

Yes in mathematical terms the problem sounds exactly the way you described it.

Actually you are right the problem has a practical nature and it comes from the other field. However this field is not well investigated yet and there was no previous work yet. I cannot reveal more details due to confidentiality, but mathematical modelling of the problem can be done exactly the way you did it.

Thanks in advance if there are any suggestions or ideas how to tackle it.