%I #89 Mar 21 2024 21:18:27
%S 1,1,1,1,2,1,1,1,3,3,3,3,1,1,4,6,6,12,4,3,6,1,1,5,10,10,30,10,15,30,5,
%T 15,10,1,1,6,15,15,60,20,45,90,15,90,60,6,15,45,15,1,1,7,21,21,105,35,
%U 105,210,35,315,210,21,105,315,105,7,105,105,21,1
%N Coefficients for normal ordering of (x + D)^n and for the unsigned, probabilist's (or Chebyshev) Hermite polynomials H_n(x+y).
%C This irregular triangular array contains the integer coefficients of the normal ordering of the expansions of the differential operator R = (x + D)^n with D = d/dx. This operator is the raising/creation operator for the unsigned, modified Hermite polynomials H_n(x) of A099174; i.e., R H_n(x) = H_{n+1}(x). The lowering/annihilation operator L is D; i.e, L H_n(x) = D H_n(x) = n H_{n-1}(x).
%C Generalizing to the ladder operators for S_n(x) a general Sheffer polynomial sequence, (L + R)^n 1 = H_n(S.(x)), where the umbral composition is defined by H_n(S.(x)) = (h. + S.(x))^n = Sum_{k = 0..n} binomial(n,k) h_{n-k} S_k(x), where h_n are the Taylor series coefficients of e^{t^2/2}; i.e., e^{h.t} = e^{t^2/2}.
%C Another interpretation is that the n-th row contains the coefficients of the terms in the normal ordering of the 2^n permutations of two binary symbols given by (L + R)^n under the Leibniz condition LR = RL + 1 equivalent to the commutator relation [L,R] = LR - RL = 1. For example, (x + D)^2 = xx + xD + Dx + DD = x^2 + 2 xD + 1 + D^2.
%C As in the examples, the coefficients are ordered as those for the terms x^k D^m, ordered first from higher k to lower k and subordinately from lower m to higher m.
%C The number sequences associated to these polynomials are intimately related to the complete graphs K_n, which have n vertices and (n-1) edges. H_n(x) are the independence polynomials for K_n. The moments, h_n, of the H_n(x) Appell polynomials are the aerated double factorials A001147, the number of perfect matchings in the complete graph K_{n}, zero for odd n. The row lengths, A002620, give the number of maximal strokes on the complete graph K_n. The triangular numbers--the sum of two consecutive row lengths--give the number of edges of K_n. The row sums, A005425, are the number of matchings of the corona K'_n of the complete graph K_n and the complete graph K_1. K_n can be viewed as the projection onto a plane of the edges of the regular (n-1)-dimensional simplex, whose face polynomials are (x+1)^n - 1 (cf. A135278 and A074909).
%C The coefficients represent the combinatorics of a switchboard problem in which among n subscribers, a subscriber may talk to one of the others, someone on an outside line, or not at all--no conference calls allowed. E.g., the coefficient 12 for H_4(x+y) is the number of ways among 4 subscribers that a pair of subscribers can talk to each other while another is on an outside line and the remaining subscriber is disconnected. The coefficient 3 for the polynomial corresponds to the number of ways two pairs of subscribers can talk among themselves. This can be regarded as a dinner table problem also where a diner may exchange positions with another diner; remain seated; or get up, change plans, and sit back down in the same chair--no more than one exchange per diner.
%C From _Peter Luschny_, May 28 2021: (Start)
%C If we write the monomials of the row polynomials in degree-lexicographic order, we observe: The coefficient triangle appears as a series of concatenated subtriangles. The first one is Pascal's triangle A007318. Appending the rows of triangle A094305 begins in row 2. In row 4, the next triangle starts, which is A344565. This scheme seems to go on indefinitely. [This is now set out in A344911.] (End)
%C From _Tom Copeland_, May 29 2021: (Start)
%C Simplex model: H_n(x+y) = (h. + x + y)^n with h_n the aerated odd double factorials (h_0 = 1, h_1 = 0, h_2 = 1, h_3 = 0, h_4 = 3, h_5 = 0, h_6 = 15, ...), the number of perfect matchings for the n vertices of the (n-1)-Dimensional simplices, i.e., the hypertriangles, or hypertetrahedrons. This multinomial enumerates permutations of three families of objects--vertices labeled with either x or y, or perfect (pair) matchings of the unlabeled vertices for the n vertices of the (n-1)-D simplex. For example, (x+D)^2 = xx + xD + Dx + D^2 = x^2 + 2xD + D^2 + 1 corresponds to H_2(x+y) = (h.+ x + y)^2 = h_0 (x+y)^2 + 2 h_1 (x+y) + h_2 = x^2 + 2xy + y^2 + 1, which, in turn, corresponds to a line segment, the 1-D simplex, with both vertices labeled with x's; or one with an x, the other a y; or both vertices labeled with y's; or one unlabeled matched pair. The exponent k of x^k y^m represents the number of these vertices to which an x is assigned, and m, those with a y assigned. The remaining unlabeled vertices (a sub-simplex) form an independent edge set of (single color) colored edges, i.e., no colored edge is touching another colored edge (a perfect matching for the sub-simplex) nor the vertices assigned an x or y. Accordingly, the coefficients for k=m=0 represent the number of ways to assign a perfect matching to the simplex--zero for simplices with an odd number of vertices and the odd double factorials (1, 3, 15, 105, ...) for the simplices with an even number. For the simplices with an odd number of vertices, the coefficients for k+m=1 are the odd double factorials. (Note the polynomials are invariant upon interchange of the variables x and y.) (End)
%H P. Blasiak and P. Flajolet, <a href="https://arxiv.org/abs/1010.0354v3">Combinatorial Models of Creation-Annihilation</a>, arXiv:1010.0354v3 [math.CO], 2011.
%H A. Varvak, <a href="https://arxiv.org/abs/math/0402376">Rook numbers and the normal ordering problem</a>, arXiv:math/0402376v2 [math.CO], 2004
%F The bivariate e.g.f. is e^{t^2/2} e^{t(x + y)} = Sum_{n >= 0} H_n(x+y) t^n/n! = e^{t H.(x+y)} = e^{t (x + H.(y))}, as described below.
%F The coefficient of x^k D^m is n! h_{n-k-m} / [(n-k-m)! k! m!] with 0 <= k,m <= n and (k+m) <= n with h_n, as defined in the comments, aerated A001147.
%F Row lengths, r(n): 1, 2, 4, 6, 9, 12, 16, 20, 25, ... A002620(n).
%F Row sums: A005425 = 1, 2, 5, 14, 43, 142, ... .
%F The recursion H_{n+1}(x+y) = (x+y) H_n(x+y) + n H_{n-1}(x+y) follows from the differential raising and lowering operations of the Hermite polynomials.
%F The Baker-Campbell-Hausdorff-Dynkin expansion leads to the disentangling relation e^{t (x + D)} = e^{t^2/2} e^{tx} e^{tD} from which the formula above for the coefficients may be derived via differentiation with respect to t.
%F The row bivariate polynomials P_n(x,y) with y a commutative analog of D, or L, have the e.g.f. e^{-xy} e^{t(x + D)} e^{xy} = e^{-xy} e^{t^2/2} e^{tx} e{tD} e^{xy} = e^{t^2/2} e^{t(x + y)} = e^{t(h. + x + y)} = e^{t (x + H.(y))} = e^{t H.(x +y)}, so P_n(x,y) = H_n(x + y) = (x + H.(y))^n, the Hermite polynomials mentioned in the comments along with the umbral composition. The row sums are H_n(2), listed in A005425. For example, P_3(x,y) = (x + H.(y))^3 = x^3 H_0(y) + 3 x^2 H_1(y) + 3 x H_2(y) + H_3(y) = H_3(x+y) = (x+y)^3 + 3(x+y) = x^3 + 3 x^2 y + 3 x + 3 x y^2 + 3 y + y^2.
%F Alternatively, P_n(x,y) = H_n(x+y) = (z + d/dz)^n 1 with z replaced by (x+y) after the repeated differentiations since (x + D)^n 1 = H_n(x).
%F With initial index 1, the lengths r(n) of the rows of nonzero coefficients are the same as those for the polynomials given by 1 + (x+y)^2 + (x+y)^4 + ... + (x+y)^n for n even and for those for (x+y)^1 + (x+y)^3 + ... + (x+y)^n for n odd since the Hermite polynomials are even or odd polynomials. Consequently, r(n)= O(n) = 1 + 2 + 4 + ... n for n odd and r(n) = E(n) = 2 + 4 + ... + n for n even, so O(n) = ((n+1)/2)^2 and E(n) = (n/2)((n/2)+1) = n(n+2)/4 = 2 T(n/2) where T(k) are the triangular numbers defined by T(k) = 0 + 1 + 2 + 3 + ... + k = A000217(k). E(n) corresponds to A002378. Additionally, r(n) + r(n+1) = 1 + 2 + 3 + ... + n+1 = T(n+1).
%F From _Tom Copeland_, May 31 2021: (Start)
%F e^{D^2/2} = e^{h.D}, so e^{D^2/2} x^n = e^{h. D} x^n = (h. + x)^n = H_n(x) and e^{D^2/2} (x+y)^n = e^{h. D} (x+y)^n = (h. + x + y)^n = H_n(x+y).
%F From the Appell Sheffer polynomial calculus, the umbral compositional inverse of the sequence H_n(x+y), i.e., the sequence HI_n(x+y) such that H_n(HI.(x+y)) = (h. + HI.(x+y))^n = (h. + hi. + x + y)^n = (x+y)^n, is determined by e^{-t^2/2} = e^{hi. t}, so hi_n = -h_n and HI_n(x+y) = (-h. + x + y)^n = (-1)^n (h. - x - y)^n = (-1)^n H_n(-(x+y)). Then H_n(-H.(-(x+y))) = (x+y)^n.
%F In addition, HI_n(x) = (x - D) HI_{n-1}(x) = (x - D)^n 1 = e^{-D^2/2} x^n = e^{hi. D} x^n = e^{-h. D} x^n with the e.g.f. e^{-t^2/2} e^{xt}.
%F The umbral compositional inversion property follows from x^n = e^{-D^2/2} e^{D^2/2} x^n = e^{-D^2/2} H_n(x) = H_n(HI.(x)) = e^{D^2/2} e^{-D^2/2} x^n = HI_n(H.(x)). (End)
%F The umbral relations above reveal that H_n(x+y) = (h. + x + y)^n = Sum_{k = 0..n} binomial(n,k) h_k (x+y)^{n-k}, which gives, e.g., for n = 3, H_3(x+y) = h_0 * (x+y)^3 + 3 h_1 * (x+y)^2 + 3 h_2 * (x+y) + h_3 = (x+y)^3 + 3 (x+y), the n-th through 0th rows of the Pascal matrix embedded within the n-th row of the Pascal matrix modulated by h_k. - _Tom Copeland_, Jun 01 2021
%F Varvak gives the coefficients of x^(n-m-k) D^{m-k} as n! / ( 2^k k! (n-k-m)! (m-k)! ), referring to them as the Weyl binomial coefficients, and derives them from rook numbers on Ferrers boards. (No mention of Hermite polynomials nor matchings on simplices are made.) Another combinatorial model and equivalent formula are presented in Blasiak and Flajolet (p. 16). References to much earlier work are given in both papers. - _Tom Copeland_, Jun 03 2021
%e (x + D)^0 = 1,
%e (x + D)^1 = x + D,
%e (x + D)^2 = x^2 + 2 x D + 1 + D^2,
%e (x + D)^3 = x^3 + 3 x^2 D + 3 x + 3 x D^2 + 3 D + D^3,
%e (x + D)^4 = x^4 + 4 x^3 D + 6 x^2 + 6 x^2 D^2 + 12 x D + 4 x D^3 + 3 + 6 D^2 + D^4.
%e (x + D)^5 = x^5 + 5 x^4 D + 10 x^3 + 10 x^3 D^2 + 30 x^2 D + 10 x^2 D^3 + 15 x + 30 x D^2 + 5 x D^4 + 15 D + 10 D^3 + D^5
%e H_6(x + y) = x^6 + 6 x^5 y + 15 x^4 + 15 x^4 y^2 + 60 x^3 y + 20 x^3 y^3 + 45 x^2 + 90 x^2 y^2 + 15 x^2 y^4 + 90 x y + 60 x y^3 + 6 x y^5 + 15 + 45 y^2 + 15 y^4 + y^6
%e H_7(x + y) = x^7 + 7 x^6 y + 21 x^5 + 21 x^5 y^2 + 105 x^4 y + 35 x^4 y^3 + 105 x^3 + 210 x^3 y^2 + 35 x^3 y^4 + 315 x^2 y + 210 x^2 y^3 + 21 x^2 y^5 + 105 x + 315 x y^2 + 105 x y^4 + 7 x y^6 + 105 y + 105 y^3 + 21 y^5 + y^7
%t Last /@ CoefficientRules[#, {x, y}] & /@ Table[Simplify[(-y)^n (-2)^(-n/2) HermiteH[n, (x + 1/y)/Sqrt[-2]]], {n, 0, 7}] // Flatten (* _Andrey Zabolotskiy_, Mar 08 2024 *)
%Y Cf. A000217, A001147, A002378, A002620, A005425, A074909, A099174, A135278.
%Y Cf. A007318, A094305, A344565, A344911.
%K nonn,easy,tabf
%O 0,5
%A _Tom Copeland_, May 26 2021