# Combinatorics of Second Derivative: Graphical Proof of Glaisher-Crofton Identity

Authors: Pawel Blasiak; Gérard H. E. Duchamp; Karol A. Penson
Journal: Advances in Mathematical Physics
 (2018)

---

## Abstract

We give a purely combinatorial proof of the Glaisher-Crofton identity which is derived from the analysis of discrete structures generated by the iterated action of the second derivative. The argument illustrates the utility of symbolic and generating function methodology of modern enumerative combinatorics. The paper is meant for nonspecialists as a gentle introduction to the field of graphical calculus and its applications in computational problems.


---

## Body

## 1. Introduction

Many computational problems involve action of complex expressions in derivatives on functions. A typical example is the exponential of a Hamiltonian acting on some initial condition which is a formal solution to the evolution equation. Applications of the latter range from classical heat and diffusion theory, financial mathematics, and economy to quantum field theory, hence practical interest in operational formulas enabling explicit evaluation of such expressions. Methods used to this effect usually involve operator and special function techniques, integral transforms, umbral calculus methods, etc. See comprehensive review of the subject [1, 2]. In this paper we develop another approach based on modern combinatorial methods of the analysis and enumeration of structures via generating functions [3–5].The most known operational identities that involve the exponential of the first derivative are formulas for the shift and dilation operators(1)expλddxFx=Fx+λexpλxddxFx=Feλxwhere F(x) is an arbitrary function. (Here, we leave subtle problems of convergence aside and consider F(x) as a formal power series in one variable x.) They are a special case of the general closed-form operational expression(2)expλqxddx+vxFx=gλ,x·FTλ,x,where functions T(λ,x) and g(λ,x) are specified by the following equations(3)∂Tλ,x∂λ=qTλ,x,T0,x=x,(4)∂gλ,x∂λ=vTλ,x·gλ,x,g0,x=1.See [1, 2, 6] for the proof based on operator techniques and [7, Sect. 6] for a recently developed combinatorial approach.Note that formulas (1) and (2) are valid for any function F(x). However, this is a very unique situation which holds only for the exponential of an expression linear in the first derivative. For the second derivative the closed-form formulas are not known and the best that can be done is evaluation on specific functions. There are only a few explicit examples which include the formula for the exponential generating function of Hermite polynomials [8] and the Glaisher-Crofton identity [9–11](5)exp-12d2dx2expxt=∑n⩾0Henxtnn!=expxt-12t2,and the Glaisher-Crofton identity [9–11](6)expαd2dx2exp-x2=11+4αexp-x21+4α.Formulas of this type are usually derived using integral representations in the complex domain. (For example, to derive (6) one may use the integral representation exp-x2=∫-∞+∞‍exp-ξ2+2iξxdξ; see [10, 11].) However, in this paper we demonstrate that it is also possible to prove these identities on the basic algebraic level by analysing combinatorial structures generated by the iterated action of the second derivative. In this approach functions are treated as generating functions enumerating simple combinatorial objects (like sets of subsets, cycles, sequences, etc.) and consequently expressions in the derivatives transform objects in the initial class into richer structures whose generating functions can be quickly identified with the methods of symbolic combinatorics [3, 4]. We remark that methodology exposed in this note treads in the steps of combinatorial approach to algebraic identities developed by D. Foata in [12, 13].Our goal in this paper is to develop and promote general combinatorial methodology for solving computational problems which, in many cases, provides better insight into algebraic and analytic manipulations. We illustrate this approach by explaining combinatorial meaning of the exponential of the second derivative and use this interpretation to derive equations (5) and (6).


## 2. Combinatorics of Derivatives

Action of derivatives on a function can be seen as a transformation of combinatorial structures. This viewpoint comes from interpreting the function as a generating function enumerating objects in some combinatorial class. In the following we formalise this intuition by describing the relevant constructions and develop a broader picture which includes higher derivatives and their exponentials. This framework will be illustrated by a simple combinatorial proof and interpretation of Taylor’s formula in Section2.1 and equations (5) and (6) in Sections 2.2 and 3.


### 2.1. Generating Functions, First Derivative, and Taylor’s Formula

Let us consider a combinatorial classF which is defined as a denumerable collection of objects built of atoms represented by X according to some well specified procedure. A typical combinatorial problem consists in enumeration of objects in F according to the size |·|:F→N which is usually the number of atoms. In other words, one seeks the sequence fn=#{ϕ∈F:|ϕ|=n} which counts the number of objects comprised of exactly n atoms. This sequence can be encoded in a generating function(7)Fx=∑ϕ∈Fxϕ=∑n⩾0fnxn,which is a convenient tool for enumeration of complex structures via the so-called transfer rules. The latter translate combinatorial constructions into algebraic manipulations of the corresponding generating functions (see [3–5] for a comprehensive treatment of the subject and the appendix for a quick extract of a few transfer rules used in this paper). In the following we will briefly review combinatorics of the first derivative and recall a simple combinatorial interpretation of Taylor’s formula.Here we will be concerned with the derivative operationyDx acting on some well-defined class F which consists in“selecting in all possible ways a single atom of typeXin each element ofFand replacing it with an atom of a new typeY.”In other words, one may think of the new classyDxF as formed of all structures taken from F in which one of the atoms X gets “repainted” into a new colour Y. Since each structure in F built of n atoms of type X gives rise to n new ones with (n-1) atoms X and a single Y, then the generating function enumerating objects in the new class yDxF is given by(8)Gx,y=∑n,l⩾0gn,lxnyl=∑n⩾1n·fnxn-1y,where gn,l counts objects according to the number of X’s and Y’s, respectively. This is substantiated in the standard transfer rule:(9)Selectingsingleton:G=yDxF⇒Gx,y=yddxFx.Now, let us consider thek-th derivative 1/k!(yDx)k acting on F. Combinatorially it means“select in all possible ways an unordered collection ofkatoms of typeXand replace (repaint) them by atoms of typeY.”Clearly, for each structure of sizen in F we have nk possible choices, and hence the generating function of the new class 1/k!(yDx)kF evaluates to(10)Gx,y=∑n,l⩾0gn,lxnyl=∑n⩾knkfnxn-kyk.In consequence we get the following transfer rule:(11)Selectingk-subset:G=1k!yDxkF⇒Gx,y=1k!ykdkdxkFx,which gives the combinatorial interpretation of the k-th derivative on the level of combinatorial structures.This brings an interesting perspective on the derivative of a function which we will develop throughout the paper. Namely, one may think of a functionF(x) as a generating function of some combinatorial class F. Then differentiation yields a new generating function which enumerates objects in the new class comprised of structures taken from F in which some of the atoms X were replaced with Y’s (how many are replaced depends on the order of the derivative). Hence, the derivative of a function F(x) can be understood as a well-defined combinatorial transformation of the associated combinatorial class F in a sense that on the level of generating functions it corresponds to simple differentiation (cf. (9) and (11)).For illustration of this viewpoint let us recall the usual Taylor’s formula(12)∑k⩾0ykk!Fkx=Fx+y.Surprisingly, it admits a transparent combinatorial interpretation (see [3, Note III.31] or [7, Note 3]). To see this we observe that the l.h.s. is the sum of derivatives expyDx≡∑k⩾0‍1/k!(yDx)k applied to some function F(x) which can be considered as the generating function of some class of objects built of atoms X. Then from our previous discussion the exponential expyDx corresponds to “selecting in all possible ways an arbitrary number ofX’s and replacing them byY’s.”(since the sum contains derivatives of arbitrary order we may choose subsets of arbitrary cardinality). On the other hand, this is the same as substituting each atomX either with atom X (which makes no real effect) or with atom Y (which means the replacement). Hence we have the following combinatorial equivalence(13)expyDxF=F∘X+Y,which on the level of generating functions, by virtue of (11) and the transfer rule for substitutions (see the appendix, (A.4)), directly translates into (12). Hence from the combinatorial point of view Taylor’s formula is a simple manifestation of the following transfer rule (cf. (13)):(14)Selectingarbitrarysubset:G=expyDxF⇒Gx,y=Fx+y,which applies to any combinatorial class F and its generating function F(x). This is a typical example of combinatorial methodology which draws on the fact that in many cases the same combinatorial structure allows different specifications.


### 2.2. Second Derivative and Hermite Polynomials

Combinatorial interpretation of the second derivative can be developed along similar lines. From the above we know that the 2-nd derivative1/2(yDx)2 acting on F consists in“selecting in all possible ways an unordered pair ofXatoms and replacing the chosenX’s by atoms of typeY.”We will call such (unordered) pair adoubleton. Clearly, for an object composed of n atoms this can be done in n(n-1)/2 ways, which agrees with the algebraic identity 1/2(yDx)2xn=n(n-1)/2xn-2y2.More generally, by iteratingk times one picks out a sequence of doubletons in the original structure. Hence, we define the following construction:(15)Selectingk-subsetofdoubletons:G=1k!12yDx2kF⇒12kk!y2kd2kdx2kFx,which consists in“selecting in all possible ways a set ofkunordered pairs (doubletons) ofXatoms and replacing them byYatoms.”Note that, as in (11), we deem the order in the sequence irrelevant by introducing factor 1/k! in front of the iterated derivative (hence the “set” and not the “sequence” in the description). For a quick check of this specification we observe that the coefficient on the r.h.s. of the identity(16)1k!12yDx2kxn=1k!nn-12·n-2n-32·⋯·n-2k+2n-2k+12xn-2ky2kcoincides with the number of possible ways of choosing a set of k unordered pairs from the set of n objects, and hence by linearity we establish correctness of the description and transfer rule (15).Now, we are in position to give interpretation of the exponential of second derivative:(17)Selectingarbitrarysubsetofdoubletons:G=exp12yDx2F≡∑k⩾01k!12yDx2kF,whose combinatorial meaning comes down to “selecting in all possible ways an arbitrary subset of (unordered) pairs ofXatoms and replacing each chosenXby atom of typeY.”This is the sum of the derivative operations of the type (15) which on the level of generating functions is the sum of the derivatives. Unfortunately it does not come close to any neat expression like (12) or (14). Indeed, Taylor’s formula does not generalise in a straightforward manner. Innocuous as it may seem, selecting pairs instead of singletons introduces considerable complexity into the picture and requires careful analysis which quickly gets intractable. However, in particular cases of simple combinatorial structures (and their generating functions) it is possible to carry all the calculus through. An example that we will consider in detail is the Glaisher-Crofton formula (6) which evaluates action of the exponential of the second derivative on the gaussian. Before we proceed to this result, discussed in Section 3, we will illustrate our combinatorial methodology on a simpler case of the action on monomials and provide a link with combinatorial model of Hermite polynomials (cf. [4, 12, 13]).Let us start with the explicit expression which is obtained from expanding the exponential and differentiating the monomial, i.e.,(18)exp12yDx2xn=∑k=0n/2n!2kk!n-2k!xn-2ky2k.For y=i it specialises to the Hermite polynomial Hen(x). More generally, we may also write(19)exp12yDx2expxt=exp12yt2·expxt=expxt+12yt2,which stems from the fact that exp(xt) is an eigenvector of the derivative operator Dx to eigenvalue t. Again, for y=i it is the exponential generating function of Hermite polynomials (cf. (5)). For the purpose at hand we will leave variable y unspecified so as to deal with positive integers only (cf. coefficients in (18)). (It is a typical combinatorial trick to introduce additional labels (or weights) which often allows getting rid of negative or noninteger factors entering multiplicatively in the expressions. Then enumeration of structures proceeds also with respect to this additional label (or weight) which, if needed, can be specified to the required value at the end.) Our aim is to understand these formulas in terms of enumeration of structures.In order to use combinatorial description of (17) we interpret expxt as the exponential generating function of the labelled class of sets Set(XT) (see [3, Sect. II] for a precise definition and discussion of labelled classes and their relation with exponential generating functions). It is comprised of sets whose atoms T carry integer labels 1,2,3,…, and additionally to each T an atom (or weight) of type X is attached; see Figure 1 on the left. We have the following translation rule (see (A.5)):(20)F=SetXT⇒Fx,t=∑n⩾0xntnn!=expxt.(Clearly, for given n one can built one such set and its weight is xn.) Now, following the combinatorial description (17) action of exp1/2(yDx)2 on an individual set in Set(XT) consists in selecting in all possible ways a subset of doubletons. This amounts to splitting of each original set into products of two subsets: one comprising singletons and the other doubletons. Additionally, these subsets differ in that the atoms in the singletons (untouched by the derivatives) carry the weight X, while each atom forming the doubleton (arising from nontrivial action of the second derivative) carries the label Y. Yet another way of seeing the resulting class of objects is to understand them simply as a set of singletons XT and doubletons 1/2(YT)2. See Figure 1 for illustration. Formally, one writes the following sequence of combinatorial equivalences:(21)exp12yDx2SetXT=SetXT×Set12YT2=SetXT+12YT2,which on the level of generating functions readily transform (cf. the appendix) into a sequence of algebraic equalities providing a combinatorial proof of (19).Figure 1
On the left, there is an instance of a structure in classF=Set(XT), i.e., a set of labelled atoms T which are additionally weighted by an atom of type X. In the middle, example of a structure arising from the action of exp(1/2(yDx)2) on F which is obtained by selecting a set of dubletons of X atoms and replacing them by atoms of type Y. Selected pairs are depicted by wavy lines. On the right, decomposition of such a structure into a product of two sets comprising, respectively, singletons XT (untouched by the derivatives) and doubletons 1/2(YT)2 (selected by the derivatives).As a consequence of this discussion we get a simple combinatorial model of Hermite polynomials. Namely, coefficients ofHen(x)=∑k=0n‍hn,kxk count the number of possible ways of“selecting a subset ofkdoubletons (each weighted by-1) out of a set ofndistinguishable objects.”It is exactly the coefficient ofxn-2k in (18) for y=i. Another way to see it directly from our combinatorial description of the exponential of the second derivative is to interpret xn as the generating function of a single n element set; i.e., we have F=Setn(X)⇒F(x)=xn. Then combinatorial model in terms of the choice of doubletons is a simple consequence of the specification of (17). We note that this model is a rephrasing of the interpretation of Hermite polynomials in terms of weighted involutions [4, Sect. 2.3.]. Moreover, it can be straightforwardly extended to provide a combinatorial interpretation of a larger class of multivariate Hermite-Kampé de Fériet polynomials [1, 2].


## 2.1. Generating Functions, First Derivative, and Taylor’s Formula

Let us consider a combinatorial classF which is defined as a denumerable collection of objects built of atoms represented by X according to some well specified procedure. A typical combinatorial problem consists in enumeration of objects in F according to the size |·|:F→N which is usually the number of atoms. In other words, one seeks the sequence fn=#{ϕ∈F:|ϕ|=n} which counts the number of objects comprised of exactly n atoms. This sequence can be encoded in a generating function(7)Fx=∑ϕ∈Fxϕ=∑n⩾0fnxn,which is a convenient tool for enumeration of complex structures via the so-called transfer rules. The latter translate combinatorial constructions into algebraic manipulations of the corresponding generating functions (see [3–5] for a comprehensive treatment of the subject and the appendix for a quick extract of a few transfer rules used in this paper). In the following we will briefly review combinatorics of the first derivative and recall a simple combinatorial interpretation of Taylor’s formula.Here we will be concerned with the derivative operationyDx acting on some well-defined class F which consists in“selecting in all possible ways a single atom of typeXin each element ofFand replacing it with an atom of a new typeY.”In other words, one may think of the new classyDxF as formed of all structures taken from F in which one of the atoms X gets “repainted” into a new colour Y. Since each structure in F built of n atoms of type X gives rise to n new ones with (n-1) atoms X and a single Y, then the generating function enumerating objects in the new class yDxF is given by(8)Gx,y=∑n,l⩾0gn,lxnyl=∑n⩾1n·fnxn-1y,where gn,l counts objects according to the number of X’s and Y’s, respectively. This is substantiated in the standard transfer rule:(9)Selectingsingleton:G=yDxF⇒Gx,y=yddxFx.Now, let us consider thek-th derivative 1/k!(yDx)k acting on F. Combinatorially it means“select in all possible ways an unordered collection ofkatoms of typeXand replace (repaint) them by atoms of typeY.”Clearly, for each structure of sizen in F we have nk possible choices, and hence the generating function of the new class 1/k!(yDx)kF evaluates to(10)Gx,y=∑n,l⩾0gn,lxnyl=∑n⩾knkfnxn-kyk.In consequence we get the following transfer rule:(11)Selectingk-subset:G=1k!yDxkF⇒Gx,y=1k!ykdkdxkFx,which gives the combinatorial interpretation of the k-th derivative on the level of combinatorial structures.This brings an interesting perspective on the derivative of a function which we will develop throughout the paper. Namely, one may think of a functionF(x) as a generating function of some combinatorial class F. Then differentiation yields a new generating function which enumerates objects in the new class comprised of structures taken from F in which some of the atoms X were replaced with Y’s (how many are replaced depends on the order of the derivative). Hence, the derivative of a function F(x) can be understood as a well-defined combinatorial transformation of the associated combinatorial class F in a sense that on the level of generating functions it corresponds to simple differentiation (cf. (9) and (11)).For illustration of this viewpoint let us recall the usual Taylor’s formula(12)∑k⩾0ykk!Fkx=Fx+y.Surprisingly, it admits a transparent combinatorial interpretation (see [3, Note III.31] or [7, Note 3]). To see this we observe that the l.h.s. is the sum of derivatives expyDx≡∑k⩾0‍1/k!(yDx)k applied to some function F(x) which can be considered as the generating function of some class of objects built of atoms X. Then from our previous discussion the exponential expyDx corresponds to “selecting in all possible ways an arbitrary number ofX’s and replacing them byY’s.”(since the sum contains derivatives of arbitrary order we may choose subsets of arbitrary cardinality). On the other hand, this is the same as substituting each atomX either with atom X (which makes no real effect) or with atom Y (which means the replacement). Hence we have the following combinatorial equivalence(13)expyDxF=F∘X+Y,which on the level of generating functions, by virtue of (11) and the transfer rule for substitutions (see the appendix, (A.4)), directly translates into (12). Hence from the combinatorial point of view Taylor’s formula is a simple manifestation of the following transfer rule (cf. (13)):(14)Selectingarbitrarysubset:G=expyDxF⇒Gx,y=Fx+y,which applies to any combinatorial class F and its generating function F(x). This is a typical example of combinatorial methodology which draws on the fact that in many cases the same combinatorial structure allows different specifications.


## 2.2. Second Derivative and Hermite Polynomials

Combinatorial interpretation of the second derivative can be developed along similar lines. From the above we know that the 2-nd derivative1/2(yDx)2 acting on F consists in“selecting in all possible ways an unordered pair ofXatoms and replacing the chosenX’s by atoms of typeY.”We will call such (unordered) pair adoubleton. Clearly, for an object composed of n atoms this can be done in n(n-1)/2 ways, which agrees with the algebraic identity 1/2(yDx)2xn=n(n-1)/2xn-2y2.More generally, by iteratingk times one picks out a sequence of doubletons in the original structure. Hence, we define the following construction:(15)Selectingk-subsetofdoubletons:G=1k!12yDx2kF⇒12kk!y2kd2kdx2kFx,which consists in“selecting in all possible ways a set ofkunordered pairs (doubletons) ofXatoms and replacing them byYatoms.”Note that, as in (11), we deem the order in the sequence irrelevant by introducing factor 1/k! in front of the iterated derivative (hence the “set” and not the “sequence” in the description). For a quick check of this specification we observe that the coefficient on the r.h.s. of the identity(16)1k!12yDx2kxn=1k!nn-12·n-2n-32·⋯·n-2k+2n-2k+12xn-2ky2kcoincides with the number of possible ways of choosing a set of k unordered pairs from the set of n objects, and hence by linearity we establish correctness of the description and transfer rule (15).Now, we are in position to give interpretation of the exponential of second derivative:(17)Selectingarbitrarysubsetofdoubletons:G=exp12yDx2F≡∑k⩾01k!12yDx2kF,whose combinatorial meaning comes down to “selecting in all possible ways an arbitrary subset of (unordered) pairs ofXatoms and replacing each chosenXby atom of typeY.”This is the sum of the derivative operations of the type (15) which on the level of generating functions is the sum of the derivatives. Unfortunately it does not come close to any neat expression like (12) or (14). Indeed, Taylor’s formula does not generalise in a straightforward manner. Innocuous as it may seem, selecting pairs instead of singletons introduces considerable complexity into the picture and requires careful analysis which quickly gets intractable. However, in particular cases of simple combinatorial structures (and their generating functions) it is possible to carry all the calculus through. An example that we will consider in detail is the Glaisher-Crofton formula (6) which evaluates action of the exponential of the second derivative on the gaussian. Before we proceed to this result, discussed in Section 3, we will illustrate our combinatorial methodology on a simpler case of the action on monomials and provide a link with combinatorial model of Hermite polynomials (cf. [4, 12, 13]).Let us start with the explicit expression which is obtained from expanding the exponential and differentiating the monomial, i.e.,(18)exp12yDx2xn=∑k=0n/2n!2kk!n-2k!xn-2ky2k.For y=i it specialises to the Hermite polynomial Hen(x). More generally, we may also write(19)exp12yDx2expxt=exp12yt2·expxt=expxt+12yt2,which stems from the fact that exp(xt) is an eigenvector of the derivative operator Dx to eigenvalue t. Again, for y=i it is the exponential generating function of Hermite polynomials (cf. (5)). For the purpose at hand we will leave variable y unspecified so as to deal with positive integers only (cf. coefficients in (18)). (It is a typical combinatorial trick to introduce additional labels (or weights) which often allows getting rid of negative or noninteger factors entering multiplicatively in the expressions. Then enumeration of structures proceeds also with respect to this additional label (or weight) which, if needed, can be specified to the required value at the end.) Our aim is to understand these formulas in terms of enumeration of structures.In order to use combinatorial description of (17) we interpret expxt as the exponential generating function of the labelled class of sets Set(XT) (see [3, Sect. II] for a precise definition and discussion of labelled classes and their relation with exponential generating functions). It is comprised of sets whose atoms T carry integer labels 1,2,3,…, and additionally to each T an atom (or weight) of type X is attached; see Figure 1 on the left. We have the following translation rule (see (A.5)):(20)F=SetXT⇒Fx,t=∑n⩾0xntnn!=expxt.(Clearly, for given n one can built one such set and its weight is xn.) Now, following the combinatorial description (17) action of exp1/2(yDx)2 on an individual set in Set(XT) consists in selecting in all possible ways a subset of doubletons. This amounts to splitting of each original set into products of two subsets: one comprising singletons and the other doubletons. Additionally, these subsets differ in that the atoms in the singletons (untouched by the derivatives) carry the weight X, while each atom forming the doubleton (arising from nontrivial action of the second derivative) carries the label Y. Yet another way of seeing the resulting class of objects is to understand them simply as a set of singletons XT and doubletons 1/2(YT)2. See Figure 1 for illustration. Formally, one writes the following sequence of combinatorial equivalences:(21)exp12yDx2SetXT=SetXT×Set12YT2=SetXT+12YT2,which on the level of generating functions readily transform (cf. the appendix) into a sequence of algebraic equalities providing a combinatorial proof of (19).Figure 1
On the left, there is an instance of a structure in classF=Set(XT), i.e., a set of labelled atoms T which are additionally weighted by an atom of type X. In the middle, example of a structure arising from the action of exp(1/2(yDx)2) on F which is obtained by selecting a set of dubletons of X atoms and replacing them by atoms of type Y. Selected pairs are depicted by wavy lines. On the right, decomposition of such a structure into a product of two sets comprising, respectively, singletons XT (untouched by the derivatives) and doubletons 1/2(YT)2 (selected by the derivatives).As a consequence of this discussion we get a simple combinatorial model of Hermite polynomials. Namely, coefficients ofHen(x)=∑k=0n‍hn,kxk count the number of possible ways of“selecting a subset ofkdoubletons (each weighted by-1) out of a set ofndistinguishable objects.”It is exactly the coefficient ofxn-2k in (18) for y=i. Another way to see it directly from our combinatorial description of the exponential of the second derivative is to interpret xn as the generating function of a single n element set; i.e., we have F=Setn(X)⇒F(x)=xn. Then combinatorial model in terms of the choice of doubletons is a simple consequence of the specification of (17). We note that this model is a rephrasing of the interpretation of Hermite polynomials in terms of weighted involutions [4, Sect. 2.3.]. Moreover, it can be straightforwardly extended to provide a combinatorial interpretation of a larger class of multivariate Hermite-Kampé de Fériet polynomials [1, 2].


## 3. Proof of the Glaisher-Crofton Identity

Here we prove the identity (6) by a purely combinatorial argument by analysing structures generated by the second derivative discussed above. We will proceed in a step by step manner explaining the details of combinatorial constructions and structures that appear along the way. Although most of them are standard in combinatorial community we take a rather explicit and methodological route that may be of help for an unaccustomed reader. In the following we adopt the standard notation from the book [3] (see also the appendix).Our goal is to calculate the explicit form of the expression (cf. the left hand side of (6) with α=y2/2 and t=-1)(22)exp12yDx2expx2t=∑k⩾01k!yDx2k·∑n⩾0x2tnn!=Rx,y,t.Following our combinatorial strategy we will treat exp(x2t) as an exponential generating function enumerating some combinatorial objects. Let us define them as a labelled class of sets Set(X2T). This class is comprised of sets of labelled atoms T (i.e., each atom carries the integer label) which are weighted with two atoms of type X. We will depict them as sets of doubletons of unlabelled atoms X such that each doubleton carries the labelled marker T. See Figure 2 on the left for illustration. Clearly, we have the following transfer rule (cf. (A.5)):(23)C=SetX2T⇒Cx,t=∑n⩾0x2ntnn!=expx2t.We know from the discussion of (17) that on the combinatorial level exponential exp(1/2(yDx)2) consists in selecting in all possible ways unordered pairs of X’s (not necessarily attached to the same T) and replacing each X in the chosen pairs by Y. Figure 2 in the middle illustrates a generic structure arising in this procedure. If we denote the resulting class of structures by R, then we may write(24)R=exp12yDx2C⇒exp12yDx2expx2t=Rx,y,t,where R(x,y,t)=∑k,l,n⩾0‍Rk,l,nxkyltn/n! is the exponential generating function enumerating structures in R. Note that this gives a precise combinatorial meaning to (22).Figure 2
On the left, there is an instance of a structure inC=Set(X2T), i.e., a set of labelled atoms T which have additional finer structure comprised of two atoms of type X (say the left and the right one). In the middle, example of a structure arising from the action of exp(1/2(yDx)2) on C which is obtained by selecting a set of dubletons of X atoms and replacing them by atoms of type Y. Selected pairs are depicted by wavy lines. On the right, decomposition of such a structure into a product of two sets comprising, respectively, closed (A) and open (B) chains.Since we have reduced our goal to finding the exponential generating functionR(x,y,z) one needs to come up with a systematic specification of structures in R. For this purpose let us observe that doubletons, initially detached from one another in C, are now tied together to form either open or closed chains. Then, we may group them together splitting each structure in R into a product of two sets: one containing only closed and the second open chains. This entails the following combinatorial decomposition and its translation to the exponential generating functions (cf. (A.3) and (A.5)):(25)R=SetA×SetB⇒Rx,y,t=expAx,y,t·expBx,y,t,where A is the class of open chains and B is the class of closed chains; see Figure 2 on the right. Hence the problem comes down to finding both exponential generating functions A(x,y,t) and B(x,y,t) enumerating, respectively, objects of types A and B.Let us start with the class of closed chainsA. Its elements embedded in the plane can be seen as cycles whose building blocks have a finer structure of type Y2T which occurs in two possible configurations arising from two possible choices of X by the derivative in the same doubleton; see Figure 3 for pictorial explanation. Therefore the whole class is specified as follows:(26)A=Cyc2Y2T,and by the standard transfer rule for labelled classes, (A.6), we get(27)Ax,y,t=log11-2y2t.Figure 3
A generic closed chain in classA embedded in the plane can be seen as a cycle built out of two kinds of blocks, each of type Y2T, arising from different choices of X’s attached to the same T by the derivative on either the left or right (hence possible crossings of the wavy lines).The class of open chainsB can be described in a similar manner. First we observe that each such chain can be embedded in the line in two possible ways. Then it forms a sequence which can be decomposed into the inner part which is a sequence of blocks of type YTY with two additional blocks of types XYT and YTX attached at the ends (left and right, respectively). Here as well, each block occurs in two possible configurations arising from two possible choices of X by the derivative in the same doubleton. See Figure 4 for illustration. This gives the following combinatorial specification:(28)B=XTX+122XYT×Seq2YTY×2YTX.Note that the coefficient 1/2 stems from the double counting due to embedding in a line and the term XTX makes up for a single structure left out by the above description. Having specified B we obtain exponential generating function by means of the standard transfer rules, (A.7), which yield(29)Bx,y,t=x2t+122xyt·11-2y2t·2xyt=x2t1-2y2t.Figure 4
If embedded in the line, each open chain inB forms a sequence whose inner part (in the grey box) is built out of blocks of type Y2T with two blocks of type XYT attached at the ends. Here again, each block can have two configurations due to different choices made by the derivatives (possible crossings of the wavy lines).Now, by substituting (27) and (29) to (25), we get(30)Rx,y,t=11-2y2texpx2t1-2y2t.This completes the proof of the Glaisher-Crofton identity, (6), which is readily obtained from (22). In conclusion, let us remark that we benefit from the proof by a deeper combinatorial insight into the nature of both factors on the r.h.s. of (6). The latter can be interpreted as exponential generating functions enumerating sets of closed and open chains, respectively, formed by derivatives acting on the gaussian.


## 4. Discussion and Outlook

Many computational problems require keeping track and skilful rearrangement of terms involved in algebraic expressions. It often comes down to the analysis of their structural properties and counting terms grouped with respect to some relevant characteristics. This is a natural domain of application for modern combinatorics which has developed a large array of tools for systematic treatment of such problems. In this paper, we have considered a few examples where it can be effectively used for evaluation of the action of the exponential in the derivatives on a function. Fundamental in this approach is treatment of the function as a generating function enumerating some simple combinatorial objects. This shift in perspective allows interpreting the derivatives (and their exponentials) as combinatorial constructors which produce a new class of objects which often can be enumerated with combinatorial flair. We have illustrated this approach by showing simple combinatorial proofs and interpretation of Taylor’s formula, connecting exponential in second derivative with a model of Hermite polynomials, and deriving the Glaisher-Crofton identity. It is worth emphasising that the proofs are purely combinatorial and thus do not require any arguments involving integral representations or analyticity. We note that our exposition builds up on the seminal papers of D. Foata [12–14] who gave combinatorial insight into the related Mehler formula. In this paper, the focus is shifted towards graphical calculus based on symbolic methods in enumeration of combinatorial structures in [3, 4].Crucial to our development was combinatorial understanding of the exponential of the second derivative which consists in selecting a collection of unordered pairs in a structure it acts on. It can be also seen as superposition of the doubleton structure on the other one which is connected with the Hadamard product of generating functions considered in various combinatorial contexts (see, e.g., [3, 4, 15]). We should also mention a natural link with a rich framework of umbral calculus [16], where polynomial sequences can be considered as generated by the action of differential operators (see also monomiality principle [17]). Such description is attainable for a large family of Sheffer-type polynomials [18] (including binomial-type and Appell sequences [19]) and therefore admits combinatorial interpretation along the lines considered in the present paper. This theme will be the subject of subsequent publication.We observe that our discussion is not limited only to the first and second derivatives. It can be straightforwardly extended to derivatives of higher order which correspond to selecting subsets of higher cardinality. Moreover, one can generalise this framework to partial derivatives in several variables and multivariate polynomials (e.g., Hermite or Kampé de Fériet polynomials [1, 2]) by interpreting them as enumerating combinatorial structures built of atoms of several kinds.Finally, let us remark that combinatorial approach to derivatives also provides an interesting insights into operator identities. One example is a systematic treatment of the normal ordering problem [7, 20, 21]. Clearly, majority of operator identities admit combinatorial interpretation as they typically arise from algebraic manipulation of discrete structures [4, 22, 23]. As such it opens the whole field of application for combinatorial approach. In this paper we have illustrated this point only on a few examples which can be seen as instances of a broad class of operator identities amenable to combinatorial methodology (cf. Sack identity, Baker-Campbell-Hausdorff formula, Rodrigues-type formulas, Crofton identities, etc. [1, 2]).



---

*Source: 9575626-2018-10-22.xml*