Classes of equally likely outcomes of a riffle shuffle on a deck of alternating cards

Abstract

The mathematical model of riffle shuffle has been a subject of some studies. Whereas most of these regard the cards as all different, in 2006 Conger and Viswanath treated some of them as identical and investigated the implications. When the initial deck is arranged in alternating reds and blacks, they showed that two outcomes are equally likely if a number of particular transformations can turn one of them into the other. This transformation, which may be viewed as a reversible string rewriting system, partitions the set of outcomes into equivalence classes. They conjectured that the number of such classes is precisely , where is the number of cards of each color. In this paper, the assertion is proven true by the method of invariant and derivation of canonical forms.