Posts: 55
Threads: 23
Joined: Oct 2007
Sorry for posting a maths question here rather than calculator question. Some day ago someone ask me the following question:
Suppose you enter a sugar shop and there are 10 different types of sugars. You're going to pick out 10 sugars. For each type of sugar you can pick from none to all 10. How many possibilities do you have? Is there a general theorum or equation for such type of question? Also, can such kind of question be programmed? I obtained the answer, and my friend thought I was clever. The thing I didn't tell him is that I obtained the answer by COUNTING!
KC
Posts: 536
Threads: 56
Joined: Jul 2005
Posts: 776
Threads: 25
Joined: Jun 2007
KC,
I think you need to restate your problem. Please confirm if this is the correct statement:
"There are 10 different kinds of sugar. You are going to make 10 individual choices of what kind of sugar to buy. (i.e. you are first going to buy one kind of sugar, choosing from the 10 varieties; after that you are going to buy your second kind of sugar, again choosing from all 10 varieties, and so on, for 10 times) You can buy the same type of sugar as many times as you want (up to 10, of course!). How many different combinations of sugar buys can you make?"
If that is the problem, then the answer is pretty big: 10^10. In other words, at each purchasing decision, you can choose from 10 different products, and you get to choose 10 times.
Another way to look at it: give each sugar type a number value from 0 to 9. Your first overall purchasing decision might be to make 10 purchases of sugar type 0, and you purchase listing would be 0000000000. Then you might say, "hey this is kind of boring, I'd like to try type 1 at least once." Then, if you choose type 1 last, your purchase list would be 0000000001. Since you could choose any type at any point in your sequence, you would ultimately cover all the numbers between 0000000000 and 9999999999.
Posts: 610
Threads: 53
Joined: Aug 2005
I agree with your understanding of the statement, which at first was not clear to me.
But I think we want to go into deeper in the analysis.
As a matter of fact, you can choose out of 10 candies, any one you like, and this 10 times.
So the logical answer would be : 10*10*10...*10 = 10^10.
But this is the amount of possibilities of arranging the candies, whare place of the candies is important. To tka your example of numbers, 8181800081 does count as well as 1118888000, which is, to my understanding, the same possibility.
My understanding of the statement is how many different possibilities do you have to pick out 10 candies out of 10 different boxes. Hence no matter the place.
In this sense, we are facing to a situation where you can choose 10 * (101) * (102) *...* (108) * (109) = 10
! candies = 3,628,800 possibilities on my 41CX !
Posts: 74
Threads: 14
Joined: Jul 2007
Imagine a coffee shop with 10 flavors of coffee; you are to purchase 10 cups of coffee. You can choose 10 cups of the same flavor, one cup of each of the 10 flavors, or a combination of flavors. How many combinations are there.
10 possible choices for each cup
10*10*10*10*10*10*10*10*10*10 = 10^10 = 10,000,000,000
If there is to be no duplicates, that is you can only choose each flavor once, but the order in which the flavors are selected is counted then Pr,n = n!/(nr)! = 10!/(1010)! = 10! = 3,628,800
Posts: 1,193
Threads: 43
Joined: Jul 2005
Some of the answers given before, based on 10^10 are right as far as order is considered important. (i.e.: 12 and 21 are considered different combinations).
The case in which order is disregarded (i.e.: 12 and 21 are deemed the same) is more complex, and my first trials at it were unsuccessful... I am sure there is a better answer, but I have not found it yet...
Posts: 55
Threads: 23
Joined: Oct 2007
First of all thanks for all of your responses. Let me make things simpler and clearer. Suppose the sugar shop has only 3 different types of sugars and I had to pick 3 only. I can list all the possibilites out. Let's label each type of sugar to be 1, 2 and 3 respectively:
111
112
113
122
123
133
222
223
233
333
I have 10 possibilities. Order is not important, so 321 and 213 is the same as 123, and that's why it cannot be 3^3. From the above listing, one can see that the tenth digit can never be larger than the unit digit, and the hundredth digit can never be larger than the tenth digit, and so on. Therefore I think somehow I can programmed that in my HP calculator according to the above rule, but I haven't figure it out.
KC
Posts: 302
Threads: 34
Joined: Aug 2007
Sounds like an nPr nCr (permutations or combinations) depending on whether or not you are paying attention to repeats.
Posts: 1,792
Threads: 62
Joined: Jan 2005
The problem can be approached as a "nested recursive summation" that is not too difficult to program on an RPLbased HP calc (28/48/49 series).
For the 3variable example (let's call it red, green, and blue marbles), the 10 ways to choose three marbles is as follows:
R G B arrangements
3 0 0 1
2 1 0 3
2 0 1 3
1 2 0 3
1 1 1 6
1 0 2 3
0 3 0 1
0 2 1 3
0 1 2 3
0 0 3 1
total: 27
There are (R+G+B)!/(R!G!B!) number of each arrangement
The RPL expression (Sig = Greek letter sigma)
'Sig(R=0,3,Sig(G=0,3R,1))'
can quickly be evaluated as 10.
(NOTE: Knowing the number of red and green marbles, there is only one possible value for the number of blue ones. So, it is not necessary to include it in the summation.)
Neither my 48G nor my 49G could procude the correct answer for the 10variable case, the way I programmed it. THe 48G got stuck in a loop; the 49G seems to have different syntax.
 KS
Posts: 610
Threads: 53
Joined: Aug 2005
Posts: 5
Threads: 0
Joined: Jan 1970
CR(3,3)=C(5,3)=10
CR(m,n)=C(m+n1,n)
Is this ok?
Posts: 74
Threads: 14
Joined: Jul 2007
C(m+n1,n)= C(19,10)= 92,378.
Raul, was there a reference to this, or did you deduce by trial and error.
KC, what was your answer?
Posts: 5
Threads: 0
Joined: Jan 1970
Quote: Raul, was there a reference to this, or did you deduce by trial and error
No: I'm not a genious :( but I know this expresion since I was 14... and I teach it to my students. Combinations with repetition (as explained by KC in his example): we have m diferent elements for doing groups of m elements, don't worry about order (123=321=231=...) and we can repeat elements (111 or 112, etc)
so for the 10 sugar problem: CR(m,n)=C(m+n1,n)=CR(10,10)=C(19,10)=92378
Edited: 14 Oct 2004, 12:30 p.m.
Posts: 55
Threads: 23
Joined: Oct 2007
Excellent Raul! It was such a beautiful and elegant expression! I apologize for my early claim that I was able to count m=10 and n=10 case. It was in fact a case where m=n=7, and I spent 2 hours or so to work out the answer. For the case where m=n=10, I don't think I have the gut to count overnight!
Once again, thanks very much,
KC
Posts: 55
Threads: 23
Joined: Oct 2007
Hi Raul, I'm so impressed you told me you learned this expression at the age of 14. At my age of 14, I learned something like "what's the probability of getting two heads by flipping two coins?" Nevertheless, I love probability very much.
KC
Posts: 5
Threads: 0
Joined: Jan 1970
Perhaps someone could be interested in this "new command":
COMBR
« DUP ROT + 1  SWAP COMB »
But if you are using Erable in a 48GX, you can use this version:
« DUP ROT + 1  SWAP
15 FC?
IF
THEN COMB
ELSE comb
END
»
so, you will obtain exact results (all digits) or approximated results (scientific notation) depending on user flag 15. (This is not necessary with the 49)
Posts: 1,792
Threads: 62
Joined: Jan 2005
Raul provided the following RPL routines:
« DUP ROT + 1  SWAP COMB »
« DUP ROT + 1  SWAP 15 FC? IF THEN COMB ELSE comb END »
The first of which does indeed work on a 48G and 49G, but can't work on a 28C or any 41 (no statistical combination function "COMB").
Here are the RPN versions of the first program:
(others) (HP42)
LBL C LBL "COMBR"
ENTER ENTER
RDN RDN
+ +
1 1
 
RUP RUP
Cy,x COMB
RTN END
No real difference in understandability, but that second RPL routine sure looks like jibberish to me.
The first routine is quickest and easiest to program and invoke on any nonalphanumeric RPN programmable.
Fie upon RPL! :^)
 KS
Posts: 2
Threads: 0
Joined: Jan 1970
Karl, Instead of your "ENTER RDN + 1  RUP" I did "X<>Y 1  X<>Y + LASTX" here. Any reason to prefer one over the other?
If COMB is replaced by PERM (or equivalents) in these routines then we have Pochhammer's Symbol, the rising factorial. Now this sounds like something to hit RPL with<G>
Posts: 57
Threads: 5
Joined: Jan 1970
This is COMB for the 41. I wrote it the last summer, adapting this program from the MoHPC's Library,
(Caution with RND and RDN)
LBL COMB (uses R00 and R01)

LAST X
X<Y?
X<>Y
STO 00
1
STO 01
+
STO 02
RDN
X=0?
GTO 00
LBL 02
1
RCL 01
+
STO 01
X<=Y?
GTO 01
RCL 02
FIX 0
RND
FIX 4
GTO 04
LBL 01
RCL 00
+
RCL 01
/
STO*02
RDN
GTO 02
LBL 00
1
LBL 04
END
And this is the COMBR I use in my 41:
LBL COMBR
1
ST  Z
RDN
+
LAST X
XEQ COMB
END
Edited: 20 Oct 2004, 3:55 p.m.
Posts: 1,792
Threads: 62
Joined: Jan 2005
Tony posted,
Quote:
Instead of your "ENTER RDN + 1  RUP" I did "X<>Y 1  X<>Y + LASTX" here. Any reason to prefer one over the other?
No preference; you program is just as good as mine  six steps to set up the inputs to the C(y,x), using one extra stack level.
Now, here's a better RPN program for the 42S, using only three steps and no extra stack levels to set up the argument,. It should also work in conjunction with Raul's "COMB" program on the 41's.
LBL "COMBR"
+
LAST x
DSE ST Y
COMB
END
