Author 
Message 
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)...#(an1
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)^(rm)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

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)...#(an1
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)^(rm)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(r1,m1) in your formula.
 Christopher Heckman 

Back to top 


Google


Back to top 



The time now is Wed Oct 17, 2018 7:05 pm  All times are GMT

