For finite sets , the inclusion-exclusion principle statesTo prove it, count one element at a time. An element belonging to exactly of the sets occurs in of their -fold intersections, so its total coefficient on the right is , using . An element in no set has coefficient zero. Every element of the union is therefore counted once, proving the identity.
For the keypad, an initial zero can never be entered: it has no preceding pair of ones and the first key is not two. Define four classes of valid four-digit sequences. Let contain sequences starting with two, with the last three digits arbitrary; let contain sequences with no zeros; let contain sequences of the form with ; and let contain sequences with .
These classes exhaust the valid codes. A sequence starting with two is unrestricted thereafter. Otherwise a zero cannot occur in position two, a zero in position three requires the first two digits to be ones, and a zero in position four requires digits two and three to be ones. Positions three and four cannot both be zero, since the last zero would then lack the required preceding pair. Thus a code outside either belongs to or has precisely one of the zero patterns covered by .
Their sizes areThe only nonempty pairwise intersections are , consisting of first digit two and three nonzero remaining digits, and , containing the single code . Hence and . All other pairwise intersections vanish, and therefore so do all intersections of three or four classes. Applying inclusion-exclusion givesThis counts sequences actually enterable under the history-dependent zero-key rule, rather than simply counting sequences which contain the substring .
Articles by others on the same topic
There are currently no matching articles.