# Combinatorics: how many ways are there to form 100 with 1, 2 and 5 [duplicate]

Possible Duplicate:
Making Change for a Dollar (and other number partitioning problems)

dollar notes in denominations of 1, 2 and 5. How many ways are there to form exactly $100 using just multiples of these notes? - ## marked as duplicate by Marc van Leeuwen, draks ..., Micah, rschwieb, froggieNov 27 '12 at 14:43 This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question. ## 1 Answer$x+2y+5z=1000\le x\le100\implies 0\le 100-2y-5z\le100\implies 0\le 2y+5z\le 100\implies 0\le y\le \lfloor \frac{100-5z}2\rfloor$As$0\le 5z\le 100, 0\le z\le 20 $If$z$is odd$=2a+1, 0\le y\le \lfloor \frac{100-5(2a+1)}2\rfloor=47-5a, 47-5a+1=48-5a$values of$z$So,$0\le 2a+1\le 20\implies 0\le a\le9 $If$z$is even,$=2b, 0\le y\le \lfloor \frac{100-5(2b)}2\rfloor=50-5b, 50-5b+1=51-5b$values of$z$So,$0\le 2b\le 20\implies 0\le b\le10 $So, the number of combinations =$\sum_{ 0\le a\le9}(48-5a)+\sum_{0\le b\le10}(51-5b)=48\cdot10+51\cdot 11-5\sum_{ 0\le a\le9}a-5\sum_{0\le b\le10}b=541\$

-
THANKYOU for your help –  chndn Nov 27 '12 at 11:39