# Another question on SDR's

1. Jan 22, 2008

### junho

1. Suppose A1,A2,...,An contain 2,3,...,n+1 elements, respectively. Show that this collection has at least 2^n SDRs. Find such a collection with exactly 2^n SDRs

2. These are the only equations given in my notes regarding "the number of SDRs a collection of sets has"
k! if k <= n
k!/(k-n)! if k > n

3. Ok, for part one of the question, I know that I have to show that k! > 2^n. I can't seem to decide what k is in this case, is k = 2? or is k variable for each set within the collection?

And for part 2, I'm just doing my best to guess, but to have exactly 2^n SDR's I think that each successive set in the collection must have 2 elements that don't exist in the previous set. Is my line of thinking correct?

Thank you in advance for any help.

Last edited: Jan 22, 2008
2. Jan 22, 2008

### HallsofIvy

Staff Emeritus
It might be helpful if you would define "DR" and "SDR" here.

3. Jan 22, 2008

### junho

Sorry. I'll do just that.

First of all, DR was a typo.
SDR = System of Distinct Representatives