Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Find cardinality of set

  1. Apr 2, 2014 #1
    I have faced the following problem recently:

    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, which do not overlap. (example L_T = 3 , subsequences are {1,2,3},{4,5,6},{7,8,9},...). Let's call the elements of T "tiles".

    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 "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. For example, subsequence {1,2,3} is possible to cover with 2 tiles of length 2 ({1,2} and {3,4}), while subsequnce {1,3,5} is not possible to "cover" with 2 "tiles" of length 2, but is possible to cover with 2 "tiles" of length 3 ({1,2,3} and {4,5,6}).

    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.

    Any ideas would be appreciated how to tackle this problem.
  2. jcsd
  3. Apr 2, 2014 #2


    User Avatar
    Science Advisor
    Homework Helper

    It may make sense to look at the union of each subset of K tiles, and then take power sets of their union.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook