Number of distinct riffle shuffles I'm learning about riffle shuffles and am struggling to understand the number of distinct riffle shuffles mentioned here.
The following sentence confuses me: 

"More generally, the formula for this number is $2^n − n$; for
  instance,..."

Why is $2^n - n$ the number of distinct riffle shuffles on a deck of n cards? 
 A: Well, take $Id= 12\cdots (n-1)n$ the identity permutation in string notation. So, if you break in two parts(with $p$ and $q$ elements such that $p+q=n$) this permutation, say $$\sigma _1 = 12\cdots p,\sigma _2 = (p+1)(p+2)\cdots (p+q),$$ then by a stars and bars argument (see the two decks as one is bars and the other stars and you can have no stars in between bars), you get $\binom{p+(q+1)-1}{(q+1)-1}=\binom{p+q}{q}$ ways to shuffle them. So, if you want to generate all permutations, you split in every possible way and hence you will get $$\sum _{p+q=n}\binom{p+q}{q}=\sum_{q=0}^n\binom{n}{q}=2^n.$$ The only problem is that you are counting the identity permutation $n+1$ times. Because in this procedement $Id$ can be obtained by all decomposition by placing the left part of the deck in the top of the other one. As you want to count it just $1$ time, then you subtract $n+1-1$ to the sum and you get $2^n-n.$
The only thing remaining is to understand that you can not get another permutation different of the identity more than once by this procedement. But that's easy to see, given $\sigma\neq Id$, take $p$ to be the maximum number such that $12\cdots p$ is a subsequence of $\sigma$ and $(p+1)\cdots (p+q)$ is also a subsequence. Notice that $p\neq n$ and $p\neq 0,$ otherwise $\sigma = Id.$ Can you divide for a number $p'<p$ and get the same permutation? Why?
A: In the riffle shuffle you split the deck into a deck consisting of the $p$ top cards and another consisting of the bottom $q$ cards with $p+q=n$.  For any given split the $p$ cards in one deck maintain their order but can occupy any $p$ slots in the resulting deck, so there are $n \choose p$ resulting decks that can result from the division.  We can have $p$ range from $0$ to $n$ and sum these up, which gives $2^n$ like any row of Pascal's triangle.  These shuffles are all distinct except the identity one where every card is in its original location.  This can be achieved with any value of $p$ from $0$ through $n$, we just put the whole first deck on top of the whole second one.  We have counted it $n+1$ times, so we need to subtract $n$ to only count it once.  The point is that we want to count final configurations, not the routes to get to them.
