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 » Combinatorics
is there a nice proof for one formula?
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
Author Message
butylka@gmail.com
science forum beginner


Joined: 31 Oct 2005
Posts: 5

PostPosted: Mon Oct 31, 2005 6:06 pm    Post subject: is there a nice proof for one formula? Reply with quote

It is well known that if we want to calculate number of objects which
have at least one of n properties than we have to use such formula #(a1
U a2 U ... U an)=#(a1)+...+#(an)-#(a1 U a2)-...-#(an-1
Uan)....+(-1)^(n+1)#(a1 U...Uan)
here U stands for union,
# - number of objects, for example #(a1 U a2)- means the number of
objects which have a1 property and a2 property.
a1,...,an - n properties.
i am interested in similar formula when we want to calculate number of
objects which have strictly k properties.and there exist such formula
similar to written above but there will be also binomial coefficients
C(n,k).
#= summ( r=m to r=n) ( (-1)^(r-m)C(m,r)S(r))
where S(r)=summ ( for all subsets (i1,..ir) of 1,...,n) ( #(a_(i1)
a_(i2) ..a(ir))

My question- is there exist a proof of such formula without appealing
to principe of mathematical induction?
why without induction- it is quite boring to use it always in prooving
such results.I know non induction proof for the first formula and
wonder if there exist such nice combinatoric non math induction proof
for the second one.
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Tue Nov 01, 2005 2:40 am    Post subject: Re: is there a nice proof for one formula? Reply with quote

butylka@gmail.com wrote:
Quote:
It is well known that if we want to calculate number of objects which
have at least one of n properties than we have to use such formula #(a1
U a2 U ... U an)=#(a1)+...+#(an)-#(a1 U a2)-...-#(an-1
Uan)....+(-1)^(n+1)#(a1 U...Uan)
here U stands for union,
# - number of objects, for example #(a1 U a2)- means the number of
objects which have a1 property and a2 property.
a1,...,an - n properties.
i am interested in similar formula when we want to calculate number of
objects which have strictly k properties.and there exist such formula
similar to written above but there will be also binomial coefficients
C(n,k).
#= summ( r=m to r=n) ( (-1)^(r-m)C(m,r)S(r))

I think that should be C(r,m) instead. (C(m,m+1) = 0.)

Quote:
where S(r)=summ ( for all subsets (i1,..ir) of 1,...,n) ( #(a_(i1)
a_(i2) ..a(ir))

My question- is there exist a proof of such formula without appealing
to principe of mathematical induction?

Yes. Verify it for the cases:

(1) S(i) = {x} for exactly 1 value of i, and S(i) empty otherwise;
(2) S(i) = {x} for exactly 2 values of i (and empty otherwise);
....
(n) S(i) = {x} for all n values of i.

Then use linearity.

BTW, there's also a formula for the number of elements in at least m of
the sets; change C(r,m) to C(r-1,m-1) in your formula.

--- Christopher Heckman
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
The time now is Fri Jun 23, 2017 1:43 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts about uni. continuous proof bill1158 Math 1 Tue Jul 18, 2006 10:30 pm
No new posts Stumped with figuring a formula... moriman Recreational 8 Mon Jul 17, 2006 12:21 am
No new posts (humor) Another hand-waving incredibly simple proof of FLT DGoncz@aol.com Math 0 Fri Jul 14, 2006 7:50 pm
No new posts Newton's formula kunzmilan@atlas.cz Math 0 Thu Jul 13, 2006 11:12 am
No new posts Another nice mean value like theorem eugene Math 3 Wed Jul 12, 2006 3:09 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.0189s ][ Queries: 16 (0.0041s) ][ GZIP on - Debug on ]