Odd Multiplicities in Pascal's Triangle

116 Views Asked by At

This is more of a knowledge-sharing post, but I would love more insight. I was looking at Pascal's triangle and I was curious which numbers appear precisely an odd number of times. My first observations were:

  1. 1 appears infinitely often, so it is not a candidate.
  2. If $x$ appears an odd number of times, then $x={2n\choose n}$ for some $n$ (if not, then due to the symmetry of Pascal's triangle, $x$ would appear an even number of times).
  3. The first occurrence of $x$ is $x={2n\choose n}$ (any preceding rows contain strictly smaller numbers).
  4. The last occurrences of $x\ne 1$ are at $x={x\choose 1}$ and $x={x\choose x-1}$.
  5. There are two diagonals that intersect at $x$. Between (and including) those two diagonals (below row $2n$) contain numbers strictly larger than $x$.

I haven't made much headway beyond this, so I turned to computation. I recognized that the diagonals of the triangle are strictly ascending (except those lines of 1s on the border, of course). This means that I can perform a binary search on each diagonal to locate an occurence of $x$. As well, symmetry means I only need to check the left- or right-side diagonals. Observation (4) means I can start at the 2nd diagonal (the triangular numbers, 1,3,6,...), and point (5) means I only have to check up to the $n-1$ diagonal.

I wrote a Python program to test up to $398\choose199$ and I didn't find any numbers with odd multiplicity greater than three. This means, for example, that there are no integers smaller than $\approx 2.58026316\cdot10^{118}$ that appear 5 times.


I started off looking at the as-of-yet unproven Singmaster's Conjecture, and my gut instinct was to look instead at the cases of odd multiplicity. My hunch is that there are no numbers that have odd multiplicity greater than 3.

It's a super accessible problem, so maybe I've infected a few more minds. I'm also unsure if this belongs on math.stackexchange or MO.


Python code:

# x is our candidate, starting at (2n-2) choose (n-1).
x=2
# To compute the next x, we need to multiply by (2n-1)(2n)/(n*n)
# This simplifies to 2*(2n-1)/n
for n in range(2,200):
  x*=(n+n-1)
  x+=x
  x/=n
#now we have our next candidate
#We need to search through the diagonals, we'll start at k=2, the 2nd diagonal (the triangular numbers)
#These evaluate to f(j)=(j(j-1)(j-2)...(j-k+1))/k!
#It's a strictly ascending sequence, so we can use a binary search.
  e=1   #this will be our k!
  print("%s : %s digits : %s" % (n,len(str(x)),x))
  for k in range(2,n):
    e*=k
    mn=n+1  #performing a binary search, this is the lower bound
    mx=x    #this is the upper bound
    p=x*e   #multiplication is generally faster than division, so instead of comparing y/k!==x, we'll test y==x*k!
    f=True
    while f and mn<mx:
      j=(mn+mx)>>1  #subdivide the interval into halves
      z=1   #computing j(j-1)(j-2)...(j-k+1)
      for f in range(k):
        z*=(j-f)
      f=z!=p  #set f=False if we have a match, causing the loop to exit early
      if z<p:
        mn=j+1  #set the new lower bound
      else:
        mx=j    #set the new upper bound
    if z==p:
      print("  %d  %d=>%d" % (e,j,z/e))