@priyanka.. SuperSum(k, n) : For any given base X representation there will be X digits.. Now say, the digits are named as A(i) ... such that, A1 < A2 < A3 < .... < A(X)... [ all digits being significant ]
Then SuperSum basically says that what are the no. of (k+1) sized integers that can formed such that the digits in the integers are in non-decreasing order from left to right and ends with A(n) where n <= X... For ex - for Base 5, the digits are 1,2,3, 4, 5 Now SuperSum(1,4) = No. of 2-sized integers that can be formed for base-5, where the integer ends with at A(4) [ i.e. '4' for base-5].. ------------------------------ For simplicity, lets define P(i, j) = SuperSum(i - 1, j).. Therefore, P(k, n) : the no. of (k) sized integers that can formed such that the digits in the integers are in non-decreasing order from left to right and ends with A(n) where n <= X Hence, P(1, i) = 1 P( k, n ) = P(k-1, 1) + P(k-1, 2) + ....+ P(k-1,n) i.e. No. of 'k' sized non-decreasing integers = sum over all i { no. of 'k-1' sized integers that end at A(i) such that A(i)<= A(n) } Now, the P(k, n) equation is nothing but a recurrence equation which should be obvious based on the above explanation.. But, P(k, n) is nothing but (n+k-1) C (k).. i.e SuperSum(k, n) = (n+k) C (k+1)... = SuperSum(k-1, n) * (n+k) / (k+1).. ----------------------------------------------------------------------------------- Probably the next question would be : P(k, n) = (n+k-1) C (k) ?? Well i will explain it with a short example... Base-3 : {1, 2 ,3 } Size : 1 Integers ending No. of integers at 'i' th digit 1 1 2 1 3 1 Size-2 Integers ending No. of integers at 'i' th digit (1)1 1 (1)2, (2)2 2 (1)3, (2)3, (3)3 3 // the brackets above indicate that the integers within the bracket have been used from table 'Size-1' // Basically we are building table 'Size-n' based on table 'Size- (n-1)'... Also you must observe that the 'no. of digits' column of table 'Size-2' is nothing but the cumulative sum of 'no. of digits' column of table 'Size-1'.... The 'no. of digits' column of table 'Size-3' would be 1 3 6 The 'no. of digits' column of table 'Size-4' would be 1 4 10.. Do you observe something ??? [Remember pascal's triangle...] ----------------------------------------------------- A naive approach would be prove: SuperSum(k-1, n) = SuperSum(k-1, n) * (n+k) / (k+1) using induction.. Calculate for SuperSum(1, 1), SuperSum(1, 2),.. SuperSum(1, n) and so on.. and see how it goes... Observe the pattern... ---------------------------------------------- On Jan 10, 8:35 pm, Lucifer <sourabhd2...@gmail.com> wrote: > @atul > > First of all, i must say you are really good at catching my "editing > mistakes" :).. > > Correction: > superSum = ( superSum * ( ( n + i )%1000000007 ) ) / (i+1); > > On Jan 10, 8:29 pm, atul anand <atul.87fri...@gmail.com> wrote: > > > > > > > > > @Lucifier : your reduced form is not generating right output... > > remove modulo and calculate for SuperSum(2,3) > > > On Tue, Jan 10, 2012 at 6:12 PM, priyanka <priyankajag...@gmail.com> wrote: > > > @lucifier : > > > Please tell how you reduce SuperSum ( k, n) into > > > SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1) > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To view this discussion on the web visit > > >https://groups.google.com/d/msg/algogeeks/-/jWq_vujbiCkJ. > > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.