A character is any feature (genetic, physical, etc.) that divides a collection of organisms into two separate groups. One commonly used genetic character is the possession of a single-nucleotide polymorphism (SNP).
In a process called genotyping, the SNP markers taken from a large number of human donors have been used very successfully to catalogue the migration and differentiation of human populations over the last 200,000 years. For $199, you can participate in National Geographic's Genographic Project1, and discover your own genetic heritage.
Whether we use genetic or physical characters, we may think of a
collection of $$n$$ characters as a collection of "ON"/"OFF" switches. An
organism is said to possess a character in the "ON" position (although
often the assignment of "ON"/"OFF" is arbitrary). Given a collection of
taxa, we may represent a character by the collection of taxa possessing
the character.
A set is the mathematical term for a loose collection of objects, called elements. Examples of sets include $$\{\textrm{the moon, the sun, Wilford Brimley}\}$$ and $$\mathbb{R}$$, the set containing all real numbers. We even have the empty set, represented by $$\emptyset$$ or $$\{\}$$, which contains no elements at all. Two sets are equal when they contain the same elements. In other words, in contrast to permutations, the ordering of the elements of a set is unimportant (e.g., $$\{\textrm{the moon, the sun, Wilford Brimley}\}$$ is equivalent to $$\{\textrm{Wilford Brimley, the moon, the sun}\}$$). Sets are not allowed to contain duplicate elements, so that $$\{\textrm{Wilford Brimley, the sun, the sun}\}$$ is not a set. We have already used sets of 2 elements to represent edges from a graph.
A set $$A$$ is a subset of $$B$$ if every element of $$A$$ is also an element of $$B$$, and we write $$A \subseteq B$$. For example, $$\{\textrm{the sun, the moon} \} \subseteq \{\textrm{the sun, the moon, Wilford Brimley} \}$$, and $$\emptyset$$ is a subset of every set (including itself!).
As illustrated in the biological introduction, we can use subsets to represent the collection of taxa possessing a character. However, the number of applications is endless. For example, an event in probability can now be defined as a subset of the set containing all possible outcomes.
Our first question is to count the total number of possible subsets of a
given set.
Write a function subsets that takes a positive integer $$n
\in \mathbb{N}$$. The function must return the total number of subsets of
$$\{1, 2, \ldots, n\}$$.
>>> subsets(3) 8 >>> subsets(12) 4096
What does counting subsets have to do with characters and "ON"/"OFF" switches?