An application of Fourier transforms on finite Abelian groups to an enumeration arising from the Josephus problem

详细信息    查看全文

• 作者：Gregory L. Wilson ; Christopher L. Morgan
• 关键词：Fourier transform on groups ; Josephus problem ; Hermite normal form ; Smith normal form
• 刊名：Journal of Number Theory
• 出版年：2010
• 出版时间：April 2010
• 年：2010
• 卷：130
• 期：4
• 页码：815-827
• 全文大小：203 K

文摘

Text

We analyze an enumeration associated with the Josephus problem by applying a Fourier transform to a multivariate generating function. This yields a formula for the enumeration that reduces to a simple expression under a condition we call local prime abundance. Under this widely held condition, we prove (Corollary 3.4) that the proportion of Josephus permutations in the symmetric group S_n that map t to k (independent of the choice of t and k) is 1/n. Local prime abundance is intimately connected with a well-known result of S.S. Pillai, which we exploit for the purpose of determining when it holds and when it fails to hold. We pursue the first case where it fails, reducing an intractable DFT computation of the enumeration to a tractable one. A resulting computation shows that the enumeration is nontrivial for this case.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=DnZi-Znuk-A.