Author 
Message 
Alexander Blessing science forum beginner
Joined: 05 Feb 2005
Posts: 11

Posted: Sat Jul 15, 2006 3:30 pm Post subject:
More on combinatorics



Suppose you have a set of 10 _distinct_ elements (say, balls for
example). Next, you have a certain number n of boxes (where n is at
least 10). The job is to fill those boxes with the balls. There are two
rules however:
Rule #1: the first box cannot contain ball number 1
Rule #2: at the very end, the boxes must contain _at most_ 9 different
balls.
To make this more clear, let's label the balls with numbers from 0 to
9.
So, if we take n = 11, the following would be valid: 1 2 1 3 4 5 2 3 4
4 2 (there are 4 different balls)
The following combination would not work, however, because there would
be 10 different balls: 1 3 2 4 5 6 7 8 9 0 1
So, how can I generalize: how many possibilities are there to form
combinations which obey to the two rules? 

Back to top 


matt271829news@yahoo.co. science forum Guru
Joined: 11 Sep 2005
Posts: 846

Posted: Sat Jul 15, 2006 10:41 pm Post subject:
Re: More on combinatorics



Whatever5k@web.de wrote:
Quote:  Suppose you have a set of 10 _distinct_ elements (say, balls for
example). Next, you have a certain number n of boxes (where n is at
least 10). The job is to fill those boxes with the balls. There are two
rules however:
Rule #1: the first box cannot contain ball number 1
Rule #2: at the very end, the boxes must contain _at most_ 9 different
balls.
To make this more clear, let's label the balls with numbers from 0 to
9.
So, if we take n = 11, the following would be valid: 1 2 1 3 4 5 2 3 4
4 2 (there are 4 different balls)

Doesn't this violate rule #1? And aren't there 5 different balls here?
Quote:  The following combination would not work, however, because there would
be 10 different balls: 1 3 2 4 5 6 7 8 9 0 1

And anyway, this violates rule #1?
Quote: 
So, how can I generalize: how many possibilities are there to form
combinations which obey to the two rules?

I don't understand your examples, but let's have a go anyway...
Let f(n,b,x) be the number of different sequences of n items, where
each item is chosen from any of b candidates, such that exactly x
different items appear. Then if x <= b and x <= n, I get
f(n,b,x) = C(b,x) * (1)^x * sum{j = 1 to x} (1)^j * C(x,j) * j^n
otherwise f(n,b,x) = 0.
So, momentarily ignoring rule 1, the answer to your question would be
10^n  f(n,10,10). Then by symmetry exactly 1/10 of these will start
with 1, so the final answer should be 9/10*(10^n  f(n,10,10)). 

Back to top 


Alexander Blessing science forum beginner
Joined: 05 Feb 2005
Posts: 11

Posted: Sun Jul 16, 2006 8:26 am Post subject:
Re: More on combinatorics



Hi.
Sorry, my examples are a bit wrong. The first box should not contain
ball #1. Anyway, let's say that the first box musn't contain ball
number #2.
What is C(b,x) in your explanation? 

Back to top 


matt271829news@yahoo.co. science forum Guru
Joined: 11 Sep 2005
Posts: 846

Posted: Sun Jul 16, 2006 10:15 am Post subject:
Re: More on combinatorics



Whatever5k@web.de wrote:
Quote:  Hi.
Sorry, my examples are a bit wrong. The first box should not contain
ball #1. Anyway, let's say that the first box musn't contain ball
number #2.
What is C(b,x) in your explanation?

C(b,x) is a binomial coefficient, defined as
C(b,x) = b!/(x! * (bx)!)
where x! ("x factorial" or "factorial x") is equal to x*(x1)*(x2)*
.... *3*2*1, and similarly for the other factorials in the expression.
It is the number of different ways of choosing x items from a total of
b different items, without regard to the order in which the items are
chosen. 

Back to top 


Google


Back to top 



The time now is Mon Feb 19, 2018 10:05 pm  All times are GMT

