July 19, 2012, midnight by Rosalind Team
Topics: Combinatorics, Set Theory
Characters and SNPs
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, or 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 Project, 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
A set
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.
Given: A positive integer
Return: The total number of subsets of
3
8
Hint
What does counting subsets have to do with characters and "ON"/"OFF" switches?