# Find the nth permutation in dictionary order

What would be the most efficient way of solving the following problem? -

A toy set contains blocks showing the numbers from 1 to 9. There are plenty of blocks showing each number and blocks showing the same number are indistinguishable. We want to examine the number of different ways of arranging the blocks in a sequence so that the displayed numbers add up to a fixed sum. For example, suppose the sum is 4. There are 8 different arrangements:

1 1 1 1

1 1 2

1 2 1

1 3

2 1 1

2 2

3 1

4

The rows are arranged in dictionary order (that is, as they would appear if they were listed in dictionary). In each of the cases below, you are given the desired sum S and a number K. You have to write down the Kth line when all arrangements that add up to S are written down as described above. For instance, if S is 4 and K is 5, the answer is 2 1 1. Remember that S may be large, but the numbers on the blocks are only from 1 to 9.

(a) S = 9, K = 156 (b) S = 11, K = 881 (c) S = 14, K = 4583

Thanks!

Source - Zonal Informatics Olympiad 2012 Question Paper

-
What have you tried so far? –  Daryl Oct 29 '12 at 23:15
I've tried to construct the answer to the bigger problem through answers to smaller problems, but that didn't quite work out due to different dictionary arrangements. And brute-force doesn't appear to be a pragmatic approach... –  7Aces Oct 29 '12 at 23:19
Welcome to MSE, by the way. For the best responses, you should include where the question came from, what you have already attempted and what the problem is you are having. Also, if it is homework, you should add the homework tag (people will still help, so don't worry). –  Daryl Oct 29 '12 at 23:29
Thanks for the tip! –  7Aces Oct 29 '12 at 23:38

Hint: the first lines all start with 1. They are 1 followed by all the ways of writing S-1, in dictionary order. Then you get the ones that start with 2, which are 2 followed by writing S-2. If you can figure out how many total lines there are to write $n$, you can figure out the first number and recurse.

-
Thanks! I re-applied my approach "to construct the answer to the bigger problem through answers to smaller problems" with some edits & it yielded the correct answer... Cheers!! –  7Aces Oct 29 '12 at 23:42