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

Homework Help: Counting problem

  1. Nov 26, 2006 #1

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Suppose you pick a k-element subset of {1, 2, ..., n}, call it A. How many of the other k-element subsets have k-1 elements in common with A?

    I've been at this for quite some time, but I always overcount. Can anyone help me out? My last attempt gave me [itex](n-k+1)k - \frac{k(k-1)}{2}[/itex], which isn't always correct. I feel I'm missing something simple.
     
    Last edited: Nov 26, 2006
  2. jcsd
  3. Nov 26, 2006 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    How many choices for B are there such that B is a k-element subset with k-1 elements in common with A? There are k-choices for the element of A that B doesn't have, and n-k choices for the element of AC that B does have, giving a total of k(n-k) choices for B. And if by "k-1 elements in common" you mean "at least k-1 elements in common," add 1 to include A.
     
  4. Nov 26, 2006 #3

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Thanks! My problem was that I always took n-k+1 for the element of A^c that B doesn't have, which forced me to overcomplicate things thinking my reasoning was wrong, when in fact it was only a simple overcount.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook