1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting methods for subsets

  1. Sep 4, 2014 #1
    1. The problem statement, all variables and given/known data
    Let Ω be the universe and A1, A2, A3, ..., An the subsets of Ω.
    Prove that the number of elements of Ω that belongs to exactly p (p≤n) of the sets A1, A2, A3, ..., An is
    [itex] \sum_{k=0}^{n-p}(-1)^k\binom{p+k}{k}S_{p+k} [/itex]

    in which
    [itex]S_{0} = |\Omega| [/itex]
    [itex]S_{1} = \sum_{i=1}^{n}|A_{i}| [/itex]
    [itex]S_{2} = \sum_{1\leq i<j}^{n}|A_{i}\cap A_{j}| [/itex]

    [itex]... [/itex]

    And
    |A| is the number of elements that belongs to A

    2. Relevant equations
    Counting methods and the principle of inclusion and exclusion

    3. The attempt at a solution
    The equation demanded to be proved is very useful for solving problems such as counting the numbers of integers between 0 and 1001 that are divisible by exactly two of the numbers 2, 3, 7 and 10. How should I demonstrate it?
     
    Last edited: Sep 4, 2014
  2. jcsd
  3. Sep 5, 2014 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Do what Feller does in his Probability Theory Volume I, where he does something similar for probabilities. Just look at an element ##w## that is in exactly ##p## of the subsets ##A_i##. Let
    [tex] B_p = \{ x \in \Omega: x \text{ is in exactly}\:p\: \text{of the sets} \: A_i \} [/tex]
    and let ##M_p = |B_p|.##

    Pick any ##w \in B_p##. How much does ##w## contribute to the right-hand-side?

    For example, if ##p=2##, ##w## appears in two of the ##A_i## so contributes 2 to ##S_1## (but this is irrelevant, since ##S_1## does not appear on the right-hand-side for ##p \geq 2##). The element ##w## appears in just one doublet ##A_i \cap A_j##, so contributes 1 to ##S_2##. It does not contribute anything to ##S_3, S_4, \ldots, S_n##. So, its contribution on the right-hand-side is
    [tex]{2+0 \choose 0} 1 - {2+1 \choose 1} 0 + {2+2 \choose 2} 0 - \cdots + 0 = 1 [/tex]

    However, we are not yet done. How much does ##w## contribute to ##M_1##? Its contribution should be 0, since ##w \not\in B_1##. Let's look at what its contribution would be on the right-hand-side. As already stated, its contribution is 2 to ##S_1## and 1 to ##S_2## (and 0 to ##S_k, \:k \geq 3##). So, its contribution to ##M_1## would be
    [tex] {1+0 \choose 0} 2 - {1+1 \choose 1} 1 + {1 + 2 \choose 2} 0 - \cdots + 0 = 2 - 2 = 0[/tex]
    This is as it should be.

    Try the simpler case ##p=1##, then try ##p=3##. After than you might see how to handle the general case.
     
    Last edited: Sep 5, 2014
  4. Sep 7, 2014 #3
    Great, Ray!! I didn't know about this book, though. Thanks
     
    Last edited: Sep 7, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Counting methods for subsets
  1. Counting question (Replies: 8)

  2. Counting combinations (Replies: 7)

  3. Counting functions (Replies: 10)

  4. Subset Question (Replies: 3)

Loading...