Symmetric and Asymptotically Symmetric Permutations

MaRDI QIDQ6208237zbMATH OpenFDO

Authors Joshua Cooper, Andrew Petrarca

Publication date 27 January 2008

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Binomial coefficients; factorials; (q)-identities (11B65)

Abstract: We consider two related problems arising from a question of R. Graham on quasirandom phenomena in permutation patterns. A ``pattern in a permutation $sigma$ is the order type of the restriction of $sigma:[n]o[n]$ to a subset $Ssubset[n]$. First, is it possible for the pattern counts in a permutation to be exactly equal to their expected values under a uniform distribution? Attempts to address this question lead naturally to an interesting number theoretic problem: when does $k!$ divide $$? Second, if the tensor product of a permutation with large random permutations is random-like in its pattern counts, what must the pattern counts of the original permutation be? A recursive formula is proved which uses a certain permutation ``contraction.

This page was built for publication: Symmetric and Asymptotically Symmetric Permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6208237)