×

A note on divisors of multinomial coefficients. (English) Zbl 1314.05023

Summary: We introduce a simple equivalence relation on ordered rooted tree graphs. As a consequence we show that \[ \frac{(n_0 + n_1 + n_2 + \dots + n_m - 1)!}{n_0 ! n_1 ! n_2 !\dots n_m!} \] is divisible by \(n_0 + 1\), where \(n\), \(n_0\), \(n_1\), \(n_2\dots , n_m\) are nonnegative integers such that \(n - 1 = n_1 + 2n_2 + \cdots + mn_m\), \(n_0 = n - (n_1 + n_2 + \cdots + n_m)\). There is at least one \(a \in \{n_0 + 1, n_i \mid i > 0\}\) such that \(a\) is an odd positive integer, and for every divisor \(d > 1\) of every \(i + 1\) where \(n_i > 0\) and \(i > 0\), there is at least one \(b \in U_i = \{n_0 + 1, n_j, n_i - 1 \mid j > 0\) and \(j \not = i\}\) which is not divisible by \(d\).
In particular, it follows that \(C_j \equiv 0 \pmod {j + 2}\), where \(j>2\) is an odd integer such that \(j-1\) is not divisible by 3 and \(C_j\) denotes the \(j\)th Catalan number.

MSC:

05A19 Combinatorial identities, bijective combinatorics
05C05 Trees
11B65 Binomial coefficients; factorials; \(q\)-identities
11B75 Other combinatorial number theory
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Alter and K.K Kubota, Prime and prime power divisibility of Catalan numbers, Journal of Combinatorial Theory, Series A, 15 (1973), 243-246. · Zbl 0273.10010
[2] G. M. Bergman, On common divisors of multinomial coefficients, Bulletin of the Australian Mathematical Society 83 (2011), pp. 138-157. ISSN 0004-9727. · Zbl 1225.11024
[3] W. Y. C. Chen, A general bijective algorithm for trees, Proc. Nati. Acad. Sci. USA, 87 (1990), 9635-9639. · Zbl 0707.05019
[4] E. Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory, 117 (2006), 191-215. · Zbl 1163.11310
[5] R. Diestel, Graph Theory, Electronic Edition 2005, Springer-Verlag Heidelberg · Zbl 1074.05001
[6] D. Knuth, The art of computer programming vol 1. Fundamental Algorithms, 3rd Edition, Addison-Wesley, 1997. ISBN 0-201-89683-4. · Zbl 0895.68055
[7] C. Pomerance, On numbers related to Catalan numbers, 2013, Submitted for publication, http://www.math.dartmouth.edu/ carlp/catalan
[8] R. P.Stanley, Enumerative Combinatorics, Volume 2, Cambridge University Press, Cambridge, 1999. · Zbl 0928.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.