Multinomial Coefficients ------------------------ Let us adopt the standard notation for multinomial coefficients. That is, for an integer n and a vector of integers m, define --- m! = | | m[j]! [1a] j --- |m| = > m[j] [1b] --- j n! C(n,m) = ---------- [1c] m!(n-|m|)! If |m| > n or m[j] < 0 for any j, C(n,m) = 0. For example, 7! C(7,[3,2]) = -------- = 210 3! 2! 2! To compute the number of factors of a prime p in C(n,m), we start by computing the number of factors of p in n!. Counting Prime Factors of n! ---------------------------- Let us count the number of factors of a prime p in n! A factor of p will come from each multiple of p less than n; that is, floor(n/p). This only counts the multiples of p^2 once, so we add 1 for each multiple of p^2; that is floor(n/p^2). This only counts the multiples of p^3 twice, so we add 1 for each multiple of p^3; that is floor(n/p^3). Continuing this way, we get the number of factors of p in n! to be oo --- n > floor(---) [2] --- p^j j=1 Write n in base p: --- k n = > n p [3] --- k k Then, for any j, n --- k-j floor(---) = > n p [4] p^j --- k k>j Summing over all j >= 1, we get oo --- n --- p^k-1 > floor(---) = > n ----- --- p^j --- k p-1 j=1 k --- = (n - > n ) / (p-1) [5] --- k k Thus, the number of factors of p in n! is n, less the sum of the base p digits of n, divided by p-1. Counting Prime Factors of Multinomial Coefficients -------------------------------------------------- Write m[j] in base p: --- k m[j] = > m [j] p [6] --- k k Write r = n-|m| in base p: --- k r = > r p [7] --- k k The number of factors of p in C(n,m) is the number of factors of p in n! minus the number of factors of p in (n-|m|)! minus the sum of the number of factors of p in the m[j]. That is, using [5], 1 --- --- --- --- --- [ (n - > n ) - (r - > r ) - > (m[j] - > m [j]) ] p-1 --- k --- k --- --- k k k j k 1 --- = --- > |m | + r - n [8] p-1 --- k k k k Equation [8] follows since --- n - r - > m[j] = n - (n-|m|) - |m| = 0 --- j Not only is [8] the number of factors of p in C(n,m), it is also the number of base p carries that occur when adding the m[j] and r to get n. That is because every time a carry takes p from the sum of one column and adds 1 to the next column, the difference in the sum of the digits increases by p-1. For example, let p = 7 and consider the base 7 sum 214 146 5 --- 401 The sum of the digits in the addends is 23 while the sum of the digits in the sum is 5; a difference of 18 = 3(7-1). There is a carry of 2 from the 1s column to the 7s column, and then a carry of 1 from the 7s column to the 49s column; 3 carries. Thus, there are 3 factors of 7 in C(197,[109,83]) (verification left as an exercise for the reader). Therefore, the only way that C(n,m) is not divisible by p is if there are no base p carries when adding the m[j] and r to get n; that is, if |m_k| + r_k = n_k [9a] for every k. Since r = n-|m|, this is the same as saying |m_k| <= n_k [9b] for every k. Summary ------- The number of factors of p in C(n,m) is given by 1 --- --- > |m | + r - n p-1 --- k k k k which is also the number of base p carries that occur when adding the m[j] and n-|m| to get n. C(n,m) is not divisible by p if and only if |m_k| <= n_k for every k. Rob Johnson