@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
