Given first X natural numbers(1,2,3,4,....x) and calculate the sum of the maximum value of each subsequence of size n these numbers.
example x=2 and n=2 sequence -> 1,2
subsequnces-{1,2},{2,1},{1,1},{2,2} sum=max{1,2}+max(2,1)+max(1,1)+max(2,2) therefore sum =7
Idea:I have a idea but cant formulate it completely
Take the largest value of the sequence X and then take n-1 values from X-1 so that becomes 1*C(x-1,n-1)*n!
Now take 2 X so that leaves us with n-2 choices from x-1 elements and therfore C(x-1,n-1)*n!/2! and so on in all these cases value would be 6 so multiply the entire thing with 6
Now think for max value x-1 and do the above process
Basically thinking how many times each max value can occur.
I was looking for a way to exactly think of this question and how to formulate into a formula.If thier are some other method or idea other than what i said i would highly want to know it.
The number of sequences of length $n$ for which 1 is maximum is equal to 1 (11...1 $n$ times). The number of sequences of length $n$ for which 2 is maximum is equal to $2^n-1$ (consider sequences in which each element is 1 or 2, and ensure that there's at least one 2). More generally, $i$ is maximum in $i^n-(i-1)^n$ sequences (i.e. those sequences consisting of numbers from 1 to $i$, and having at least one $i$).
Thus, the sum is $\sum_{i=1}^{n} i\left(i^n-(i-1)^n \right)$, which can be simplified further.