CODEWITHSUNDEEP
combinations
MathNoob
MathNoob

Reputation: 1

Counting Amount of subsets from a set

Let set S = {a1, a2, a3, ..., a12}, where all 12 elements are distinct. We wish to form subsets, each of which contains one or more of the elements of set S (including the possibility of using all the elements of S). The only restriction is that the subscript of each element in a specific set must be an integer multiple of the smallest subscript in that set. For example, {a2, a4, a6} is an acceptable set, as is {a6}. How many such sets can be formed?

I was thinking of dividing the problem in cases, one for 3 elements, and then 4 and 5 and so on. This would take way too long so can I have help doing it a faster way?

Upvotes: 0

Views: 267

Answers (1)

kaya3
kaya3

Reputation: 51043

The constraint relates to the smallest subscript, so it makes more sense to branch on that, rather than branching on the size of the subset. You want to branch on something which simplifies the constraint, so instead of "each subscript is a multiple of the smallest subscript" you have e.g. "each subscript is a multiple of 3". Then within each branch it's much easier to count.

You only want to count non-empty subsets, so every subset has a smallest subscript:

  • If the subset contains a1, then each of the 11 remaining elements can be freely chosen as either present or not present. There are 211 such subsets.
  • If the smallest subscript is a2, then there are 5 possible other elements a4, a6, a8, a10, a12, each of which can be freely chosen as either present or not present. There are 25 such subsets.
  • If the smallest subscript is a3, then there are 3 possible other elements a6, a9, a12. There are 23 such subsets.
  • If the smallest subscript is a4, then there are 2 possible other elements a8, a12. There are 22 such subsets.
  • If the smallest subscript is a5 or a6, then there is one possible other element (a10 or a12 respectively). There are 2 subsets for a5 and 2 for a6.
  • Otherwise, the smallest subscript is a7, a8, a9, a10, a11, or a12, and the subset cannot contain any other elements due to the restriction. There is one subset in each case.

The total is therefore 211 + 25 + 23 + 22 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 2,102.

Generalising this argument, if there are n elements in the original set, then the total number of subsets satisfying this constraint is:

formula

Upvotes: 1

Related Questions