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.

  • $\begingroup$ consider decimal numbers from 111 to 999. Each number has a "roof" i.e. a maximal figure, for example 321 -> 3, 788 -> 8. Calculate the sum of roofs of the given numbers. $\endgroup$ – Nicholas Boyku Jun 17 '18 at 0:19
  • $\begingroup$ What was the intution behind using this idea $\endgroup$ – Srin Chow Jun 17 '18 at 5:31
  • $\begingroup$ Your example does not seem to fit your problem statement as I understand it. $2,2$ is not a subsequence of $1,2$. $\endgroup$ – awkward Jun 17 '18 at 12:49
  • $\begingroup$ sorry its all combinations with position mattering $\endgroup$ – Srin Chow Jun 17 '18 at 16:23

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.

  • $\begingroup$ I think we also have to consider subsequences $S$ with maximum element $j\in S$ where $S$ is a proper subset of $\{1,2,\ldots,j\}$. Neverthless (1+) for this nice starter. $\endgroup$ – Markus Scheuer Jun 18 '18 at 13:25
  • 1
    $\begingroup$ Thanks for the correction. $\endgroup$ – Aravind Jun 19 '18 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.