Cancer cells frequently undergo chromosome missegregation events during mitosis, whereby the copies of a given chromosome are not distributed evenly among the two daughter cells, thus creating cells with heterogeneous karyotypes. A stochastic model tracing cellular karyotypes derived from clonal populations over hundreds of generations was recently developed and experimentally validated, and it was capable of predicting favorable karyotypes frequently observed in cancer. Here, we construct and study a Markov chain that precisely describes karyotypic evolution during clonally expanding cancer cell populations. The Markov chain allows us to directly predict the distribution of karyotypes and the expected size of the tumor after many cell divisions without resorting to computationally expensive simulations. We determine the limiting karyotype distribution of an evolving tumor population, and quantify its dependency on several key parameters including the initial karyotype of the founder cell, the rate of whole chromosome missegregation, and chromosome-specific cell viability. Using this model, we confirm the existence of an optimal rate of chromosome missegregation probabilities that maximizes karyotypic heterogeneity, while minimizing the occurrence of nullisomy. Interestingly, karyotypic heterogeneity is significantly more dependent on chromosome missegregation probabilities rather than the number of cell divisions, so that maximal heterogeneity can be reached rapidly (within a few hundred generations of cell division) at chromosome missegregation rates commonly observed in cancer cell lines. Conversely, at low missegregation rates, heterogeneity is constrained even after thousands of cell division events. This leads us to conclude that chromosome copy number heterogeneity is primarily constrained by chromosome missegregation rates and the risk for nullisomy and less so by the age of the tumor. This model enables direct integration of karyotype information into existing models of tumor evolution based on somatic mutations.

In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. (In fact, a special case of this algorithm is commonly used to hand-sort files.) However, it is not obvious that this algorithm necessarily terminates. We show that in fact the algorithm terminates after at most 2n−1 – 1 steps in the worst case (confirming a conjecture of L. Larson), and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation.

A permutation $\pi$ is realized by the shift on N symbols if there is an infinite word on an N-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as $\pi$. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [J. M. Amigó, S. Elizalde, and M. B. Kennel, J. Combin. Theory Ser. A, 115 (2008), pp. 485–504] that the shortest forbidden patterns of the shift on N symbols have length $N+2$. In this paper we give a characterization of the set of permutations that are realized by the shift on N symbols, and we enumerate them according to their length.