Explore BrainMass

lexicographic order

The Complement A of an r-subset A of {1,2...,n} is the (n-r)-subset of {1,2,...,n} consisting of all those elements that do not belong to A. Let M= C(n,r), the number of r subsets and at the same time the number of (n-r)-subsets of {1,2...,n}. Prove that if A1,A2,A3...AM are the r subsets in lexigraphic order then complements Am,...,A3,A2,A1 are the (n-r)-subsets in lexiographic order.

(so the last Am,...,A3, A2,A1 are compliments)

Solution Summary

This post assesses lexicographic order.