Here are some obvious and less obvious places where we encounter the sequence . Most of these come from the corresponding OEIS page.

- as a solution to the recurrence .
- the number of subsets of a n-element set: To each element there are two choices – to include it or not include it in the subset. Hence there are subsets.
- the sum of the numbers in the n’th row of Pascal’s triangle This is a consequence of the binomial theorem applied to .
- the sum of the coefficients of , which is the sum of binomial coefficients
- the number of even or odd-sized subsets of an (n+1)-element set, i.e. , a consequence of the binomial theorem .
- each term in the sequence is the smallest natural number that is not the sum of any number of distinct earlier terms, an example of a sum-free sequence
- the sequence forms the set of every natural number that is not the sum of 2 or more consecutive positive integers: Such a sum has the form . If this were a power of 2 then and must both be powers of 2 greater than or equal to 2. But their difference is odd, which is impossible for the difference of even powers of 2. Conversely if a natural number is not a power of two it is of the form where is an odd number at least 3. Then may be written as the sum of either consecutive positive integers with middle (mean) term (if ) or consecutive positive integers with mean (if ). For example, and while and .
- the number of ordered partitions of is : for example, the eight ordered partitions of 4 are: 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3, 4 To see why this result is true, imagine items in a row. Imagine separating them with dividers so that the number of items between each divider gives us the ordered partition. For example with 4 items we may place a divider between the third and fourth item to give the partition 3+1. We have possible locations for dividers (between any adjacent items) and each location has a choice of being assigned to a divider or not. This leads to possible partitions. Alternatively, an ordered partition of may be derived inductively from an ordered partition of by either forming or . Also any ordered partition of has one of these forms as we may form from it an ordered partition of by either subtracting 1 from the first element of the partition (if it is greater than 1) or deleting the first element if it is 1. Hence the number of partitions doubles as is increased by 1 and for we have the single partition.
- the number of permutations of with exactly one local maximum: for example, for we have the permutations 1234, 1243, 1342, 2341, 1432, 2431, 3421, 4321. Here we have the highest element somewhere and there are possible subsets of that we may choose to precede it. These elements must be in ascending order, while the elements after are in descending order to ensure exactly one local maximum at . Hence the order of terms is determined once the subset is chosen and we have permutations.
- the number of permutations of elements where no element is more than one position to the right of its original place: for example, for the allowed permutations are 1234, 1243, 1324, 1423, 2134, 2143, 3124, 4123. This can be seen inductively: if is a valid permutation of n+1 elements, then and are valid permuations of n+2 elements. Also any valid (n+2) element permutation is of this form as it may be reduced to a valid (n+1) element permutation by deleting the 1 (which must occur in either the first or second position) and subtracting 1 from every other element. This describes a one to two mapping between valid permutations of n+1 and n+2 elements. Finally for 1 element there is allowed permutation, so the result follows by induction.

Advertisements

## Leave a Reply