Jason (jcreed) wrote,

After I finished up work for the day, (result: I think I at least understand the source of my bug now...) I found myself playing another round of "WTF, The On-Line Encyclopedia of Integer Sequences?".

I had a rather old idea about Conor McBride's type derivative stuff, which is that I sometimes want zipper-like data structures for many-holed data. Like maybe I want to think about a (text/tree/arbitrary data) editor that lets you bookmark different editing points, or maybe think of a real piece of concurrent version control software that has many editing agents active at once.

So instead of just the the operator D that takes a polymorphic type and returns its one-hole version, I might like to consider (1 + D + D^2 + D^3 + ...) which allows any number of holes, or even (1 + D/1! + D^2/2! + D^3/3! + ...) which considers all those holes equivalent. The latter is actually totally easy - you just "add one" to the underlying type. To make this clear, abbreviate (1 + D/1! + D^2/2! + D^3/3! + ...) punningly as e^D. That is if my type operator is F : * → *, and someone hands me a type T : *, then (e^D F)(T) = F(T + 1). This has a natural combinatorial interpretation that if you allow a hole anywhere that the argument T of F appears, then it's like you just expanded that type by one other option, namely "a hole goes here". Also it makes sense if you look at Taylor series. The Taylor series approximation to f(x + 1) is just f(x) + f'(x) + f''(x)/2! + ... = (e^D f)(x).

Anyway, that operator is easy to deal with, but I might prefer to keep my different holes distinct. I don't know a whole lot about this case, but I discovered some cute things about it while playing around with mathematica and OLEoIS. Let me make another punning abbreviation: 1/(1-D) = 1 + D + D^2 + D^3 + ... I want to get a simple example going. Let's try applying this operator to list. I know that D list = list^2, (a list with a hole in it is the same as two lists, the left-of-hole piece, and the right-of-hole piece) and more generally, D^n list = n! list^(n+1). so

(1/(1-D)) list =      (list + list^2 + 2! list^3 + 3! list^4 + ...)
               = list (1    + list   + 2! list^2 + 3! list^3 + ...)

Now that bit in parens looks like it wants to be the following function applied to 'list':

y(x) = 1 + x + 2! x^2 + 3! x^3 + 4! x^4 + ...

It's like the exponential power series, but upside-down: I'm multiplying by factorials instead of dividing by them. What is this function?

Well... its radius of convergence around zero is NO IT DOESN'T. No matter how small x is, n! grows faster than x^n. Nonetheless, using generatingfunctiony intuitions, it looks like it should satisfy the diffeq

x D(x y(x)) = y(x) - 1

because imagine taking a term n! x^n, multiplying it by x to get n! x^(n+1), taking a derivative to get (n+1)! x^n, multiplying by x again to get (n+1)! x^(n+1), and you've recreated the same power series except you've moved up the ladder and nobody lands on 1.

So I asked mathematica what function has this property and it said

(e^(-1/x) Ei(1/x))/x

which is indeterminate at zero, but is a sensible function elsewhere on the real line, and for all I know looking at its graph it might be smooth at zero if you plugged the discontinuity. As a function on the complex plane it looks like it goes through a bunch of other garbage in the vicinity of zero and seems to have infinitely many poles around there, so that's gross.

Anyway! Looking at this unfamiliar-to-me function Ei, the so-called Exponential Integral, expanding its power series around some other points yields a few cute combinatorial sequences.

The arrangements of n things (that is, the total collection of subsets laid out in some order, like the arrangments of {A, B} are empty sequence, A, B, AB, BA) come from -e times the iterated derivatives of Ei at -1, the derangements arise from the alternating series of the iterated derivatives of Ei at 1 after you multiply the nth derivative by (-e)^(-n), and likewise the number of partial permutations are the iterated derivatives of Ei(1/x) at 1, multiplied by (-e)^(-n).


Hmmm maybe this isn't such a big deal after all. These three also appear naturally as the power series around zero for e^x/(1-x) (arrangements) e^-x/(1-x) (derangements) and e^(x/(1-x))/(1-x) (partial permutations) and their integrals then involve the exponential integral.
Tags: math, sequences

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded