Proving the Number of SDRs in a Collection of Sets: A Mathematical Analysis

[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.

 

[HallsofIvy]

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

 

[junho]

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

Sorry. I'll do just that.

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