Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
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?
matt271829-news@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)).
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?
matt271829-news@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! * (b-x)!)

where x! ("x factorial" or "factorial x") is equal to x*(x-1)*(x-2)*
.... *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.
Google

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Sat Jun 23, 2018 4:14 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Probabilistic Combinatorics Notes Help Sundus Math 0 Fri Jul 21, 2006 11:27 am Probabilistic combinatorics help Sundus Math 1 Fri Jul 21, 2006 4:59 am A Combinatorics/Graph Theory Question mathlover Undergraduate 1 Wed Jul 19, 2006 11:30 pm A Combinatorics/Graph Theory Question mathlover Math 2 Wed Jul 19, 2006 11:02 pm A Combinatorics/Graph Theory Question mathlover Combinatorics 0 Wed Jul 19, 2006 10:58 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters

Powered by phpBB © 2001, 2005 phpBB Group
 [ Time: 0.0132s ][ Queries: 16 (0.0020s) ][ GZIP on - Debug on ]