Language：English   Publishing type：Research paper (scientific journal)  

This paper studies a sliding block puzzle defined on the two by three grid, which we call the 5-puzzle. Our main aim in this paper is to show a fine geometric property of the graph representing the transitions of the positions of the 5-puzzle. We show that by identifying every position with its 180° rotation and applying path contractions, the soccer ball graph is obtained.

DOI： 10.1016/j.dam.2023.08.011

Language：English  

A deck of n cards are shuffled by repeatedly taking off the top card, flipping it with probability 1/2, and inserting it back into the deck at a random position. This process can be considered as a Markov chain on the group B n of signed permutations. We show that the eigenvalues of the transition probability matrix are 0, 1/n, 2/n,…,(n− 1)/n, 1 and the multiplicity of the eigenvalue i/n is equal to the number of the signed permutation having exactly i fixed points. We show the similar results hold also for the colored permutations. Further, we show that the mixing time of this Markov chain is n log n and exhibits cut off, same as the ordinary’top to random’shuffles without flipping the cards. The cut off is also analyzed by the strong stationary time as well as the asymptotic formula of the Stirling numbers of the second kind.

DOI： https://doi.org/10.1016/j.dam.2023.06.037

Language：English   Publishing type：Research paper (scientific journal)  

DOI： https://doi.org/10.1016/j.tcs.2022.01.033

DOI： https://doi.org/10.1016/j.tcs.2022.01.033

Language：English   Publishing type：Research paper (scientific journal)  

We consider a generalized riffle shuffle on the colored permutation group and derive a determinantal formula for the probability of finding descents at given positions, proof of which is based on the bijection between the set of shuffles in question and that of non-intersecting lattice paths.

DOI： https://doi.org/10.1016/j.disc.2021.112599

Language：English   Publishing type：Research paper (scientific journal)