Concept

How do partitions simplify counting?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"Partitions come up quite a bit, and when they do, we can make some important simplifications. Take S, the set of all students at UMW. We can partition it in several different ways. If we divide S into the set of freshmen, sophomores, juniors, and seniors, we have a partition: every student is one of those grade levels, and no student is more than one. If we group them into in-state and out-of-state students, we again have a partition. And if we divide them into those who live on-campus and those who live off, we again have a partition. Note that dividing S into computer science majors and English majors does not give us a partition. For one thing, not everyone is majoring in one of those two subjects. For another, some students might be double-majoring in both. Hence this group of subsets is neither mutually exclusive nor collectively exhaustive. It’s interesting to think about gender and partitions: when I grew up, I was taught that males and females were a partition of the human race. But now I’ve come to realize that there are non-binary persons who do not identify with either of those genders, and so it’s not a partition after all. Is the number of students |S| equal to the number of off-campus students plus the number of on-campus students? Obviously yes. But why? The answer: because the off-campus and on-campus students form a partition. If we added up the number of freshmen, sophomores, juniors, and seniors, we would also get |S|. But adding up the number of computer science majors and English majors would almost certainly not be equal to |S|, because some students would be double-counted and others counted not at all. This is an example of the kind of beautiful simplicity that partitions provide."

Related Ideas

How do partitions simplify counting? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm