How to solve Sport Jersey problem of CODN2018 contest?
Problem: Count the total possible combination of increasing and decreasing order from 1 to N numbers.
The question asked for number of non-decreasing and number of non-increasing sequences. Every such sequence will have groups of similar numbers present one after the other (because repetition is allowed). There can be ‘N’ groups at most, and there must be at least one group. Once you fix the number of groups, say, ‘R’, you can find the number of ways of splitting ‘N’ into ‘R’ parts. It will be :
{N-1\choose R-1}
Then, for each part, you need to decide what number must be present in it. This is counting the number of ways of selecting ‘R’ numbers out of ‘N’ numbers. The smallest number make up the first part, and so on till the largest number (for increasing sequences). So, now the number of ways is:
{N-1\choose R-1}*{N\choose R}
You need to find the sum of this expression over all possible ‘R’ ie.:
\sum_{R=1}^{N}{N-1\choose R-1}*{N\choose R} = \sum_{R=0}^{N-1}{N-1\choose R}*{N\choose R+1} = \sum_{R=0}^{N-1}{N-1\choose R}*{N\choose N-R-1}
If you use Vandermonde’s identity, this summation will be equal to :
{2*N-1\choose N-1}
The expression for decreasing sequences will also be the same. Finally, you need to subtract the sequences made up of a single number, because those will be counted twice.
2 Likes
Would you please explain the first part with the help of an example.
Suppose N = 4 and R = 3, it means that your sequence is made up of 3 parts. In how many ways can we do this ?
1 1 2
2 1 1
1 2 1
These are the three possibilities. Here, each of the three numbers represents the size of a part. Take the first possibility for example, ie., 1 1 2, I’ll give an example of increasing sequences of this type :
2 3 4 4
If you group same numbers and look at the group sizes, you’ll get 1 1 2. This is what I mean when I say group similar numbers :
2 | 3 | 4 4 (groups are separated by ‘|’)
I’m still confused with N and R. Please elaborate it for further clarification
How does any non-decreasing sequence look ? It will start with some number, that number will be repeated one or more times, and then there will be a different (bigger) number. Again, this number will be repeated one or more times, and the sequence continues like this. I’ll take an example :
Suppose that N=8 Eg : 1 1 2 2 2 3 3 3
Like I mentioned above, there are 1s, followed by 2s, followed by 3s. Basically, this sequence is made up of three different numbers. That is what ‘R’ means (R=3 here). Since the sequence must be increasing, all 1s must be together, all 2s must be together etc.
Like in the above example, once you fix ‘R’, ie., say, you decide that there will be three different numbers, then you need to decide how many times each one should be repeated. If x1,x2,x3 are the number of times each number appears, then you need to find the number of solutions to the equation : x1 + x2 + x3 = N.
In general, the number of solutions to x1 + x2 + x3 + … + xk = N is C(N-1,K-1). Now we know how many times each number will appear, we need to decide the numbers that will appear. For the above example, you need to choose 3 numbers out of 8. This can be done in C(8,3) ways.
This problem is quite similar to finding the number of integer solutions to a+b+c = N, where a >= 0, b >= 0, c >=0. The solution to the problem is {N+R-1}\choose{R-1}.
Say you have 2*N-1 slots in which you are going to select N-1 of them to fill them with partition. The rest of the slots are the numbers from 1 to N. The number of ways is what @hemanth_1 told.
{2N-1}\choose{N-1}
Then, after that double it to get both the orders and remove the sequence made by a single number.
For example, take N=4, we have 7 slots
_ _ _ _ _ _ _
We select 3 partitions
_ | _ _ | _ |
Then fill the rest with numbers based on that partition [1 2 2 3]
1 | 2 2 | 3 |
2 Likes
How could you say that "this problem is quite similar to finding the number of integer solutions to a+b+c=N" ?
Take R = N, then it will be clear. The solution to a_1 + a_2 + a_3 + a_4 + ... + a_n = N, a_i>=0 where a_i denotes the number of i's, is the answer.
1 Like