# how to formulate this combinatorics problem?

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.

• 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. – Nicholas Boyku Jun 17 '18 at 0:19
• What was the intution behind using this idea – Srin Chow Jun 17 '18 at 5:31
• Your example does not seem to fit your problem statement as I understand it. $2,2$ is not a subsequence of $1,2$. – awkward Jun 17 '18 at 12:49
• sorry its all combinations with position mattering – 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.
• 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. – Markus Scheuer Jun 18 '18 at 13:25