Thursday, October 10, 2019

asymptotics - Sum of digits in base b the nth row of Pascal's Triangle



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 b12m. 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 b12n2O(n2)


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...