Telephone Numbers and Generating Functions — A Mathematical Exploration

[00:00:02]today we're going to look at something called telephone numbers we'll explore what they are calculate the first couple of telephone numbers and then build the generating function one of my favorite things that will help us get a closed form for these functions so there's a lot of cool tricks that we'll see along the way so what is a telephone number well we'll Define the nth telephone number to be the number of pairwise connections that can be made between in people so let's look at a condition that's allowed and then one that's not allowed so here we've got five people and these two are connected and these two are connected notice this person up here is not connected to anyone that's allowed okay now moving on to this here we've got five people again these two are connected but then this person right here is connected to two people that is not allowed each individual can be connected to zero people or one person that's what we mean by these pairwise connections now we can like draw some nice pictures in order to find the first couple of telephone numbers so for instance if n equals zero well there are no people and we would take that to be like the empty connection space and so we would say the zeroth telephone number was one now if we go to n equals one well the first telephone number is also one there are no connections that can be made between those people again it's kind of like an empty connection now if we move on to n equals two we've got that empty connection where no one is connected but then we could also connect the two people that are in the situation moving to n equals three there are four total types of connections the empty connection and then three kind of depending on who you leave out and then finally the last one that we'll look at specifically is n equals four and there are ten possibilities here and that comes from no one being connected there are six ways that you can connect two people and then there are three ways you can connect two pairs of two people okay so now let's get to building our generating function and building our generating function will start with the recursion which will develop using standard counting techniques so recall that t of n is the number of pairwise connections between n people I'm using T of n here to be our telephone number and then I've got a little bit of a picture of what's going on here so there's person in and then we've got everyone else so obviously we can break this into a couple of cases and maybe the first case is the connections where person in is disconnected okay so well if person in is disconnected then we've got n minus 1 people to connect but we know exactly how to connect n minus one people we do that with t n minus one okay but then we're gonna look at the complement of that situation and so those will be the connections where person in is connected okay so let's go down to our picture here so we've got person in and we're going to connect them to one of the other people in this scenario but how many choices do we have to connect them to someone else well exactly n minus one because there are n minus 1 people left over so I'll just make this connection right here and I'll point out that there are n minus 1 possible ways to make this connection you know here or here or here or so on and so forth after we've done that we're left with all of these people left over and there are exactly n minus two people here that's because we're using person in and whoever we're connecting them to okay we can count the number of connections between n minus two people well that's going to be exactly T of n minus 2 but then we need to multiply that by this first choice this n minus 1 possible ways to connect person in and that builds the rest of this recursion so this choice right here is n minus 1 times T of n minus 2. and there's our recursion so now let's take that and start to build our generating function so we just developed the following recursion for our telephone numbers but now we can almost redefine these numbers in terms of this recursion where we have seeds T of 0 equals T of 1 equals one and now we're going to build an exponential generating function so there are two main types of generating function ordinary generating functions and exponential generating functions and anytime you've got like a multiplication by the index out here you know often at least the exponential generating function is the way to go okay so what do I mean by an exponential generating function well I'm going to set T of x equal to the sum as n goes from 0 to Infinity of T of n so that's our in telephone number over n factorial times x to the N so it looks like maybe the exponential function but it still has part of the sequence in there maybe be making us think that yes it is an exponential generating function okay so let's get to it well we can only apply this recursion if n is bigger than or equal to 2 because the seeds take care of the first two cases so that's exactly the first thing that I'll do is pull out the first two terms the N equals zero term which is one because we have t of zero over zero factorial x to the zero those are all one and then we'll have X for the second term because we have t of 1 over 1 factorial x to the one and then after that we'll have the sum now n is going to go from 2 to Infinity because we took out the first two terms of T of n Over N factorial times x to the N but now we'll take this T of n term and we'll replace it with well what we know from the recursion so in this case it's t of n minus 1 plus n minus 1 times T of n minus 2. so that's the replacement that will really like fuel the first couple steps of our calculation okay so let's rewrite this we'll have 1 plus X those are going to come down and then we'll have the sum as n goes from 2 to Infinity I'm actually going to split this sum into two pieces now that's obviously only allowed if we're in the region where this absolutely converges but the thing with these generating functions is is that we're not really interested in convergence these are so-called formal power series okay so anyway our first term will be t n minus one that's over n factorial and then we have x to the n okay nice and then our second term well it's the sum as n goes from 2 to Infinity again and we'll have n minus 1 times T of n minus 2 that's still over n factorial and it's x to the n and now we'll re-index these so that we get a t of n here instead of a t of n minus 1 or a t of n minus 2. so in this case we need to re-index by replacing all of the ends within plus ones because well n minus 1 plus 1 is clearly equal to n and then over here we'll take all of the ends and replace them with n plus two kind of for the symmetric reason okay so let's see what that leaves us with we'll have 1 plus X plus the sum as n goes from 1 to Infinity that's because if n plus 1 is equal to 2 N is equal to 1 and then we'll have t of n Over N plus 1 factorial but I'm going to write that in plus 1 factorial as n plus 1 times n factorial kind of looking ahead and then I've got x to the N plus one so I've got something like that and then what do we have for this next term so I'll have the sum as n goes from 2 up to Infinity sorry that should be 0 up to Infinity because of our change of index and then this n minus 1 will become an N plus one and then we'll be left with t of n Over N plus 2 factorial and then x to the N plus two okay so now where could we possibly go from here so I'm going to take this x term and recognize that it could be the zeroth term of this series so I'll maybe seem like I'm getting rid of it but what I'm really doing is putting it into that series okay so that's nice and then what am I going to do over here well I'd like to take this n minus 1 and then cancel this n minus 2 factorial down to n plus 2 times n factorial so something like that but now we can start recognizing some things well this one is obviously just going to be brought down as one but look at this we've got an N plus 1 in the denominator and we also have an N plus 1 as our exponent well it looks like we've taken an antiderivative so I make maybe could write this as a symbolic antiderivative as the integral from 0 to X of this sum where well I take the derivative because of the fundamental theorem of calculus if I add in an integral I need to also add in a derivative they annihilate each other so I've got the sum as n goes from 0 up to infinity and now this is T of n Over N factorial and then it is T to the n and now we could just check really quick that if you took this integral or this symbolic antiderivative you would get exactly this thing that's above and now something pretty similar is happening over here except we've got this n plus 2 in the denominator and that n plus 2 as our exponent well that means we've like taken the antiderivative where we had a t to the N plus 1 in there so that looks something like this so the antiderivative from 0 to X of our sum as n goes from 0 to Infinity of t to the N Over N factorial and then t to the N plus one but I'm going to put it in here and a t out here and just recognize that in the end that would be t to the N plus one and then I've got DT here but now let's look at what we've got inside of these anti-derivatives so this thing right here is exactly our exponential generating function which we called T of X up there but now the variable is T so it's like T of t and then this thing within the antiderivative here is almost that it's exactly that multiplied by another variable T so we've got that this is T times capital T of t Okay so let's maybe bring that up here you know realizing that those are still in antiderivatives and then we'll take it from there okay so this is where we ended our last board this is a little bit awkward to work with it's like an integral equation but we can turn it into something that's more familiar a differential equation if we take the derivative of this whole thing so let's say that's what this magenta arrow is it's taking the derivative so that's going to give us T Prime of x equals well the derivative of 1 is 0 but then derivatives and anti-derivatives cancel each other that gives us T of x T of x here we've used the fundamental theorem of calculus part 2 there but now we've erased some information because this one is gone but we can get it back with an initial condition and we know that initial condition because T evaluated at zero well that just cancels out all of the terms except for the well T of zero term it's a little bit awkward there with our variable for our generating function versus our index but I think that's okay so T of 0 is 1. okay so now we've got what's called an initial value problem okay so I think we could maybe like solve that on this board and then get to finding a closed form so we would maybe write it like that but notice very quickly that's going to give us T Prime of X over T of x equals 1 plus X and then we can take the antiderivative of both sides and that will give us the log of T of x equals x squared over 2 plus X plus some constant but now we can evaluate this at zero so T of zero is one the log of 1 is 0. but then these two terms zero out oh but that means that constant is zero so we can actually erase this constant we don't need it but now we can exponentiate both sides and we have a nice closed form for our exponential generating function it's e to the x squared over 2 plus X okay so let's take that and we'll unravel it a bit in order to build a nice closed form so on the last board we got our exponential generating function was e to the x squared over 2 plus X now the first step I'm going to do is split this up into the product of two exponential functions we'll have e to the x squared over 2 times e to the X this is an easier way to expand it and now I'm going to recall the standard expansion for an exponential function and then do that to both of these so let's see that's going to give us the sum as R goes from 0 to Infinity of we'll have x to the 2R over so this is going to be 2 to the r times R factorial okay nice and then what about e to the X well that's even simpler so I've got the sum as s goes from 0 to Infinity of x to the S over s factorial okay now notice that here we have even powers of X and here we have even and odd powers of x so I think maybe the easiest way to continue from here is to break this term right here into even and odd powers of X and only focus on the even ones and then later maybe for a homework exercise you could focus on the odd ones so let's notice this breaks into some pieces so this will break into the even part which is the sum as s goes from 0 to Infinity of x to the 2s over 2s factorial so I think those are pretty clearly the even parts and then we'll have the sum of the odd Parts which will be the sum as s goes from 0 to Infinity of x to the 2s plus one over two S Plus 1 factorial and then let's see where we could go from there so I'm going to take this product given here and here and call that t even so let's do that so we have t even of X is equal to well that product so I've got this sum as R goes from 0 to Infinity of x to the 2R over 2 to the r times R factorial times this even part of the exponential function which I split off so that's the sum as s goes from 0 to Infinity of x to the 2s over 2 s factorial and then maybe I'll write here that there's a similar thing for what I'll call T odd and what do I mean by T even and T odd well the just the even powers of x from our exponential generating function versus the odd powers of x from our exponential generating function which the T even will allow us to calculate the even telephone numbers whereas T odd allows us to calculate the odd telephone numbers Okay so she's product formula on these two series and get like a nice sort of closed-ish form so this turns into the sum as n goes from 0 to Infinity of the sum as K goes from 0 to n of the kth term of this first one so that'll be 1 over let's see 2 to the K times K factorial times the N minus kth term of this second one so that'll be 2N minus 2 K factorial but now we do the same thing for the powers of X it just turns out that those will always multiply to x to the 2N so we have something like that okay so now let's bring that up and then we're pretty much ready to write down our closed form okay so finally we have this nice formula for what I call T even which is the even part of the exponential generating function for the whole thing so writing it out in terms of its definition it's the sum as n goes from 0 to Infinity of T2 n over two n factorial x to the 2N but in terms of all the calculations we do it's this object so notice that the coefficient of x to the 2 in here is exactly equal to all of this stuff whereas the coefficient of x to the 2 in here is all of this stuff so now we get our closed form for T of 2N by equating those and solving for T of 2N and that gives us this following like you know semi-closed form I would call it a closed form it's still in terms of a sum but I think that's okay so we have t of 2N is equal to the sum as K goes from 0 to n of 2 times n factorial over 2 to the K times K factorial times 2N minus 2K factorial site you can rewrite that in terms of some binomial coefficients I'll let you do that on your own though and like I said maybe as a follow-up question you could finish the other calculation to find out what T of well 2N plus 1 is maybe Post in the comments to see what you got and that's a good place to stop thanks for watching and sticking around until the end of the video and since you're here don't forget to gently press that like button subscribe ring the bell and select all notifications to never miss a video if you want to get your name in the credits like you see here access the live seminar series review videos before release and more go to patreon.com michaelpinmath and become a patreon member today if you want full ad free course content subscribe to my second Channel math major I've got courses on linear algebra complex analysis and proof writing among several others and that's everything bye