Source code online books for professionals by professionals

Figure 3-4.  Passing n tokens down through the levels of a binary tree
Tip
 
■
  a geometric (or exponential ) series is a sum of ki, where i = 0...n, for some constant k. If k is greater  than 1,  
the sum will always be 
Q(k
 n+1
). The doubling sum is just a special case.
Subsets, Permutations, and Combinations
The number of binary strings of length k should be easy to compute, if you’ve read the previous section. You can, for 
example, think of the strings as directions for walking from the root to leaves in a perfectly balanced binary tree. The 
string length, k, will be the height of the tree, and the number of possible strings will equal the number of leaves, 2
k
. 
Another, more direct way to see this is to consider the number of possibilities at each step: The first bit can be zero or 
one, and for each of these values, the second also has two possibilities, and so forth. It’s like k nested for loops, each 
running two iterations; the total count is still 2
k
.