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 *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.

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?