Generalized Binomial Coefficients from Multiplicative and Divisible Functions

Given a function f from the natural numbers to the natural numbers, one way to generalize the binomial coefficient is via

\displaystyle \binom{n+m}{n}_f = \frac{ \prod_{i=1}^{n+m} f(i)}{ \left( \prod_{i=1}^n f(i) \right) \left( \prod_{i=1}^m f(i) \right)}.

The usual binomial coefficient \binom{n+m}{n} of course has f as the identity function f(n) = n.

Question: What kinds of functions f guarantee that \binom{m+n}{n}_f is an integer for all natural values of n and m?  A famous paper by Knuth and Wilf [2] includes a proof that strongly divisible functions (i.e., functions satisfying \gcd(f(m), f(n)) = f(\gcd (m,n)) guarantee this property.  The most famous strongly divisible function is probably the Fibonacci sequence F_n, so the binomial coefficient \binom{n+m}{n}_F is always an integer.

Another answer to this question comes from a paper [1] Tom Edgar and I just published.  We prove that functions that are both multiplicative and divisible also guarantee that \binom{m+n}{n}_f is an integer for all natural values of n and m.  (Multiplicative functions have f(mn) = f(m)f(n) when m and n are relatively prime.  Divisible functions have f(m)|f(n) whenever m|n.)  The class of multiplicative and divisible functions includes Euler’s totient, Dedekind’s psi, as well as many others.  (See Appendix A in our paper for a long list of some of these.)  It also includes the class of completely multiplicative functions (i.e., f(mn) = f(m)f(n) for all natural numbers m and n).  The class of multiplicative and divisible functions has overlap with the strongly divisible class of functions, but it is neither a subset nor a superset of it.

Tom and I start by proving the following formula for the generalized binomial coefficient when f is multiplicative:

\displaystyle \binom{n+m}{n}_f = \prod_p \left( \prod_{i \geq 0} \left( \frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^p_i}\right),

where the outer product is taken over all primes p.  Also, \epsilon^p_i is defined to be 1 if there is a carry in the ith position when m and n are added in base p and 0 otherwise.  Since the condition “f(p^i) divides f(p^{i+1}) for all primes p and nonnegative integers i” turns out to be equivalent to f being divisible, the integrality result follows.

Our formula also allows us to give a quick proof of Kummer’s Theorem on the prime factorization of the binomial coefficients, as f(p^{i+1})/f(p^i) = p when f is the identity function.

In addition, we prove that generalized Catalan numbers C_f = \frac{1}{f(n+1)} \binom{2n}{n}_f are always integers when f is both multiplicative and divisible.  (Actually, we prove this for generalized Fuss-Catalan numbers and then derive the usual Catalan numbers as a special case.)

References

  1. Tom Edgar and Michael Z. Spivey, “Multiplicative Functions, Generalized Binomial Coefficients, and Generalized Catalan Numbers,” Journal of Integer Sequences 19 (1): Article 16.1.6, 2016.
  2. Donald E. Knuth and Herbert S. Wilf, “The Power of a Prime That Divides a Generalized Binomial Coefficient,” Journal für die reine und angewandte Mathematik 396: 212-219, 1989.

 

Posted in binomial coefficients, elementary number theory, number theory | 2 Comments

Integrality of the Catalan Numbers via Kummer’s Theorem

Why is the nth Catalan number, \binom{2n}{n}/(n+1), an integer?  If you know one of its combinatorial interpretations, then the answer is clear, but how do you get integrality strictly from this formula?  In this post I’m going to discuss how one can use Kummer’s Theorem to prove that the Catalan numbers are integers.

Kummer’s Theorem states that the highest power of a prime p dividing the binomial coefficient \binom{n+m}{n} is the number of carries when m and n are added in base p.

Proof.  Assuming we already know that the binomial coefficient \binom{2n}{n} is an integer, we only need to consider primes p that divide n+1 in order to prove \binom{2n}{n}/(n+1) is an integer.  So, suppose p is a prime that divides n+1.  It may be that p^2, or p^3, or some higher power of p divides n+1 as well.  So let’s let p^r be the highest power of p that divides n+1.  Since p^r | (n+1), the base p representation of n+1 has r zeros at the end.  (Similarly, the fact that nine thousand, seven hundred has 10^2 as the highest power of 10 that divides it means that its base 10 representation, 9700, has two zeros at the end.)  This means that the base p representation of n has r instances of p-1 at the end.  (In the previous example, we see this with the fact that 9699 has two copies of 9 at the end.)  When n is added to itself in base p, then, we get carries in the ones place, the p‘s place, and so forth, up through at least the p^{r-1} place, for a total of at least r carries.  Thus, by Kummer’s Theorem, \binom{2n}{n} is divisible by p^r.  Since we can make a similar argument for all primes p that divide n+1, \binom{2n}{n} is divisible by n+1.  Therefore, \binom{2n}{n}/(n+1) is an integer.  \square

Pomerance makes this argument in his paper [1] and extends it to divisors n+k and n-k instead of n+1.  Tom Edgar and I have a paper that will soon be appearing in the Journal of Integer Sequences that generalizes it in another way – to generalized Fuss-Catalan numbers that are formed from generalized binomial coefficients.

References

  1.  Carl Pomerance, “On numbers related to Catalan numbers,” preprint.
Posted in binomial coefficients, Catalan numbers, number theory | Leave a comment

An arcsecant/arctangent integral

Recently in my integral calculus class I assigned the problem of evaluating

\displaystyle \int \frac{dx}{x \sqrt{x^4-1}}.

I intended for the students to recognize the integrand as similar to the derivative of arcsecant:

\displaystyle \frac{d}{dx} \sec^{-1} x = \frac{1}{x \sqrt{x^2-1}}.

This leads to the substitution u = x^2, with du = 2x dx.  The original integral then becomes

\displaystyle \frac{1}{2} \int \frac{2x dx}{x^2 \sqrt{x^4-1}} = \frac{1}{2} \int \frac{du}{u \sqrt{u^2-1}} = \frac{1}{2} \sec^{-1} u + C = \frac{1}{2} \sec^{-1} (x^2) + C.

However, one of my students, Max, tried the substitution u = \sqrt{x^4-1} (on the general principle that letting u be the most complicated part of the integral is a good idea).  This gives du = 2x^3/\sqrt{x^4-1}.  Max then got stuck with the substitution.  The problem was in the inverse trig functions section of the text, though, and so he guessed \arctan (\sqrt{x^4-1}) as an antiderivative.  Checking this, he obtained

\displaystyle \frac{d}{dx} \arctan (\sqrt{x^4-1}) = \left(\frac{1}{x^4-1+1} \right) \left(\frac{1}{2}\right) \left(\frac{1}{\sqrt{x^4-1}}\right) \left(4x^3\right) = \frac{2}{x \sqrt{x^4-1}}.

Since this is only off by a factor of 2, he concluded that the answer is

\displaystyle \int \frac{dx}{x \sqrt{x^4-1}} = \frac{1}{2} \arctan (\sqrt{x^4-1}) + C!

Why are both of these answers correct?  Let’s complete the evaluation of the integral using Max’s substitution, and then we’ll show that the two answers are actually equal to each other.

With u = \sqrt{x^4-1}du = 2x^3/\sqrt{x^4-1}, and x^4 = u^2+1, we can rewrite the original integral and evaluate it via

\displaystyle \frac{1}{2} \int \frac{2x^3 dx}{x^4 \sqrt{x^4-1}} = \frac{1}{2} \int \frac{du}{u^2+1} = \frac{1}{2} \arctan u + C = \frac{1}{2} \arctan (\sqrt{x^4-1}) + C.

It’s easy to get stuck here because the correct evaluation doesn’t actually substitute u into the integrand (at least not by itself).  Instead, the radical becomes part of the du, and the remaining expression in x gets replaced by u^2+1.  The rest of the evaluation is surprisingly simple, but getting to here is the trick.

The reason the two answers are equal has to do with trigonometry.  If \theta = \sec^{-1} (x^2), then \sec \theta = x^2.  Using the trig identity \tan^2 \theta + 1 = \sec^2 \theta, we have \tan \theta = \sqrt{\sec^2 \theta - 1} = \sqrt{x^4-1}.  Thus \theta can also be expressed as \theta = \arctan (\sqrt{x^4-1}).  (This can also be seen by setting x^2 and 1 as the hypotenuse and adjacent side of a right triangle; the Pythagorean theorem plus the triangle definition of tangent gets you the rest of the way.)

I’ve come across different-looking answers to the same integral evaluation before, but this is probably the most complicated different-looking pair of answers I’ve seen.

Posted in calculus | Leave a comment

Tiling Proofs for the Sum of Even or Odd-Indexed Binomial Coefficients

Two basic identities for the binomial coefficients are contained in the equation \displaystyle \sum_{k \geq 0} \binom{n}{2k} = \sum_{k \geq 0} \binom{n}{2k+1} = 2^{n-1}.   There are multiple ways to prove these identities (even if you restrict yourself to combinatorial proofs).  In this post I’m going to discuss a tiling or coloring-based combinatorial proof that I find aesthetically satisfying.

Proof: Suppose you have a 1 \times (n-1) board.  If you can color each square in the board either black or white, there are 2^{n-1} ways to color the board.

There are also n grooves in this board: n-2 grooves between the squares plus a groove (numbered 0 before the first square and a groove after the last square.  Suppose we select an even number 2k of those grooves: a_1, a_2, \ldots, a_{2k}.  We can then construct a coloring of the board by coloring black the squares between grooves [a_{2i-1}, a_{2i}], 1 \leq i \leq k, and coloring the remaining squares white.  This produces a coloring with k runs of black tiles.  For example, if n = 10, selecting grooves 1, 3, 4, and 5 (so that k = 2) yields the coloring WBBWBWWWW.  There are \binom{n}{2k} ways to choose 2k even numbers from n.  Summing over all possible values of k, we have the number of ways to color the board as \displaystyle \sum_{k \geq 0} \binom{n}{2k}.

Instead of choosing an even number of grooves, we could also choose an odd number 2k+1 of grooves: a_0, a_1, \ldots, a_{2k}.  Now we color black the squares between grooves [a_{2i-1}, a_{2i}] as before, but we also color black the squares between grooves 0 and a_0.  Color the remaining squares white.  This selection might not have k+1 runs of black tiles because a_0 might be 0.  However, it will have exactly k transitions from a white run to a black run.  For example, selecting grooves 0, 1, 3, 4, and 5 produces the same coloring WBBWBWWWW as in the previous example.  It has two white-to-black transitions, and k = 2.  There are \binom{n}{2k+1} ways to choose 2k+1 odd numbers from n.  Summing over all possible values of k, we also have the number of ways to color the board as \displaystyle \sum_{k \geq 0} \binom{n}{2k+1}.

Therefore, \displaystyle \sum_{k \geq 0} \binom{n}{2k} = \sum_{k \geq 0} \binom{n}{2k+1} = 2^{n-1}.


There are simpler combinatorial proofs of these identities.  For example, one can count the number of ways to form, out of n people, a committee with an even only or odd only number of members.  One can also construct a one-to-one mapping between even-sized committees and odd-sized committees, showing that there must be an equal number of each.  Proofs That Really Count [1] (p. 65 and p. 81, respectively) discusses both of these proofs.

References

  1.  Arthur Benjamin and Jennifer Quinn, Proofs That Really Count, MAA, 2003.
Posted in binomial coefficients, combinatorics | Leave a comment

Combinatorial Proofs of Two Hagen-Rothe Identities in Concrete Mathematics

There are two binomial coefficient identities in Concrete Mathematics that have bothered me for years:  They look they should have combinatorial proofs, but I couldn’t for the life of me think of what those might be.  (In Concrete Mathematics they are proved with generating functions.)  Well, I just recently found those combinatorial proofs I was looking for.

Here are the identities. [2, p. 202]

(1)  \displaystyle \sum_k \binom{tk+r}{k} \binom{tn-tk+s}{n-k} \frac{r}{tk+r} = \binom{tn+r+s}{n}.

(2)  \displaystyle \sum_k \binom{tk+r}{k} \binom{tn-tk+s}{n-k} \frac{r}{tk+r} \cdot \frac{s}{tn-tk+s} = \binom{tn+r+s}{n} \frac{r+s}{tn+r+s}.

The key idea I didn’t have before is the general ballot theorem, which states that the number of lattice paths from (0,0) to (n,m), m > rn, that never touch the line y = rx after (0,0) is given by \frac{m-rn}{m+n} \binom{m+n}{m}. This can be proved combinatorially; see, for example, Renault’s paper [5].

Identity (1) counts the number of lattice paths from (0,0) to (n, (t-1)n + r+ s).  The right-hand side is straightforward, since \binom{n+m}{n} counts the number of lattice paths from (0,0) to (n,m).  For the left side, condition on the number of right steps k a lattice path takes after touching the line y = (t-1)x+s for the last time.  By the general ballot theorem, the number of paths from (n-k, (t-1)(n-k)+s) to (n, (t-1)n + r + s) that never touch the line y = (t-1)x + s after the initial point is \frac{r}{tk+r} \binom{tk+r}{k}.  (This is because there are k right steps and (t-1)k + r up steps.)  Also, the number of lattice paths from (0,0) to (n-k, (t-1)(n-k) + s) is \binom{t(n-k)+s}{n-k}.  Summing over all possible values of k gives the left side of Identity (1).

Identity (2) is similar, although it counts the number of lattice paths from (0,0) to (n, (t-1)n + r + s) that never touch the line y = (t-1)x after (0,0).  The right side follows from the general ballot theorem.  For the left side, condition on the last place (k, (t-1)k + r) a lattice path touches the line y = (t-1)x + r.  By the general ballot theorem, there are \frac{r}{tk+r} \binom{tk+r}{k} paths from (0,0) to (k, (t-1)k + r) that never touch the line y = (t-1)x after (0,0).  Also by the general ballot theorem, there are \frac{s}{tn-tk+s} \binom{tn-tk+s}{n-k} lattice paths from (k, (t-1)k + r) to (n, (t-1)n + r + s) that never touch the line y = (t-1)x + r after the initial point.  Multiplying these together and summing over all values of k gives the left side.

I don’t think these proofs are new; for example, Chu [1] mentions lattice path proofs of these identities in books by Mohanty [3] and Narayana [4].

References

  1. Wenchang Chu, “Elementary Proofs for Convolution Identities of Abel and Hagen-Rothe,” Electronic Journal of Combinatorics 17, Note #N24, 2010.
  2. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.
  3. S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, 1979.
  4. T. V. Narayana, Lattice Path Combinatorics with Statistical Applications, Univ. of Toronto Press, 1979.
  5. Marc Renault, “Lost (and Found) in Translation: André’s Actual Method and Its Application to the Generalized Ballot Problem,” American Mathematical Monthly 115 (4), 2008, pp. 358-363.
Posted in combinatorics, lattice paths | Leave a comment

Vandermonde’s Identity from the Generalized Product Rule

Vandermonde’s Identity, \displaystyle \sum_{k=0}^r \binom{n}{k} \binom{m}{r-k} = \binom{n+m}{r}, is one of the more famous identities involving the binomial coefficients.  A standard way to prove it is with the following combinatorial argument.

How many ways are there to choose a committee of size r from a group of n men and m women?  By definition of the binomial coefficient, the answer is \binom{n+m}{r}.  Alternatively, condition on the number k of men on the committee.  There are \binom{n}{k} ways to choose the men, and then there are \binom{m}{r-k} ways to choose the remaining r-k members of the committee from the m women.  Summing over all possible values of k gives the left side.

In this post we’re going to give a much less standard proof of Vandermonde’s Identity — one via the generalized product rule for derivatives.  In addition, while the combinatorial proof requires n and m to be natural numbers, our proof holds for all real numbers.

The generalized product rule, sometimes known as Leibniz’s Generalized Rule, gives a formula for the nth derivative of the product of two functions.  Here it is:

\displaystyle (fg)^{(n)}(x) = \sum_{k=0}^n \binom{n}{k} f^{(k)}(x) g^{(n-k)}(x).

This formula can be easily proved by induction.

Let f(x) = x^n, and let g(x) = x^m.  We know that the rth derivative of a power function like x^n is n^{\underline{r}} x^{n-r}, where n^{\underline{r}} is the falling factorial n(n-1) \cdots (n-r+1).  Now, let’s look at the rth derivative of f(x) g(x) = x^{n+m}.  As we just argued, this is (n+m)^{\underline{r}} x^{n+m-r}.  By the generalized product rule, then, we have

\displaystyle (n+m)^{\underline{r}} x^{n+m-r} = \sum_{k=0}^r \binom{r}{k} n^{\underline{k}} x^{n-k} m^{\underline{r-k}} x^{m-r+k}

\displaystyle \implies (n+m)^{\underline{r}} x^{n+m-r} = \sum_{k=0}^r \frac{r!}{(r-k)! k!} n^{\underline{k}} m^{\underline{r-k}} x^{n+m-r}

\displaystyle \implies \frac{(n+m)^{\underline{r}}}{r!} x^{n+m-r} = \left(\sum_{k=0}^r \frac{n^{\underline{k}}}{k!} \frac{m^{\underline{r-k}}}{(r-k)!}\right) x^{n+m-r}.

The coefficients of the two expressions here must be equal in order for the expressions themselves to be equal.  In addition, using the definition of the generalized binomial coefficient, we have \binom{n}{k} = \frac{n^{\underline{k}}}{k!}.  (This allows binomial coefficients to be defined for values of n that are not natural numbers.)  All of this gives us Vandermonde’s Identity,

\displaystyle \binom{n+m}{r} = \sum_{k=0}^r \binom{n}{k} \binom{m}{r-k}.

Posted in binomial coefficients, calculus, combinatorics | Leave a comment

Combinatorial Proofs for the Binomial and Alternating Binomial Power Sums

In this post I give combinatorial proofs of formulas for the binomial and alternating binomial power sums: \displaystyle \sum_{k=0}^n \binom{n}{k} k^m and \displaystyle \sum_{k=0}^n \binom{n}{k} k^m (-1)^k.

Here’s the first.

Identity 1.

\displaystyle \sum_{k=0}^n \binom{n}{k} k^m = \sum_{j=0}^m \left\{ {m \atop j} \right\} \binom{n}{j} j! 2^{n-j}.

Proof.  Both sides count the number of functions from \{1, 2, \ldots, m\} to subsets of \{1, 2, \ldots, n\}.  For the left side, condition on the number of elements in the codomain.   If there are k elements in the codomain, there are \binom{n}{k} ways to choose those k elements from the n possible.  Once the k elements in the codomain are chosen, there are k choices for f(1)k choices for f(2), and so forth, for a total of k^m choices for the function values from f(1) to f(m).  Summing over all possible values of k gives the left side.

For the right side, condition on the number of elements in the image.  If there are j elements in the image, there are \binom{n}{j} ways of choosing these j from the n possible.  Then there are 2^{n-j} ways to complete the codomain, as any of the remaining n-j elements in \{1, 2, \ldots, n\} could either be in the codomain or not.  In addition, there are \left\{ {m \atop j } \right\} j! onto functions from a set with m elements to a set with j elements.  Finally, sum over all possible values of j.    \square

And the second.

Identity 2.

\displaystyle \sum_{k=0}^n \binom{n}{k} k^m (-1)^k = (-1)^n \left\{ m \atop n \right\} n!.

Proof.  We use the same interpretation as in the first proof.  The left side is the difference between the number of functions from \{1, 2, \ldots, m\} to subsets of \{1, 2, \ldots, n\} with an even-sized codomain and the number of such functions with an odd-sized codomain.  We construct a sign-reversing involution on the set of functions from \{1, 2, \ldots, m\} to \{1, 2, \ldots n\}.

Given a function f: \{1, 2, \ldots, m\} \mapsto S, where S is a subset of \{1, 2, \ldots, n\}, let y be the largest-numbered element of \{1, 2, \ldots, n\} that is not in the image of f.  Define \sigma(f) to be the function g: \{1, 2, \ldots, m\} \mapsto T, where T \subseteq \{1, 2, \ldots, n\} such that f(x) = g(x) for all x \in \{1, 2, \ldots, m\} but that T = S \cup \{y\} if y \not\in S and T = S - \{y\} if y \in S.  In other words, f and g are the same function except that the codomain of exactly one of them contains the largest-numbered element not in their common image.  From this definition we can see that \sigma is both sign-reversing (as it maps functions with even-sized codomains to those with odd-sized codomains and vice versa) and an involution.  Thus the functions for which \sigma is defined are canceled out in the sum on the left.  The only functions for which \sigma is not defined are those for which y does not exist.  These are the onto functions from \{1, 2, \ldots, m\} to \{1, 2, \ldots, n\}.  There are \left\{ {m \atop n } \right\} n! of these, and their sign is determined by whether n is even or odd.  \square

For proofs of these two identities by using the formulas for \displaystyle \sum_{k=0}^n \binom{n}{k} k^{\underline{m}} and \displaystyle \sum_{k=0}^n \binom{n}{k} k^{\underline{m}} (-1)^k and then using the Stirling numbers of the second kind to convert from falling factorial powers to ordinary powers, see my paper [1].

References

[1]  Michael Z. Spivey.  “Combinatorial Sums and Finite Differences.”  Discrete Mathematics 307 (24): 3130-3146, 2007.

Posted in binomial coefficients, combinatorics, Stirling numbers | Leave a comment