FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
More on combinatorics
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Alexander Blessing
science forum beginner


Joined: 05 Feb 2005
Posts: 11

PostPosted: Sat Jul 15, 2006 3:30 pm    Post subject: More on combinatorics Reply with 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)
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
matt271829-news@yahoo.co.
science forum Guru


Joined: 11 Sep 2005
Posts: 846

PostPosted: Sat Jul 15, 2006 10:41 pm    Post subject: Re: More on combinatorics Reply with quote

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

PostPosted: Sun Jul 16, 2006 8:26 am    Post subject: Re: More on combinatorics Reply with 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?
Back to top
matt271829-news@yahoo.co.
science forum Guru


Joined: 11 Sep 2005
Posts: 846

PostPosted: Sun Jul 16, 2006 10:15 am    Post subject: Re: More on combinatorics Reply with quote

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.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Thu Sep 21, 2017 11:14 pm | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Probabilistic Combinatorics Notes Help Sundus Math 0 Fri Jul 21, 2006 11:27 am
No new posts Probabilistic combinatorics help Sundus Math 1 Fri Jul 21, 2006 4:59 am
No new posts A Combinatorics/Graph Theory Question mathlover Undergraduate 1 Wed Jul 19, 2006 11:30 pm
No new posts A Combinatorics/Graph Theory Question mathlover Math 2 Wed Jul 19, 2006 11:02 pm
No new posts 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.0750s ][ Queries: 16 (0.0559s) ][ GZIP on - Debug on ]