1
00:00:03,640 --> 00:00:09,394
I just want to briefly mention that 
ordinary generating functions are no the 

2
00:00:09,394 --> 00:00:15,148
only way to represent a sequence with a 
simple function and actually there's an 

3
00:00:15,148 --> 00:00:20,903
important one that plays a very important 
role in analytic combinatorics that I 

4
00:00:20,903 --> 00:00:26,442
just want to mention briefly now. 
you can define other types of kernels to 

5
00:00:26,442 --> 00:00:31,980
represent the sequence so instead of Z to 
the K say we put Z to the K over K 

6
00:00:31,980 --> 00:00:35,939
factorial. 
if we do that then what we have is what's 

7
00:00:35,939 --> 00:00:38,963
called an exponential generating 
function. 

8
00:00:38,963 --> 00:00:44,939
so for example the sequence of all 1s, 
the exponential generating function that 

9
00:00:44,939 --> 00:00:51,058
represents that sequence is Z to the N 
over N factorial and we saw that's E to 

10
00:00:51,058 --> 00:00:57,610
the Z and the powers of two again just do 
the math, two to the N, Z to the N over N 

11
00:00:57,610 --> 00:01:01,642
factorial, that's two to the Z to the N 
over N factorial. 

12
00:01:01,642 --> 00:01:06,235
That's E to the 2Z. 
So same sequence different functions for 

13
00:01:06,235 --> 00:01:12,173
representing them in there are situations 
where it's more natural, it's better, 

14
00:01:12,173 --> 00:01:16,644
it's more convenient to use exponential 
generating functions. 

15
00:01:16,644 --> 00:01:20,310
And many other possibilities have been 
studied. 

16
00:01:20,310 --> 00:01:25,695
but for analytic combinatorics we're 
going to focus on ordinary generating 

17
00:01:25,695 --> 00:01:29,162
functions and exponential generating 
functions. 

18
00:01:29,162 --> 00:01:33,736
So it's worth spending 
here's another one oh, N factorial 

19
00:01:33,736 --> 00:01:39,269
itself, the exponential generating 
function for N factorial is one over one 

20
00:01:39,269 --> 00:01:42,432
minus Z. 
so that's an example of when we might 

21
00:01:42,432 --> 00:01:44,440
need it. 
If you've got a very 

22
00:01:44,440 --> 00:01:50,477
a sequence that grows very fast like n 
factorial ordinary generating function's 

23
00:01:50,477 --> 00:01:54,085
not going to work. 
Some of N factorial Z to the N doesn't 

24
00:01:54,085 --> 00:01:59,785
converge for any Z and it's cumbersome to 
work with so use the exponential 

25
00:01:59,785 --> 00:02:02,930
generating function that's one over one 
minus Z. 

26
00:02:02,930 --> 00:02:07,781
It can be a bit confusing because the 
same functions arise in different 

27
00:02:07,781 --> 00:02:12,292
contexts but really not. 
It's just a different way to represent 

28
00:02:12,292 --> 00:02:16,392
the sequence. 
and we have the same kinds of operations, 

29
00:02:16,392 --> 00:02:21,176
and you can read in the book about 
differentiating, integrating, and so 

30
00:02:21,176 --> 00:02:24,456
forth. 
and there's one important operation 

31
00:02:24,456 --> 00:02:27,873
that's what happens when you multiply two 
EGFs. 

32
00:02:27,873 --> 00:02:31,290
Then you get what's called a binomial 
convolution. 

33
00:02:31,290 --> 00:02:37,429
and that's just applying the same steps 
that we use when we were proving what 

34
00:02:37,429 --> 00:02:43,716
happens with the product of two ordinary 
generating functions but we carry through 

35
00:02:43,716 --> 00:02:49,855
the K factorial and the N factorial, so I 
distribute now when we change N to N 

36
00:02:49,855 --> 00:02:56,142
minus K, we've got a K factorial, N minus 
K factorial but then we can, we need the, 

37
00:02:56,142 --> 00:03:02,574
an N factorial in the denominator anyway, 
so we multiply and divide by N factorial 

38
00:03:02,574 --> 00:03:06,986
and now we've got. 
a exponential after we switch orders. 

39
00:03:06,986 --> 00:03:13,538
we've got a exponential generating 
function for this convolved sequence, the 

40
00:03:13,538 --> 00:03:17,714
binomial convolution. 
And actually there's plenty of 

41
00:03:17,714 --> 00:03:23,690
applications where these kinds of 
sequences arise and we'll see them very 

42
00:03:23,690 --> 00:03:28,476
soon. 
so there's recurrences say, related to 

43
00:03:28,476 --> 00:03:36,827
such problems that arise and if 
confronted with a recurrence like that 

44
00:03:36,827 --> 00:03:41,088
we'll have to now 
naturally from the problem. 

45
00:03:41,088 --> 00:03:46,977
It, that one looks like I should use an 
exponential generating function on. 

46
00:03:46,977 --> 00:03:54,537
so this is an example that actually we'll 
come up with some similar examples in 

47
00:03:54,537 --> 00:04:00,266
specific applications related to 
important algorithms later on. 

48
00:04:00,266 --> 00:04:04,882
so FN equals sum NK of N choose K. 
Fk over two to the K. 

49
00:04:04,882 --> 00:04:10,054
how are we going to function find an 
equation for that number? 

50
00:04:10,054 --> 00:04:13,392
well 
Exponential generating functions we'll 

51
00:04:13,392 --> 00:04:17,849
use the same rule except we make an 
exponential generating function, so that 

52
00:04:17,849 --> 00:04:21,250
is multiplied by z to the n over n 
factorial and sum on n. 

53
00:04:21,250 --> 00:04:26,542
Then on the left hand side we get F of Z. 
And on the right hand side we get a 

54
00:04:26,542 --> 00:04:30,137
double sum. 
and then what we're going to wind up 

55
00:04:30,137 --> 00:04:35,951
doing is, kind of, working backwards for 
the convolution, that we just did. 

56
00:04:35,951 --> 00:04:41,997
so, switch order summation on that. 
that's just switching the sums and, 

57
00:04:41,997 --> 00:04:45,407
keeping. 
Now, if it's all K, then, N's got to be 

58
00:04:45,407 --> 00:04:48,973
bigger than K. 
and then, change N to N + K. 

59
00:04:48,973 --> 00:04:56,027
so that brings us N + K in the top of the 
binomial coefficient, and the exponent is 

60
00:04:56,027 --> 00:04:58,120
Z. 
and N + K factorial. 

61
00:04:58,120 --> 00:05:04,020
and then do some, if the N plus K 
factorials cancel out. 

62
00:05:04,020 --> 00:05:11,678
we still have the F K the Z to the K, and 
the two to the K absorbed together in the 

63
00:05:11,678 --> 00:05:19,603
Z to the N and now those are independent 
sums m so that's the binomial convalution 

64
00:05:19,603 --> 00:05:25,747
backwards and so what it says is that F 
of Z equals E to the Z. 

65
00:05:25,747 --> 00:05:33,050
that's Z to the N over N factorial sum 
and the other one is F to Z over two. 

66
00:05:33,050 --> 00:05:36,815
so f of z equals e to the z, f of z over 
two. 

67
00:05:36,815 --> 00:05:43,675
And that's something we can telescope. 
and this is a little bit formal it's not 

68
00:05:43,675 --> 00:05:50,849
necessarily true that it converges but 
let's [COUGH] not worry about that just 

69
00:05:50,849 --> 00:05:56,878
now and work with the idea that we've 
shown that F of Z equals E of two to the 

70
00:05:56,878 --> 00:06:01,381
Z, E to the 2Z. 
And what's that what's E to the 2Z, the 

71
00:06:01,381 --> 00:06:07,638
exponential generating function for? 
that was one of the first examples that 

72
00:06:07,638 --> 00:06:11,760
we looked at. 
It just says that FN equals two to the N. 

73
00:06:11,760 --> 00:06:17,068
in this case, whether or not a generating 
function converges, we've got an answer 

74
00:06:17,068 --> 00:06:20,781
that we can check. 
2 to the N definitely equals sum on K N 

75
00:06:20,781 --> 00:06:24,740
choose K, 2 to the k / 2 to the k, that's 
the binomial theorum. 

76
00:06:24,740 --> 00:06:30,588
so it looks like a difficult recurrence. 
it actually has an easy solution with 

77
00:06:30,588 --> 00:06:36,575
exponential generating functions. 
And so N works for similar functions too 

78
00:06:36,575 --> 00:06:40,752
where, and that's what happens in the 
practical applications. 

79
00:06:40,752 --> 00:06:46,322
maybe it's N - 1k or maybe there's an 
extra term of some kind how the same 

80
00:06:46,322 --> 00:06:51,752
process works to actually tell us the 
facts that we need to know about the 

81
00:06:51,752 --> 00:06:56,981
algorithms that we're studying. 
we'll see, in much more context, the 

82
00:06:56,981 --> 00:07:02,853
important role that exponential 
generating functions take, when we look 

83
00:07:02,853 --> 00:07:07,220
into, analytic combinatorics in a couple 
of lectures. 

84
00:07:07,220 --> 00:07:11,587
but even in the context of just solving 
recurrences. 

85
00:07:11,587 --> 00:07:16,180
[COUGH], they can be important, as this 
example illustrates.