Enumeration found answer but need quick help
- Thread starter mahjk17
- Start date
I don't have an efficient solution in mind, perhaps there is a better one. We have a seven-digit integer abcdegf such that a+b+c+d+e+f+g = 19. The restrictions are: 1<a<=9, and each of b through g may be any of 0 through 9 subject to the constraint.
When a=1, we find b+...+f=18. Count the number of all "valid" unordered 6-partitions of 18 with allowing 0.
In other words we need to find "the number of ways to put 18 objects into 6 labeled boxes, with the restriction that each box contains a maximum of 9 objects". This in of itself looks very messy, and you will have to sum 9 such values.
Let N(n,k) be "the number of ways to distribute n indistinguishable objects among k distinguishable boxes such that each box has at most 9 objects".
Then your solution is \(\displaystyle \sum_{a=1}^9 N(19-a,6)\)
I haven't the slightest idea what a formula for what N(n,k) might look like, hopefully something like that has been covered in you class. However your answer is 111,573, certainly not 18 choose 6.
When a=1, we find b+...+f=18. Count the number of all "valid" unordered 6-partitions of 18 with allowing 0.
In other words we need to find "the number of ways to put 18 objects into 6 labeled boxes, with the restriction that each box contains a maximum of 9 objects". This in of itself looks very messy, and you will have to sum 9 such values.
Let N(n,k) be "the number of ways to distribute n indistinguishable objects among k distinguishable boxes such that each box has at most 9 objects".
Then your solution is \(\displaystyle \sum_{a=1}^9 N(19-a,6)\)
I haven't the slightest idea what a formula for what N(n,k) might look like, hopefully something like that has been covered in you class. However your answer is 111,573, certainly not 18 choose 6.
Last edited:
pka
Elite Member
- Joined
- Jan 29, 2005
- Messages
- 11,989
Here is another way using generating function.
Note that the coefficient of \(\displaystyle x^{19}\) is \(\displaystyle 111573\).
Hello, mahjk17!
I think I understand your reasoning . . .
Place 19 objects in a row, inserting a space between them.
. . \(\displaystyle \circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_ \cdots \,\_\,\circ\,\_\,\circ \)
Select 6 of the spaces and insert "dividers".
So that: .\(\displaystyle \circ\,\circ\,\circ\,|\,\circ\,|\, \circ\, \circ\, \circ\, \circ\, |\,\circ\,|\,\circ\,\circ\,\circ\,\circ\,\circ\,| \,\circ\,\circ\,|\,\circ\,\circ\,\circ\)
. . . . . . . represents: \(\displaystyle 3141523.\)
The number of such numbers is: .\(\displaystyle _{18}C_6 \:=\:18,\!564\)
But none of your numbers include the digit "0" (zero).
I think I understand your reasoning . . .
Place 19 objects in a row, inserting a space between them.
. . \(\displaystyle \circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_ \cdots \,\_\,\circ\,\_\,\circ \)
Select 6 of the spaces and insert "dividers".
So that: .\(\displaystyle \circ\,\circ\,\circ\,|\,\circ\,|\, \circ\, \circ\, \circ\, \circ\, |\,\circ\,|\,\circ\,\circ\,\circ\,\circ\,\circ\,| \,\circ\,\circ\,|\,\circ\,\circ\,\circ\)
. . . . . . . represents: \(\displaystyle 3141523.\)
The number of such numbers is: .\(\displaystyle _{18}C_6 \:=\:18,\!564\)
But none of your numbers include the digit "0" (zero).