Generating Combinations by Three Basic Operations

We investigate the problem of listing combinations using a specialclass of operations, \it prefix shifts. Combinations arerepresented as bitstrings of 0's and 1's, and prefix shifts are theoperations of rotating some prefix of a bitstring by one position toleft or right. We give a negative answer to an open problem asked byF. Ruskey and A. Williams (Generating combinations by prefix shifts,In Proc. 11th Annual International Computing and CombinatoricsConference 2005, LNCS 3595, Springer, 2005, pp.570\sim576), that iswhether we can generate combinations by only using three very basicprefix shifts on bitstrings, which are transposition of the firsttwo bits and the rotation of the entire bitstring by one position ineither direction (i.e., applying the permutations \sigma_2,\sigma_n and \sigma_n^-1 to the indices of the bitstrings).