# Counting problem

1. Nov 26, 2006

### morphism

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 $(n-k+1)k - \frac{k(k-1)}{2}$, which isn't always correct. I feel I'm missing something simple.

Last edited: Nov 26, 2006
2. Nov 26, 2006

### AKG

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.

3. Nov 26, 2006

### morphism

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.