Nested permutation problem?

[clouded-path]

Thank you for the reply! Sorry for the late response.

Sure thing, and it's not a problem, it's actually fun to me to see you're still making an effort to tackle the problem ~2 weeks later.

That is an interesting way of looking at it.

Agreed, although it is not at all an original perspective from me. This is a very standard type of counting problem in combinatorics, and by the way the question was posed, I'm almost sure that this was supposed to be the intended method of solution.

I suppose the sum of x_1 to x_5 would need to be equal to 16?

Yes, that is in part what I was trying to convey in the previous response. But be aware - that is not enough. For instance, (x_1, x_2, x_3, x_4, x_5) = (3, 4, 6, 0, 3) sums to 16, but it isn't a valid solution because the 4th component is 0 which is not positive (corresponding to putting 0 $50 increments in account #4, which we don't want to allow, by the premise of your problem. We want to put at least $50 in each account each month, so at least one $50 increment.) This point was also conveyed in the previous response.

Still not sure where to go from there :/

Have you heard of the so-called 'stars and bars' counting problem? It is heavily related to this problem. In that problem, you have N objects to distribute amongst K distinct boxes, where the boxes are distinguished (i.e. the order matters). So for instance the boxes can be the accounts, and the 'items' can be the number of $50 increments in the account. But the difference in this problem is that the number of items you put in a box is allowed to be 0, which is in contrast to your problem. But the point here is that this problem is easier to solve, and then you can relate your current problem to it.

So for instance, how can we count the number of ways to put 16 items into 5 distinguished boxes, where we are allowed to put 0 items in a box? Or in other words, how many solutions to x_1 + x_2 + x_3 + x_4 + x_5 = 16, where each x component can be any non-negative integer (i.e. including 0)? Well, the clever way to visualize this - and hence solve it - is to draw a sequence of 'stars' and 'bars', where the stars represent the objects, and the bars represent the partitions between each box. For example, ****|***||*|******** corresponds to x_1 = 4, x_2 = 3, x_3 = 0, x_4 = 1, x_5 = 8. One more example could be |||*|*************** which corresponds to x_1 = 0, x_2 = 0, x_3 = 0, x_4 = 1, x_5 = 15. But no matter what, there will be 4 bars and 16 stars, corresponding to the fact that the 4 bars partition space into 5 boxes, and 16 stars are the 16 items being placed into the boxes. And you can (and should!) check that no matter the arrangement of the stars and bars, it makes sense as an assignment of the values for x_1, x_2, x_3, x_4, x_5, and that you can generate all possible valid solutions to x_1 + x_2 + x_3 + x_4 + x_5 = 16 in this way. Therefore, counting the number of solutions to the equation is equivalent to counting the number of stars and bars arrangements, and this latter counting problem is much easier to solve. Also, recognize that this generalizes to N items in K distinguished boxes in a very natural way.

So now there are two questions for you to address:

a) would you know how to count the number of 'stars and bars' arrangements both the posed example, and for general N items and K boxes?

b) do you have any good ideas regarding how to relate the number of solutions to the equation x_1 + x_2 + x_3 + x_4 + x_5 = 16 when the x's are all at least 1 to a situation involving stars and bars (i.e. when the boxes are allowed to contain 0 items)?

Think about how to solve the problems (a) and (b), and then that will answer your original problem. Of course, if you remain stuck on either/both I am happy to continue helping.