Number of digits in row of Pascal's triangle is O(n2)
Out of curiosity, continuing off of the linked question, I present the following question:
What is the asymptotic growth of the sum of all the digits in the nth row of Pascal's Triangle, when all the binomial coefficients are written in base b?
It can be assumed that b is a positive integer.
Answer
You can assume that most of the digits are random, so if there are m digits in the sum, the sum of digits is about b−12m. The leading digits may be biased low, but there are only n leading digits in row n, so the non-leading digits will dominate. The sum of digits is then b−12n2∈O(n2)
No comments:
Post a Comment