Search   Memberlist   Usergroups
 Page 1 of 1 [2 Posts]
Author Message
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

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

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
butylka@gmail.com
science forum beginner

Joined: 31 Oct 2005
Posts: 5

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

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.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [2 Posts]
 The time now is Wed Dec 12, 2018 3:15 pm | 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 about uni. continuous proof bill1158 Math 1 Tue Jul 18, 2006 10:30 pm Stumped with figuring a formula... moriman Recreational 8 Mon Jul 17, 2006 12:21 am (humor) Another hand-waving incredibly simple proof of FLT DGoncz@aol.com Math 0 Fri Jul 14, 2006 7:50 pm Newton's formula kunzmilan@atlas.cz Math 0 Thu Jul 13, 2006 11:12 am Another nice mean value like theorem eugene Math 3 Wed Jul 12, 2006 3:09 pm