Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Asymptotic prime-power divisibility
of binomial, generalized binomial,
and multinomial coefficients


Author: John M. Holte
Journal: Trans. Amer. Math. Soc. 349 (1997), 3837-3873
MSC (1991): Primary 05A16; Secondary 11K16
MathSciNet review: 1389778
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents asymptotic formulas for the abundance of binomial, generalized binomial, multinomial, and generalized multinomial coefficients having any given degree of prime-power divisibility. In the case of binomial coefficients, for a fixed prime $p$, we consider the number of $(x, y)$ with $0 \leq x, y < p^n$ for which $\binom {x+y}{x}$ is divisible by $p^{zn}$ (but not $p^{zn+1}$) when $zn$ is an integer and $\alpha < z < \beta $, say. By means of a classical theorem of Kummer and the probabilistic theory of large deviations, we show that this number is approximately $p^{n D((\alpha , \beta ))}$, where $D((\alpha , \beta )) := \sup \{ D(z) : \alpha < z < \beta \}$ and $D$ is given by an explicit formula. We also develop a ``$p$-adic multifractal'' theory and show how $D$ may be interpreted as a multifractal spectrum of divisibility dimensions. We then prove that essentially the same results hold for a large class of the generalized binomial coefficients of Knuth and Wilf, including the $q$-binomial coefficients of Gauss and the Fibonomial coefficients of Lucas, and finally we extend our results to multinomial coefficients and generalized multinomial coefficients.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 05A16, 11K16

Retrieve articles in all journals with MSC (1991): 05A16, 11K16


Additional Information

John M. Holte
Affiliation: Department of Mathematics, Gustavus Adolphus College, St. Peter, Minnesota 56082
Email: holte@gac.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-97-01794-7
PII: S 0002-9947(97)01794-7
Keywords: Binomial coefficients, generalized binomial coefficients, multinomial coefficients, asymptotic enumeration, prime-power divisibility, large deviation principle, carries, Markov chains, multifractals, fractals, $p$-adic numbers
Received by editor(s): December 8, 1995
Received by editor(s) in revised form: March 26, 1996
Article copyright: © Copyright 1997 American Mathematical Society