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

JOURNAL OF NUMBER THEORY

卷:130

Article

Wilson, Gregory L.¹  Morgan, Christopher L.² 

[1] BerrieHill Res Corp, Dayton, OH 45459 USA

[2] Calif State Univ E Bay, Hayward, CA 94542 USA

关键词: Fourier transform on groups;    Josephus problem;    Hermite normal form;    Smith normal form;   

DOI  :  10.1016/j.jnt.2009.11.004

来源: Elsevier

【 摘 要 】

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. (C) 2010 Elsevier Inc. All rights reserved.

【 授权许可】

Free