Combinatorics-Systems of Distinct Representatives proof problem?
Let n>1 and let Ą=(A1, A2,...,An) be the family of subsets of a {1,2,...n}, where Ai={1,2,...,n} - {i}, (i=1,2,...,n).
Prove that Ą has an SDR (system of distinct representatives) and that the number of SDR's is the nth derangement number Dn.
Any help on this problem would be appreciated. Please answer as completely as you can so I can hopefully understand what's going on. Thanks.
Comments
I believe this one can be expressed as a special case of the chessboard problem with forbidden positions. So in terms of an n-by-n chessboard, the {1,...,n} once again label the column coordinates and the rows are the Ai with the i^th column being forbidden. So if we look at the whole chessboard thus formed, exactly the top-left to bottom-right diagonal is forbidden. So this is just the chessboard problem with p = n-1 i.e. SDR exists. I'm assuming your Prof allows the use of one problem to solve another.
As for the derangements, first note that an SDR in the context of a chessboard with all squares allowed is nothing more than a good old permutation on n letters. So in the case of a chessboard that forbids use of the diagonal an SDR would be a permutation restricted in that no letter is allowed to remain in its original place i.e. derangement. Therefore the number of SDRs is just Dn.
For anyone else who may be reading this and wondering about the chessboard problem, the link is provided below.