Counting
Subsets Keywords Type Prerequisite
Knowledge Solution Pedagogy Learning Outcomes
Contributed
by: Bill Marion (Bill.Marion@valpo.edu) Source Connections
(i)
Given
a finite set, S, determine the number of subsets of S, that is, determine the
size of the Power Set of S. In particular, suppose S = {3, 7, 9, 11, 24}. List
all the subsets of S and count how many there are.
(ii)
Now,
given the same set S, determine the number of subsets of S with the property
that the sum of the integers in the subset is less than 28.
Keywords: Counting Techniques, sets,
subsets
Type: Lecture example, homework
problem, in-class group assignment
Solution: It is easy to list all the subsets of S and
determine that there are 32 =2^5
such subsets. It might be
useful to list them in terms of their size and, then,
see how many there are.
In addition, after all the subsets have been listed, it
is easy to see that there
are 16 subsets whose sum of integers is less than 28
(17 of them if the empty
set is included).
Pedagogical Notes: Even though this particular problem seems trivial, addressing the
second
part of the problem can lead to some interesting questions
concerning algorithm design strategies for solving similar
problems where the size of the set, S, is finite but rather large.
Also,
variants of this problem can be presented which lead to
consideration
of well-known problems, such as the Subset Sum
problem, the Knapsack problem, Scheduling problems and
problems in Cryptography.
Learning Outcomes: To reinforce the use of both the Addition and Multiplication
Principles for counting and to illustrate the idea that even simple
problems, when extended, can lead to important applications in
computer science.
Connections: algorithm design strategies, encryption algorithms, scheduling
algorithms,
complexity classes
Prerequisite Knowledge: Precalculus
Source: Textbook--K. Rosen, Discrete Mathematics and Its Applications,
(4th ed.)
Textbook—S. Maurer and A.
Ralston, Discrete Algorithmic Mathematics
(2nd ed.)