# Ways of spending money combinatorial problem

Suppose person X has $12$ dollars.In each of the first 5 days he buys one of the following items.

1.Item A for $1 2.Item B for$2

3.Item C for $3. In how many ways can he spend the money during the first five days? This is what I did. Each of the five days he can buy Item A without running out of money. Also each of the five days he can buy Item B without running out of money.Therefore based on these 2 choices he has 2 selections each day.Thus$2^5$selections. Now if he decides to buy item C, If he buys Item C for 1 day then, still all other four days have 2 choices each day.Ways of selecting the day to buy item C=${5 \choose 1}$.And each 4 days having 2 choices make the total number of selections=$2^4*5=80$. If he buys Item C for 2 days then ways of selecting these two days =${5 \choose 1}$.All other three days have 2 choices each day.Total selections in this case=$2^3*10=80$. If he buys Item C for 3 days then ways of selecting these two days =${5 \choose 2}$There are 3 ways of selecting items for the next two days.Thus total number of selections for this case=$3*10=30$Therefore total number of ways of spending 12 dollars is$2^5+80+80+30=222$. Is this correct. • Does order matter? Or does only the final shopping bag matter? – Alexandre Halm Oct 14 '14 at 11:19 • It is correct if order matters. – Coolwater Oct 14 '14 at 11:58 ## 3 Answers So basically if order matters your universe is$\{1,2,3\}^5$(cardinal$3^5=243$). I would simply count how many of these quintuplets$(a_1,...,a_5) \in \{1,2,3\}^5$do not satisfy$a_1+...+a_5 \le 12$by distinguishing how many "$3$" values they have : • 5 times "3" : only one tuple$(3,3,3,3,3)$• 4 times "3" : fives tuples where "1" is the fifth value (from$(1,3,3,3,3)$to$(3,3,3,3,1)$) and five ones where "2" is the last value • 3 times "3" : only those where the two other values are "2", I count$\binom{5}{2}$ways to place the two "2"s Answer :$243 - 1 - 5 - 5 - 10 = 222$. If we understand the probleme as this: What is the number of ways to spend 12 dollars in 5 days if we have to buy only one item a day, which costs 1 or 2 or 3 dollars? It is the number of ways to partition 12 in 5 parts, with each of these 5 parts are 1 or 2 or 3:$1 + 2 + 3 + 3 + 3 =12$all the permutations:$\frac{5!}{3!} =202 + 2 + 2 + 3 + 3 =12$all the permutations:$\frac{5!}{3!2!} =10$So,$20+10 =30$ways Cheers • you don't need to spend the whole 12 dollars in the problem – Alexandre Halm Oct 14 '14 at 12:57 This is trickier, are number of sums to a limited quantity. You can calculate it using a generating function or by hand knowing the limitations. Using a generating function will be the sum of the coefficients from the power 5 to 12 of this polynomial $$f(x)=(x+x^2+x^3)^5=x^{15}+5x^{14}+15x^{13}+30x^{12}+45x^{11}+51x^{10}+45 x^9+30 x^8+15x^7+5 x^6+x^5\\ \to f^*(x)=30x^{12}+45x^{11}+51x^{10}+45 x^9+30 x^8+15x^7+5 x^6+x^5\\ f^*(1)=222$$ Im not consumist so I prefer the version where you can choose DONT buy if you want, in this version the generating function will be $$g(x)=(1+x+x^2+x^3)^5=x^{15}+5 x^{14}+15 x^{13}+35x^{12}+65 x^{11}+101x^{10}+135 x^9+155 x^8+155x^7+135 x^6+101 x^5+65x^4+35 x^3+15 x^2+5 x+1\\ \to g^*(x)=35x^{12}+65 x^{11}+101x^{10}+135 x^9+155 x^8+155x^7+135 x^6+101 x^5+65x^4+35 x^3+15 x^2+5 x+1\\ g^*(1)=1003$$ ;) • Does g represent the ordered selection and f the unordered – clarkson Oct 14 '14 at 12:51 • @clarkson, all are ordered/unordered. Order doesnt matter for this problem.$g(x)$is a version of the original question but considering that you can NOT buy too, i.e., spent 0$ if you want any day. – Masacroso Oct 14 '14 at 12:54
• Everyday during these 5 days he buys something – clarkson Oct 14 '14 at 12:58
• Guy, you read what I write? – Masacroso Oct 14 '14 at 12:58