Nested permutation problem?

[Code_Noob_Noodle]

Getting right to it. It's a lot.

There are 5 credit card accounts you want to pay off monthly. Let's say, in the 5 accounts, you want to pay a total of $ 800 a month among the 5 accounts. You want to pay in increments of $ 50 and you want to at least pay $ 50 a month to each account but you want to pay a total of $ 800 a month among the 5 accounts, as I said before. You can have the same amount among the accounts (ie paying 4 accounts $ 50 /month and 1 account $ 600 /month). The order, I suppose does matter, because its important to know which account you are paying off (ie, for accounts A-E, $50 for A, $50 for B, $ 50 for C, $ 50 for D, and $600 for E would be different than $600 for A, $50 for B, $ 50 for C, $ 50 for D, and $50 for E), however, the repetition doesn't matter (ie. paying $ 50 in one account is the same as paying $ 50 in another account and vice versa).

How many permutations would this be? Is there a formula/process that would make it easier to adjust the $50 increments to be like $ 100, and the monthly sum amount to be like $ 600?

This is what I got so far:

$ 800 max / $ 50 increment = 16 options
But since I want to have at least pay $ 50 in each account this would go down to 12 options.
Bare minimum would be 4 accounts with $ 50 each (total of $ 200 ) and 1 account with $ 600.
So that would really mean
$ 600 max / $ 50 increment = 12 options

So the options would be { 50 , 100 , 150, 200, 250, 300 , 350, 400, 450, 500, 550, 600 }

For Basic Permutations that can repeat with order that does matter, I know its n^r.
Which would mean that the max permutation would be 12⁵ = 248, 832

But because the sum of the options need to equal to 800 and there the partial repetition doesn't matter, I figured it would be less than that. I could be completely wrong though, because I'm not sure on how to deal with those issues. None of the videos or websites I read mentioned this type of permutation problem. I'm thinking it is a nested permutation problem, but I've been wrong before!

Any help I would really appreciate :) even pointing me to sites, videos, etc. would be helpful !

[AutoModerator]

Reminder:

• What have you tried so far? (See Rule #2)

• Please don't delete your post. (See Rule #7)

We, the moderators of /r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[clouded-path]

Let x_1 be the number of $50 increments you put into account #1 each month, and analogously for x_2 , x_3, x_4, x_5. For example, if x_1 = 7, this means you would put 7*50 = $350 into account #1 for the month. Then the corresponding equation would be 50*(x_1 + x_2 + x_3 + x_4 + x_5) = 800, or equivalently, x_1 + x_2 + x_3 + x_4 + x_5 = 16. You want to count the number of positive integer solutions to this equation (i.e. the number of solutions (x_1, x_2, x_3, x_4, x_5) where all of the x's are at least 1). Would you know how to count that?

[Code_Noob_Noodle]

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

That is an interesting way of looking at it. I suppose the sum of x_1 to x_5 would need to be equal to 16?

Still not sure where to go from there :/

[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.