MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  birthdaylem2 Structured version   Unicode version

Theorem birthdaylem2 23422
Description: For general  N and  K, count the fraction of injective functions from  1 ... K to  1 ... N. (Contributed by Mario Carneiro, 7-May-2015.)
Hypotheses
Ref Expression
birthday.s  |-  S  =  { f  |  f : ( 1 ... K ) --> ( 1 ... N ) }
birthday.t  |-  T  =  { f  |  f : ( 1 ... K ) -1-1-> ( 1 ... N ) }
Assertion
Ref Expression
birthdaylem2  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( # `  T )  /  ( # `
 S ) )  =  ( exp `  sum_ k  e.  ( 0 ... ( K  - 
1 ) ) ( log `  ( 1  -  ( k  /  N ) ) ) ) )
Distinct variable groups:    f, k, K    f, N, k
Allowed substitution hints:    S( f, k)    T( f, k)

Proof of Theorem birthdaylem2
Dummy variable  n is distinct from all other variables.
StepHypRef Expression
1 birthday.t . . . . . . 7  |-  T  =  { f  |  f : ( 1 ... K ) -1-1-> ( 1 ... N ) }
21fveq2i 5794 . . . . . 6  |-  ( # `  T )  =  (
# `  { f  |  f : ( 1 ... K )
-1-1-> ( 1 ... N
) } )
3 fzfi 12008 . . . . . . 7  |-  ( 1 ... K )  e. 
Fin
4 fzfi 12008 . . . . . . 7  |-  ( 1 ... N )  e. 
Fin
5 hashf1 12433 . . . . . . 7  |-  ( ( ( 1 ... K
)  e.  Fin  /\  ( 1 ... N
)  e.  Fin )  ->  ( # `  {
f  |  f : ( 1 ... K
) -1-1-> ( 1 ... N ) } )  =  ( ( ! `
 ( # `  (
1 ... K ) ) )  x.  ( (
# `  ( 1 ... N ) )  _C  ( # `  (
1 ... K ) ) ) ) )
63, 4, 5mp2an 670 . . . . . 6  |-  ( # `  { f  |  f : ( 1 ... K ) -1-1-> ( 1 ... N ) } )  =  ( ( ! `  ( # `  ( 1 ... K
) ) )  x.  ( ( # `  (
1 ... N ) )  _C  ( # `  (
1 ... K ) ) ) )
72, 6eqtri 2425 . . . . 5  |-  ( # `  T )  =  ( ( ! `  ( # `
 ( 1 ... K ) ) )  x.  ( ( # `  ( 1 ... N
) )  _C  ( # `
 ( 1 ... K ) ) ) )
8 elfznn0 11715 . . . . . . . . 9  |-  ( K  e.  ( 0 ... N )  ->  K  e.  NN0 )
98adantl 464 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  K  e.  NN0 )
10 hashfz1 12344 . . . . . . . 8  |-  ( K  e.  NN0  ->  ( # `  ( 1 ... K
) )  =  K )
119, 10syl 16 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  (
1 ... K ) )  =  K )
1211fveq2d 5795 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  ( # `  ( 1 ... K ) ) )  =  ( ! `
 K ) )
13 nnnn0 10741 . . . . . . . . 9  |-  ( N  e.  NN  ->  N  e.  NN0 )
14 hashfz1 12344 . . . . . . . . 9  |-  ( N  e.  NN0  ->  ( # `  ( 1 ... N
) )  =  N )
1513, 14syl 16 . . . . . . . 8  |-  ( N  e.  NN  ->  ( # `
 ( 1 ... N ) )  =  N )
1615adantr 463 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  (
1 ... N ) )  =  N )
1716, 11oveq12d 6236 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( # `  ( 1 ... N
) )  _C  ( # `
 ( 1 ... K ) ) )  =  ( N  _C  K ) )
1812, 17oveq12d 6236 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ! `
 ( # `  (
1 ... K ) ) )  x.  ( (
# `  ( 1 ... N ) )  _C  ( # `  (
1 ... K ) ) ) )  =  ( ( ! `  K
)  x.  ( N  _C  K ) ) )
197, 18syl5eq 2449 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  T
)  =  ( ( ! `  K )  x.  ( N  _C  K ) ) )
2013adantr 463 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  N  e.  NN0 )
21 faccl 12288 . . . . . . . . 9  |-  ( N  e.  NN0  ->  ( ! `
 N )  e.  NN )
2220, 21syl 16 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  N )  e.  NN )
2322nncnd 10490 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  N )  e.  CC )
24 fznn0sub 11660 . . . . . . . . . 10  |-  ( K  e.  ( 0 ... N )  ->  ( N  -  K )  e.  NN0 )
2524adantl 464 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  K )  e.  NN0 )
26 faccl 12288 . . . . . . . . 9  |-  ( ( N  -  K )  e.  NN0  ->  ( ! `
 ( N  -  K ) )  e.  NN )
2725, 26syl 16 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  ( N  -  K
) )  e.  NN )
2827nncnd 10490 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  ( N  -  K
) )  e.  CC )
2927nnne0d 10519 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  ( N  -  K
) )  =/=  0
)
3023, 28, 29divcld 10259 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ! `
 N )  / 
( ! `  ( N  -  K )
) )  e.  CC )
31 faccl 12288 . . . . . . . 8  |-  ( K  e.  NN0  ->  ( ! `
 K )  e.  NN )
329, 31syl 16 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  K )  e.  NN )
3332nncnd 10490 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  K )  e.  CC )
3432nnne0d 10519 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  K )  =/=  0
)
3530, 33, 34divcan2d 10261 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ! `
 K )  x.  ( ( ( ! `
 N )  / 
( ! `  ( N  -  K )
) )  /  ( ! `  K )
) )  =  ( ( ! `  N
)  /  ( ! `
 ( N  -  K ) ) ) )
36 bcval2 12308 . . . . . . . 8  |-  ( K  e.  ( 0 ... N )  ->  ( N  _C  K )  =  ( ( ! `  N )  /  (
( ! `  ( N  -  K )
)  x.  ( ! `
 K ) ) ) )
3736adantl 464 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  _C  K )  =  ( ( ! `  N
)  /  ( ( ! `  ( N  -  K ) )  x.  ( ! `  K ) ) ) )
3823, 28, 33, 29, 34divdiv1d 10290 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ( ! `  N )  /  ( ! `  ( N  -  K
) ) )  / 
( ! `  K
) )  =  ( ( ! `  N
)  /  ( ( ! `  ( N  -  K ) )  x.  ( ! `  K ) ) ) )
3937, 38eqtr4d 2440 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  _C  K )  =  ( ( ( ! `  N )  /  ( ! `  ( N  -  K ) ) )  /  ( ! `  K ) ) )
4039oveq2d 6234 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ! `
 K )  x.  ( N  _C  K
) )  =  ( ( ! `  K
)  x.  ( ( ( ! `  N
)  /  ( ! `
 ( N  -  K ) ) )  /  ( ! `  K ) ) ) )
41 fzfid 12009 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( 1 ... N )  e.  Fin )
42 elfznn 11657 . . . . . . . . . 10  |-  ( n  e.  ( 1 ... N )  ->  n  e.  NN )
4342adantl 464 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( 1 ... N ) )  ->  n  e.  NN )
44 nnrp 11170 . . . . . . . . . . 11  |-  ( n  e.  NN  ->  n  e.  RR+ )
4544relogcld 23118 . . . . . . . . . 10  |-  ( n  e.  NN  ->  ( log `  n )  e.  RR )
4645recnd 9555 . . . . . . . . 9  |-  ( n  e.  NN  ->  ( log `  n )  e.  CC )
4743, 46syl 16 . . . . . . . 8  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( 1 ... N ) )  ->  ( log `  n )  e.  CC )
4841, 47fsumcl 13580 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( 1 ... N ) ( log `  n
)  e.  CC )
49 fzfid 12009 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( 1 ... ( N  -  K
) )  e.  Fin )
50 elfznn 11657 . . . . . . . . . 10  |-  ( n  e.  ( 1 ... ( N  -  K
) )  ->  n  e.  NN )
5150adantl 464 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( 1 ... ( N  -  K ) ) )  ->  n  e.  NN )
5251, 46syl 16 . . . . . . . 8  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( 1 ... ( N  -  K ) ) )  ->  ( log `  n )  e.  CC )
5349, 52fsumcl 13580 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( 1 ... ( N  -  K ) ) ( log `  n
)  e.  CC )
54 efsub 13860 . . . . . . 7  |-  ( (
sum_ n  e.  (
1 ... N ) ( log `  n )  e.  CC  /\  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n )  e.  CC )  ->  ( exp `  ( sum_ n  e.  ( 1 ... N ) ( log `  n )  -  sum_ n  e.  ( 1 ... ( N  -  K ) ) ( log `  n
) ) )  =  ( ( exp `  sum_ n  e.  ( 1 ... N ) ( log `  n ) )  / 
( exp `  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n ) ) ) )
5548, 53, 54syl2anc 659 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  ( sum_ n  e.  ( 1 ... N ) ( log `  n )  -  sum_ n  e.  ( 1 ... ( N  -  K ) ) ( log `  n
) ) )  =  ( ( exp `  sum_ n  e.  ( 1 ... N ) ( log `  n ) )  / 
( exp `  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n ) ) ) )
5625nn0red 10792 . . . . . . . . . . . 12  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  K )  e.  RR )
5756ltp1d 10414 . . . . . . . . . . 11  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  K )  <  (
( N  -  K
)  +  1 ) )
58 fzdisj 11655 . . . . . . . . . . 11  |-  ( ( N  -  K )  <  ( ( N  -  K )  +  1 )  ->  (
( 1 ... ( N  -  K )
)  i^i  ( (
( N  -  K
)  +  1 ) ... N ) )  =  (/) )
5957, 58syl 16 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( 1 ... ( N  -  K ) )  i^i  ( ( ( N  -  K )  +  1 ) ... N
) )  =  (/) )
60 fznn0sub2 11725 . . . . . . . . . . . . . . . 16  |-  ( K  e.  ( 0 ... N )  ->  ( N  -  K )  e.  ( 0 ... N
) )
6160adantl 464 . . . . . . . . . . . . . . 15  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  K )  e.  ( 0 ... N ) )
62 elfzle2 11633 . . . . . . . . . . . . . . 15  |-  ( ( N  -  K )  e.  ( 0 ... N )  ->  ( N  -  K )  <_  N )
6361, 62syl 16 . . . . . . . . . . . . . 14  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  K )  <_  N
)
6463adantr 463 . . . . . . . . . . . . 13  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  e.  NN )  ->  ( N  -  K )  <_  N
)
65 simpr 459 . . . . . . . . . . . . . . 15  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  e.  NN )  ->  ( N  -  K )  e.  NN )
66 nnuz 11058 . . . . . . . . . . . . . . 15  |-  NN  =  ( ZZ>= `  1 )
6765, 66syl6eleq 2494 . . . . . . . . . . . . . 14  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  e.  NN )  ->  ( N  -  K )  e.  (
ZZ>= `  1 ) )
68 nnz 10825 . . . . . . . . . . . . . . 15  |-  ( N  e.  NN  ->  N  e.  ZZ )
6968ad2antrr 723 . . . . . . . . . . . . . 14  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  e.  NN )  ->  N  e.  ZZ )
70 elfz5 11623 . . . . . . . . . . . . . 14  |-  ( ( ( N  -  K
)  e.  ( ZZ>= ` 
1 )  /\  N  e.  ZZ )  ->  (
( N  -  K
)  e.  ( 1 ... N )  <->  ( N  -  K )  <_  N
) )
7167, 69, 70syl2anc 659 . . . . . . . . . . . . 13  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  e.  NN )  ->  ( ( N  -  K )  e.  ( 1 ... N
)  <->  ( N  -  K )  <_  N
) )
7264, 71mpbird 232 . . . . . . . . . . . 12  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  e.  NN )  ->  ( N  -  K )  e.  ( 1 ... N ) )
73 fzsplit 11654 . . . . . . . . . . . 12  |-  ( ( N  -  K )  e.  ( 1 ... N )  ->  (
1 ... N )  =  ( ( 1 ... ( N  -  K
) )  u.  (
( ( N  -  K )  +  1 ) ... N ) ) )
7472, 73syl 16 . . . . . . . . . . 11  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  e.  NN )  ->  ( 1 ... N )  =  ( ( 1 ... ( N  -  K )
)  u.  ( ( ( N  -  K
)  +  1 ) ... N ) ) )
75 simpr 459 . . . . . . . . . . . . . . 15  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( N  -  K )  =  0 )
7675oveq2d 6234 . . . . . . . . . . . . . 14  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( 1 ... ( N  -  K ) )  =  ( 1 ... 0
) )
77 fz10 11649 . . . . . . . . . . . . . 14  |-  ( 1 ... 0 )  =  (/)
7876, 77syl6eq 2453 . . . . . . . . . . . . 13  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( 1 ... ( N  -  K ) )  =  (/) )
7978uneq1d 3588 . . . . . . . . . . . 12  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( (
1 ... ( N  -  K ) )  u.  ( ( ( N  -  K )  +  1 ) ... N
) )  =  (
(/)  u.  ( (
( N  -  K
)  +  1 ) ... N ) ) )
80 uncom 3579 . . . . . . . . . . . . . 14  |-  ( (/)  u.  ( ( ( N  -  K )  +  1 ) ... N
) )  =  ( ( ( ( N  -  K )  +  1 ) ... N
)  u.  (/) )
81 un0 3754 . . . . . . . . . . . . . 14  |-  ( ( ( ( N  -  K )  +  1 ) ... N )  u.  (/) )  =  ( ( ( N  -  K )  +  1 ) ... N )
8280, 81eqtri 2425 . . . . . . . . . . . . 13  |-  ( (/)  u.  ( ( ( N  -  K )  +  1 ) ... N
) )  =  ( ( ( N  -  K )  +  1 ) ... N )
8375oveq1d 6233 . . . . . . . . . . . . . . 15  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( ( N  -  K )  +  1 )  =  ( 0  +  1 ) )
84 1e0p1 10945 . . . . . . . . . . . . . . 15  |-  1  =  ( 0  +  1 )
8583, 84syl6eqr 2455 . . . . . . . . . . . . . 14  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( ( N  -  K )  +  1 )  =  1 )
8685oveq1d 6233 . . . . . . . . . . . . 13  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( (
( N  -  K
)  +  1 ) ... N )  =  ( 1 ... N
) )
8782, 86syl5eq 2449 . . . . . . . . . . . 12  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( (/)  u.  (
( ( N  -  K )  +  1 ) ... N ) )  =  ( 1 ... N ) )
8879, 87eqtr2d 2438 . . . . . . . . . . 11  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  ( N  -  K )  =  0 )  ->  ( 1 ... N )  =  ( ( 1 ... ( N  -  K
) )  u.  (
( ( N  -  K )  +  1 ) ... N ) ) )
89 elnn0 10736 . . . . . . . . . . . 12  |-  ( ( N  -  K )  e.  NN0  <->  ( ( N  -  K )  e.  NN  \/  ( N  -  K )  =  0 ) )
9025, 89sylib 196 . . . . . . . . . . 11  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( N  -  K )  e.  NN  \/  ( N  -  K )  =  0 ) )
9174, 88, 90mpjaodan 784 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( 1 ... N )  =  ( ( 1 ... ( N  -  K )
)  u.  ( ( ( N  -  K
)  +  1 ) ... N ) ) )
9259, 91, 41, 47fsumsplit 13587 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( 1 ... N ) ( log `  n
)  =  ( sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n )  +  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n ) ) )
9392oveq1d 6233 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( sum_ n  e.  ( 1 ... N
) ( log `  n
)  -  sum_ n  e.  ( 1 ... ( N  -  K )
) ( log `  n
) )  =  ( ( sum_ n  e.  ( 1 ... ( N  -  K ) ) ( log `  n
)  +  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( log `  n
) )  -  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n ) ) )
94 fzfid 12009 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ( N  -  K )  +  1 ) ... N )  e.  Fin )
95 nn0p1nn 10774 . . . . . . . . . . . . 13  |-  ( ( N  -  K )  e.  NN0  ->  ( ( N  -  K )  +  1 )  e.  NN )
9625, 95syl 16 . . . . . . . . . . . 12  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( N  -  K )  +  1 )  e.  NN )
97 elfzuz 11627 . . . . . . . . . . . 12  |-  ( n  e.  ( ( ( N  -  K )  +  1 ) ... N )  ->  n  e.  ( ZZ>= `  ( ( N  -  K )  +  1 ) ) )
98 eluznn 11093 . . . . . . . . . . . 12  |-  ( ( ( ( N  -  K )  +  1 )  e.  NN  /\  n  e.  ( ZZ>= `  ( ( N  -  K )  +  1 ) ) )  ->  n  e.  NN )
9996, 97, 98syl2an 475 . . . . . . . . . . 11  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  n  e.  NN )
10099, 46syl 16 . . . . . . . . . 10  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  ( log `  n )  e.  CC )
10194, 100fsumcl 13580 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n
)  e.  CC )
10253, 101pncan2d 9868 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n )  +  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n ) )  -  sum_ n  e.  ( 1 ... ( N  -  K ) ) ( log `  n ) )  =  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( log `  n
) )
10393, 102eqtr2d 2438 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n
)  =  ( sum_ n  e.  ( 1 ... N ) ( log `  n )  -  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n ) ) )
104103fveq2d 5795 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n ) )  =  ( exp `  ( sum_ n  e.  ( 1 ... N ) ( log `  n )  -  sum_ n  e.  ( 1 ... ( N  -  K ) ) ( log `  n
) ) ) )
10522nnne0d 10519 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  N )  =/=  0
)
106 eflog 23072 . . . . . . . . 9  |-  ( ( ( ! `  N
)  e.  CC  /\  ( ! `  N )  =/=  0 )  -> 
( exp `  ( log `  ( ! `  N ) ) )  =  ( ! `  N ) )
10723, 105, 106syl2anc 659 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  ( log `  ( ! `  N ) ) )  =  ( ! `  N ) )
108 logfac 23096 . . . . . . . . . 10  |-  ( N  e.  NN0  ->  ( log `  ( ! `  N
) )  =  sum_ n  e.  ( 1 ... N ) ( log `  n ) )
10920, 108syl 16 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( log `  ( ! `  N )
)  =  sum_ n  e.  ( 1 ... N
) ( log `  n
) )
110109fveq2d 5795 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  ( log `  ( ! `  N ) ) )  =  ( exp `  sum_ n  e.  ( 1 ... N ) ( log `  n ) ) )
111107, 110eqtr3d 2439 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  N )  =  ( exp `  sum_ n  e.  ( 1 ... N
) ( log `  n
) ) )
112 eflog 23072 . . . . . . . . 9  |-  ( ( ( ! `  ( N  -  K )
)  e.  CC  /\  ( ! `  ( N  -  K ) )  =/=  0 )  -> 
( exp `  ( log `  ( ! `  ( N  -  K
) ) ) )  =  ( ! `  ( N  -  K
) ) )
11328, 29, 112syl2anc 659 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  ( log `  ( ! `  ( N  -  K
) ) ) )  =  ( ! `  ( N  -  K
) ) )
114 logfac 23096 . . . . . . . . . 10  |-  ( ( N  -  K )  e.  NN0  ->  ( log `  ( ! `  ( N  -  K )
) )  =  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n ) )
11525, 114syl 16 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( log `  ( ! `  ( N  -  K ) ) )  =  sum_ n  e.  ( 1 ... ( N  -  K ) ) ( log `  n
) )
116115fveq2d 5795 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  ( log `  ( ! `  ( N  -  K
) ) ) )  =  ( exp `  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n ) ) )
117113, 116eqtr3d 2439 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ! `  ( N  -  K
) )  =  ( exp `  sum_ n  e.  ( 1 ... ( N  -  K )
) ( log `  n
) ) )
118111, 117oveq12d 6236 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ! `
 N )  / 
( ! `  ( N  -  K )
) )  =  ( ( exp `  sum_ n  e.  ( 1 ... N ) ( log `  n ) )  / 
( exp `  sum_ n  e.  ( 1 ... ( N  -  K
) ) ( log `  n ) ) ) )
11955, 104, 1183eqtr4d 2447 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n ) )  =  ( ( ! `  N )  /  ( ! `  ( N  -  K ) ) ) )
12035, 40, 1193eqtr4d 2447 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( ! `
 K )  x.  ( N  _C  K
) )  =  ( exp `  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( log `  n
) ) )
12119, 120eqtrd 2437 . . 3  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  T
)  =  ( exp `  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n
) ) )
122 birthday.s . . . . . . . 8  |-  S  =  { f  |  f : ( 1 ... K ) --> ( 1 ... N ) }
123 mapvalg 7370 . . . . . . . . 9  |-  ( ( ( 1 ... N
)  e.  Fin  /\  ( 1 ... K
)  e.  Fin )  ->  ( ( 1 ... N )  ^m  (
1 ... K ) )  =  { f  |  f : ( 1 ... K ) --> ( 1 ... N ) } )
1244, 3, 123mp2an 670 . . . . . . . 8  |-  ( ( 1 ... N )  ^m  ( 1 ... K ) )  =  { f  |  f : ( 1 ... K ) --> ( 1 ... N ) }
125122, 124eqtr4i 2428 . . . . . . 7  |-  S  =  ( ( 1 ... N )  ^m  (
1 ... K ) )
126125fveq2i 5794 . . . . . 6  |-  ( # `  S )  =  (
# `  ( (
1 ... N )  ^m  ( 1 ... K
) ) )
127 hashmap 12420 . . . . . . 7  |-  ( ( ( 1 ... N
)  e.  Fin  /\  ( 1 ... K
)  e.  Fin )  ->  ( # `  (
( 1 ... N
)  ^m  ( 1 ... K ) ) )  =  ( (
# `  ( 1 ... N ) ) ^
( # `  ( 1 ... K ) ) ) )
1284, 3, 127mp2an 670 . . . . . 6  |-  ( # `  ( ( 1 ... N )  ^m  (
1 ... K ) ) )  =  ( (
# `  ( 1 ... N ) ) ^
( # `  ( 1 ... K ) ) )
129126, 128eqtri 2425 . . . . 5  |-  ( # `  S )  =  ( ( # `  (
1 ... N ) ) ^ ( # `  (
1 ... K ) ) )
13016, 11oveq12d 6236 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( # `  ( 1 ... N
) ) ^ ( # `
 ( 1 ... K ) ) )  =  ( N ^ K ) )
131129, 130syl5eq 2449 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  S
)  =  ( N ^ K ) )
132 nncn 10482 . . . . . 6  |-  ( N  e.  NN  ->  N  e.  CC )
133132adantr 463 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  N  e.  CC )
134 nnne0 10507 . . . . . 6  |-  ( N  e.  NN  ->  N  =/=  0 )
135134adantr 463 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  N  =/=  0
)
136 elfzelz 11631 . . . . . 6  |-  ( K  e.  ( 0 ... N )  ->  K  e.  ZZ )
137136adantl 464 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  K  e.  ZZ )
138 explog 23089 . . . . 5  |-  ( ( N  e.  CC  /\  N  =/=  0  /\  K  e.  ZZ )  ->  ( N ^ K )  =  ( exp `  ( K  x.  ( log `  N ) ) ) )
139133, 135, 137, 138syl3anc 1226 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N ^ K )  =  ( exp `  ( K  x.  ( log `  N
) ) ) )
140131, 139eqtrd 2437 . . 3  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  S
)  =  ( exp `  ( K  x.  ( log `  N ) ) ) )
141121, 140oveq12d 6236 . 2  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( # `  T )  /  ( # `
 S ) )  =  ( ( exp `  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n
) )  /  ( exp `  ( K  x.  ( log `  N ) ) ) ) )
1429nn0cnd 10793 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  K  e.  CC )
143 nnrp 11170 . . . . . . 7  |-  ( N  e.  NN  ->  N  e.  RR+ )
144143adantr 463 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  N  e.  RR+ )
145144relogcld 23118 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( log `  N
)  e.  RR )
146145recnd 9555 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( log `  N
)  e.  CC )
147142, 146mulcld 9549 . . 3  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( K  x.  ( log `  N ) )  e.  CC )
148 efsub 13860 . . 3  |-  ( (
sum_ n  e.  (
( ( N  -  K )  +  1 ) ... N ) ( log `  n
)  e.  CC  /\  ( K  x.  ( log `  N ) )  e.  CC )  -> 
( exp `  ( sum_ n  e.  ( ( ( N  -  K
)  +  1 ) ... N ) ( log `  n )  -  ( K  x.  ( log `  N ) ) ) )  =  ( ( exp `  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n ) )  / 
( exp `  ( K  x.  ( log `  N ) ) ) ) )
149101, 147, 148syl2anc 659 . 2  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  ( sum_ n  e.  ( ( ( N  -  K
)  +  1 ) ... N ) ( log `  n )  -  ( K  x.  ( log `  N ) ) ) )  =  ( ( exp `  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n ) )  / 
( exp `  ( K  x.  ( log `  N ) ) ) ) )
150 relogdiv 23088 . . . . . . 7  |-  ( ( n  e.  RR+  /\  N  e.  RR+ )  ->  ( log `  ( n  /  N ) )  =  ( ( log `  n
)  -  ( log `  N ) ) )
15144, 144, 150syl2anr 476 . . . . . 6  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  NN )  ->  ( log `  (
n  /  N ) )  =  ( ( log `  n )  -  ( log `  N
) ) )
15299, 151syldan 468 . . . . 5  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  ( log `  ( n  /  N
) )  =  ( ( log `  n
)  -  ( log `  N ) ) )
153152sumeq2dv 13550 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  (
n  /  N ) )  =  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( ( log `  n )  -  ( log `  N ) ) )
15468adantr 463 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  N  e.  ZZ )
15525nn0zd 10904 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  K )  e.  ZZ )
156155peano2zd 10909 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( N  -  K )  +  1 )  e.  ZZ )
15799, 44syl 16 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  n  e.  RR+ )
158144adantr 463 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  N  e.  RR+ )
159157, 158rpdivcld 11216 . . . . . . . 8  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  ( n  /  N )  e.  RR+ )
160159relogcld 23118 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  ( log `  ( n  /  N
) )  e.  RR )
161160recnd 9555 . . . . . 6  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  ( log `  ( n  /  N
) )  e.  CC )
162 oveq1 6225 . . . . . . 7  |-  ( n  =  ( N  -  k )  ->  (
n  /  N )  =  ( ( N  -  k )  /  N ) )
163162fveq2d 5795 . . . . . 6  |-  ( n  =  ( N  -  k )  ->  ( log `  ( n  /  N ) )  =  ( log `  (
( N  -  k
)  /  N ) ) )
164154, 156, 154, 161, 163fsumrev 13619 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  (
n  /  N ) )  =  sum_ k  e.  ( ( N  -  N ) ... ( N  -  ( ( N  -  K )  +  1 ) ) ) ( log `  (
( N  -  k
)  /  N ) ) )
165133subidd 9854 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  N )  =  0 )
166 1cnd 9545 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  1  e.  CC )
167133, 142, 166subsubd 9894 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  ( K  -  1
) )  =  ( ( N  -  K
)  +  1 ) )
168167oveq2d 6234 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  ( N  -  ( K  -  1 ) ) )  =  ( N  -  ( ( N  -  K )  +  1 ) ) )
169 ax-1cn 9483 . . . . . . . . . 10  |-  1  e.  CC
170 subcl 9754 . . . . . . . . . 10  |-  ( ( K  e.  CC  /\  1  e.  CC )  ->  ( K  -  1 )  e.  CC )
171142, 169, 170sylancl 660 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( K  - 
1 )  e.  CC )
172133, 171nncand 9871 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  ( N  -  ( K  -  1 ) ) )  =  ( K  -  1 ) )
173168, 172eqtr3d 2439 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  ( ( N  -  K )  +  1 ) )  =  ( K  -  1 ) )
174165, 173oveq12d 6236 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( N  -  N ) ... ( N  -  (
( N  -  K
)  +  1 ) ) )  =  ( 0 ... ( K  -  1 ) ) )
175133adantr 463 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  N  e.  CC )
176 elfznn0 11715 . . . . . . . . . . 11  |-  ( k  e.  ( 0 ... ( K  -  1 ) )  ->  k  e.  NN0 )
177176adantl 464 . . . . . . . . . 10  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  e.  NN0 )
178177nn0cnd 10793 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  e.  CC )
179135adantr 463 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  N  =/=  0 )
180175, 178, 175, 179divsubdird 10298 . . . . . . . 8  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( ( N  -  k )  /  N )  =  ( ( N  /  N
)  -  ( k  /  N ) ) )
181175, 179dividd 10257 . . . . . . . . 9  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( N  /  N )  =  1 )
182181oveq1d 6233 . . . . . . . 8  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( ( N  /  N )  -  ( k  /  N
) )  =  ( 1  -  ( k  /  N ) ) )
183180, 182eqtrd 2437 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( ( N  -  k )  /  N )  =  ( 1  -  ( k  /  N ) ) )
184183fveq2d 5795 . . . . . 6  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( log `  ( ( N  -  k )  /  N
) )  =  ( log `  ( 1  -  ( k  /  N ) ) ) )
185174, 184sumeq12rdv 13554 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ k  e.  ( ( N  -  N
) ... ( N  -  ( ( N  -  K )  +  1 ) ) ) ( log `  ( ( N  -  k )  /  N ) )  =  sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) ) )
186164, 185eqtrd 2437 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  (
n  /  N ) )  =  sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) ) )
187146adantr 463 . . . . . 6  |-  ( ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  /\  n  e.  ( ( ( N  -  K )  +  1 ) ... N ) )  ->  ( log `  N )  e.  CC )
18894, 100, 187fsumsub 13628 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( ( log `  n
)  -  ( log `  N ) )  =  ( sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n
)  -  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( log `  N
) ) )
189 fsumconst 13630 . . . . . . . 8  |-  ( ( ( ( ( N  -  K )  +  1 ) ... N
)  e.  Fin  /\  ( log `  N )  e.  CC )  ->  sum_ n  e.  ( ( ( N  -  K
)  +  1 ) ... N ) ( log `  N )  =  ( ( # `  ( ( ( N  -  K )  +  1 ) ... N
) )  x.  ( log `  N ) ) )
19094, 146, 189syl2anc 659 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  N
)  =  ( (
# `  ( (
( N  -  K
)  +  1 ) ... N ) )  x.  ( log `  N
) ) )
191 1zzd 10834 . . . . . . . . . . . 12  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  1  e.  ZZ )
192 fzen 11646 . . . . . . . . . . . 12  |-  ( ( 1  e.  ZZ  /\  K  e.  ZZ  /\  ( N  -  K )  e.  ZZ )  ->  (
1 ... K )  ~~  ( ( 1  +  ( N  -  K
) ) ... ( K  +  ( N  -  K ) ) ) )
193191, 137, 155, 192syl3anc 1226 . . . . . . . . . . 11  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( 1 ... K )  ~~  (
( 1  +  ( N  -  K ) ) ... ( K  +  ( N  -  K ) ) ) )
19425nn0cnd 10793 . . . . . . . . . . . . 13  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( N  -  K )  e.  CC )
195 addcom 9699 . . . . . . . . . . . . 13  |-  ( ( 1  e.  CC  /\  ( N  -  K
)  e.  CC )  ->  ( 1  +  ( N  -  K
) )  =  ( ( N  -  K
)  +  1 ) )
196169, 194, 195sylancr 661 . . . . . . . . . . . 12  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( 1  +  ( N  -  K
) )  =  ( ( N  -  K
)  +  1 ) )
197142, 133pncan3d 9869 . . . . . . . . . . . 12  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( K  +  ( N  -  K
) )  =  N )
198196, 197oveq12d 6236 . . . . . . . . . . 11  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( 1  +  ( N  -  K ) ) ... ( K  +  ( N  -  K ) ) )  =  ( ( ( N  -  K )  +  1 ) ... N ) )
199193, 198breqtrd 4408 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( 1 ... K )  ~~  (
( ( N  -  K )  +  1 ) ... N ) )
200 hasheni 12346 . . . . . . . . . 10  |-  ( ( 1 ... K ) 
~~  ( ( ( N  -  K )  +  1 ) ... N )  ->  ( # `
 ( 1 ... K ) )  =  ( # `  (
( ( N  -  K )  +  1 ) ... N ) ) )
201199, 200syl 16 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  (
1 ... K ) )  =  ( # `  (
( ( N  -  K )  +  1 ) ... N ) ) )
202201, 11eqtr3d 2439 . . . . . . . 8  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( # `  (
( ( N  -  K )  +  1 ) ... N ) )  =  K )
203202oveq1d 6233 . . . . . . 7  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( # `  ( ( ( N  -  K )  +  1 ) ... N
) )  x.  ( log `  N ) )  =  ( K  x.  ( log `  N ) ) )
204190, 203eqtrd 2437 . . . . . 6  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  N
)  =  ( K  x.  ( log `  N
) ) )
205204oveq2d 6234 . . . . 5  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( log `  n
)  -  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( log `  N
) )  =  (
sum_ n  e.  (
( ( N  -  K )  +  1 ) ... N ) ( log `  n
)  -  ( K  x.  ( log `  N
) ) ) )
206188, 205eqtrd 2437 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( ( log `  n
)  -  ( log `  N ) )  =  ( sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N ) ( log `  n
)  -  ( K  x.  ( log `  N
) ) ) )
207153, 186, 2063eqtr3rd 2446 . . 3  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( sum_ n  e.  ( ( ( N  -  K )  +  1 ) ... N
) ( log `  n
)  -  ( K  x.  ( log `  N
) ) )  = 
sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) ) )
208207fveq2d 5795 . 2  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( exp `  ( sum_ n  e.  ( ( ( N  -  K
)  +  1 ) ... N ) ( log `  n )  -  ( K  x.  ( log `  N ) ) ) )  =  ( exp `  sum_ k  e.  ( 0 ... ( K  - 
1 ) ) ( log `  ( 1  -  ( k  /  N ) ) ) ) )
209141, 149, 2083eqtr2d 2443 1  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( # `  T )  /  ( # `
 S ) )  =  ( exp `  sum_ k  e.  ( 0 ... ( K  - 
1 ) ) ( log `  ( 1  -  ( k  /  N ) ) ) ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 184    \/ wo 366    /\ wa 367    = wceq 1399    e. wcel 1836   {cab 2381    =/= wne 2591    u. cun 3404    i^i cin 3405   (/)c0 3728   class class class wbr 4384   -->wf 5509   -1-1->wf1 5510   ` cfv 5513  (class class class)co 6218    ^m cmap 7360    ~~ cen 7454   Fincfn 7457   CCcc 9423   0cc0 9425   1c1 9426    + caddc 9428    x. cmul 9430    < clt 9561    <_ cle 9562    - cmin 9740    / cdiv 10145   NNcn 10474   NN0cn0 10734   ZZcz 10803   ZZ>=cuz 11023   RR+crp 11161   ...cfz 11615   ^cexp 12092   !cfa 12278    _C cbc 12305   #chash 12330   sum_csu 13533   expce 13822   logclog 23050
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1633  ax-4 1646  ax-5 1719  ax-6 1765  ax-7 1808  ax-8 1838  ax-9 1840  ax-10 1855  ax-11 1860  ax-12 1872  ax-13 2020  ax-ext 2374  ax-rep 4495  ax-sep 4505  ax-nul 4513  ax-pow 4560  ax-pr 4618  ax-un 6513  ax-inf2 7994  ax-cnex 9481  ax-resscn 9482  ax-1cn 9483  ax-icn 9484  ax-addcl 9485  ax-addrcl 9486  ax-mulcl 9487  ax-mulrcl 9488  ax-mulcom 9489  ax-addass 9490  ax-mulass 9491  ax-distr 9492  ax-i2m1 9493  ax-1ne0 9494  ax-1rid 9495  ax-rnegex 9496  ax-rrecex 9497  ax-cnre 9498  ax-pre-lttri 9499  ax-pre-lttrn 9500  ax-pre-ltadd 9501  ax-pre-mulgt0 9502  ax-pre-sup 9503  ax-addf 9504  ax-mulf 9505
This theorem depends on definitions:  df-bi 185  df-or 368  df-an 369  df-3or 972  df-3an 973  df-tru 1402  df-fal 1405  df-ex 1628  df-nf 1632  df-sb 1758  df-eu 2236  df-mo 2237  df-clab 2382  df-cleq 2388  df-clel 2391  df-nfc 2546  df-ne 2593  df-nel 2594  df-ral 2751  df-rex 2752  df-reu 2753  df-rmo 2754  df-rab 2755  df-v 3053  df-sbc 3270  df-csb 3366  df-dif 3409  df-un 3411  df-in 3413  df-ss 3420  df-pss 3422  df-nul 3729  df-if 3875  df-pw 3946  df-sn 3962  df-pr 3964  df-tp 3966  df-op 3968  df-uni 4181  df-int 4217  df-iun 4262  df-iin 4263  df-br 4385  df-opab 4443  df-mpt 4444  df-tr 4478  df-eprel 4722  df-id 4726  df-po 4731  df-so 4732  df-fr 4769  df-se 4770  df-we 4771  df-ord 4812  df-on 4813  df-lim 4814  df-suc 4815  df-xp 4936  df-rel 4937  df-cnv 4938  df-co 4939  df-dm 4940  df-rn 4941  df-res 4942  df-ima 4943  df-iota 5477  df-fun 5515  df-fn 5516  df-f 5517  df-f1 5518  df-fo 5519  df-f1o 5520  df-fv 5521  df-isom 5522  df-riota 6180  df-ov 6221  df-oprab 6222  df-mpt2 6223  df-of 6461  df-om 6622  df-1st 6721  df-2nd 6722  df-supp 6840  df-recs 6982  df-rdg 7016  df-1o 7070  df-2o 7071  df-oadd 7074  df-er 7251  df-map 7362  df-pm 7363  df-ixp 7411  df-en 7458  df-dom 7459  df-sdom 7460  df-fin 7461  df-fsupp 7767  df-fi 7808  df-sup 7838  df-oi 7872  df-card 8255  df-cda 8483  df-pnf 9563  df-mnf 9564  df-xr 9565  df-ltxr 9566  df-le 9567  df-sub 9742  df-neg 9743  df-div 10146  df-nn 10475  df-2 10533  df-3 10534  df-4 10535  df-5 10536  df-6 10537  df-7 10538  df-8 10539  df-9 10540  df-10 10541  df-n0 10735  df-z 10804  df-dec 10918  df-uz 11024  df-q 11124  df-rp 11162  df-xneg 11261  df-xadd 11262  df-xmul 11263  df-ioo 11476  df-ioc 11477  df-ico 11478  df-icc 11479  df-fz 11616  df-fzo 11740  df-fl 11851  df-mod 11920  df-seq 12034  df-exp 12093  df-fac 12279  df-bc 12306  df-hash 12331  df-shft 12925  df-cj 12957  df-re 12958  df-im 12959  df-sqrt 13093  df-abs 13094  df-limsup 13319  df-clim 13336  df-rlim 13337  df-sum 13534  df-ef 13828  df-sin 13830  df-cos 13831  df-pi 13833  df-struct 14659  df-ndx 14660  df-slot 14661  df-base 14662  df-sets 14663  df-ress 14664  df-plusg 14738  df-mulr 14739  df-starv 14740  df-sca 14741  df-vsca 14742  df-ip 14743  df-tset 14744  df-ple 14745  df-ds 14747  df-unif 14748  df-hom 14749  df-cco 14750  df-rest 14853  df-topn 14854  df-0g 14872  df-gsum 14873  df-topgen 14874  df-pt 14875  df-prds 14878  df-xrs 14932  df-qtop 14937  df-imas 14938  df-xps 14940  df-mre 15016  df-mrc 15017  df-acs 15019  df-mgm 16012  df-sgrp 16051  df-mnd 16061  df-submnd 16107  df-mulg 16200  df-cntz 16495  df-cmn 16940  df-psmet 18547  df-xmet 18548  df-met 18549  df-bl 18550  df-mopn 18551  df-fbas 18552  df-fg 18553  df-cnfld 18557  df-top 19507  df-bases 19509  df-topon 19510  df-topsp 19511  df-cld 19628  df-ntr 19629  df-cls 19630  df-nei 19708  df-lp 19746  df-perf 19747  df-cn 19837  df-cnp 19838  df-haus 19925  df-tx 20171  df-hmeo 20364  df-fil 20455  df-fm 20547  df-flim 20548  df-flf 20549  df-xms 20931  df-ms 20932  df-tms 20933  df-cncf 21490  df-limc 22378  df-dv 22379  df-log 23052
This theorem is referenced by:  birthdaylem3  23423
  Copyright terms: Public domain W3C validator