let Fy be finite-yielding Function; for X being finite set
for n, k being Nat st dom Fy = X & ex x, y being set st
( x <> y & ( for f being Function st f in Choose (X,k,x,y) holds
card (Intersection (Fy,f,x)) = n ) ) holds
Card_Intersection (Fy,k) = n * ((card X) choose k)
let X be finite set ; for n, k being Nat st dom Fy = X & ex x, y being set st
( x <> y & ( for f being Function st f in Choose (X,k,x,y) holds
card (Intersection (Fy,f,x)) = n ) ) holds
Card_Intersection (Fy,k) = n * ((card X) choose k)
let n, k be Nat; ( dom Fy = X & ex x, y being set st
( x <> y & ( for f being Function st f in Choose (X,k,x,y) holds
card (Intersection (Fy,f,x)) = n ) ) implies Card_Intersection (Fy,k) = n * ((card X) choose k) )
assume A1:
X = dom Fy
; ( for x, y being set holds
( not x <> y or ex f being Function st
( f in Choose (X,k,x,y) & not card (Intersection (Fy,f,x)) = n ) ) or Card_Intersection (Fy,k) = n * ((card X) choose k) )
assume
ex x, y being set st
( x <> y & ( for f being Function st f in Choose (X,k,x,y) holds
card (Intersection (Fy,f,x)) = n ) )
; Card_Intersection (Fy,k) = n * ((card X) choose k)
then consider x, y being set such that
A2:
x <> y
and
A3:
for f being Function st f in Choose (X,k,x,y) holds
card (Intersection (Fy,f,x)) = n
;
set Ch = Choose (X,k,x,y);
consider P being Function of (card (Choose (X,k,x,y))),(Choose (X,k,x,y)) such that
A4:
P is one-to-one
by Lm2;
consider XFS being XFinSequence of NAT such that
A5:
dom XFS = dom P
and
A6:
for z being set
for f being Function st z in dom XFS & f = P . z holds
XFS . z = card (Intersection (Fy,f,x))
and
A7:
Card_Intersection (Fy,k) = Sum XFS
by A1, A2, A4, Def3;
for z being object st z in dom XFS holds
XFS . z = n
proof
let z be
object ;
( z in dom XFS implies XFS . z = n )
assume A8:
z in dom XFS
;
XFS . z = n
A9:
P . z in rng P
by A5, A8, FUNCT_1:def 3;
then consider f being
Function of
X,
{x,y} such that A10:
f = P . z
and
card (f " {x}) = k
by Def1;
XFS . z = card (Intersection (Fy,f,x))
by A6, A8, A10;
hence
XFS . z = n
by A3, A9, A10;
verum
end;
then A11:
XFS = (dom XFS) --> n
by FUNCOP_1:11;
then A12:
rng XFS c= {n}
by FUNCOP_1:13;
( Choose (X,k,x,y) = {} implies card (Choose (X,k,x,y)) = {} )
;
then A13:
dom P = card (Choose (X,k,x,y))
by FUNCT_2:def 1;
n in {n}
by TARSKI:def 1;
then
( {n} c= {0,n} & XFS " {n} = dom P )
by A5, A11, FUNCOP_1:14, ZFMISC_1:7;
then
Sum XFS = n * (card (card (Choose (X,k,x,y))))
by A12, A13, AFINSQ_2:68, XBOOLE_1:1;
hence
Card_Intersection (Fy,k) = n * ((card X) choose k)
by A2, A7, Th15; verum