1. Not finding help here? Sign up for a free 30min 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 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Counting problem
  1. Counting problems (Replies: 19)

  2. Counting Problems (Replies: 4)

  3. Counting problem? (Replies: 5)

  4. Counting problem (Replies: 4)

  5. Counting Problem (Replies: 8)

Loading...