Two Analogues of a Classical Sequence

Ruedi Suter

Mathematikdepartement ETH Zürich 8092 Zürich, Switzerland

Email address: suter@math.ethz.ch

Abstract

We compute exponential generating functions for the numbers of edges in the Hasse diagrams for the B- and D-analogues of the partition lattices.

1991 Mathematics Subject Classification. Primary 05A15, 52B30; Secondary 05A18, 05B35, 06A07, 11B73, 11B83, 15A15, 20F55

Introduction

When one looks up the sequence 1, 6, 31, 160, 856, 4802, 28 337, 175 896, … in one of Sloane’s integer sequence identifiers [HIS, EIS, OIS], one learns that these numbers are the numbers of driving-point impedances of an n-terminal network for n = 2, 3, 4, 5, 6, 7, 8, 9, … as described in an old article by Riordan [Ri].

In combinatorics there are two common ways of generalizing classical enumerative facts. One such generalization arises by replacing the set [n] = {1, …, n} by an n-dimensional vector space over the finite field 𝔽_{q} to get a q-analogue. The other generalization or extension is by considering “B- and D-analogues” of an “A-case”. This terminology stems from Lie theory. (There is no “C-case” here since it coincides with the “B-case”.) Of course one may try to combine the two approaches and supply q-B- and q-D-analogues.

In this note I shall describe B- and D-analogues of the numbers of driving-point impedances of an n-terminal network. To assuage any possible curiosity about how these sequences look, here are their first few terms:

B-analogue 1, 8, 58, 432, 3396, 28 384, 252 456, 2 385 280, …
D-analogue 0, 4, 31, 240, 1931, 16 396, 147 589, 1 408 224, …

I should probably emphasize that I will only give mathematical arguments and will not attempt to provide a physical realization of B- and D-networks.

We start from certain classical hyperplane arrangements. A hyperplane arrangement defines a family of subspaces, namely those subspaces which can be written as intersections of some of the hyperplanes in the arrangement. For each such subspace we will choose a normal form that represents the subspace. Such a normal form consists of an equivalence class of partial {±1}-partitions in the terminology of Dowling [Do]. Dowling actually constructed G-analogues of the partition lattices for any finite group G. Using the concept of voltage graphs (or signed graphs for |G| = 2) or more generally biased graphs, Zaslavsky gave a far-reaching generalization of Dowling’s work. It is amusing to see that not only the network but also the mathematical treatment of hyperplane arrangements carries a graph-theoretical flavour. Here we will stick to the normal form and not translate things into the framework of graph theory, despite the success this approach has had for example in [BjSa]. In some sense the normal form approach pursues a strategy opposite to that of Zaslavsky’s graphs.

Whitney numbers and characteristic polynomials for hyperplane arrangements or more generally for subspace arrangements, that is, the numbers of vertices with fixed rank in the Hasse diagrams and the Möbius functions, have been studied by many authors. Apparently little attention has been paid so far to the numbers of edges in the Hasse diagrams.

There is another point worth mentioning. It concerns a dichotomy among the A-, B-, and D-series. We will see that everything is very easy for the first two series whereas for the D-series we must work a little harder. Such a dichotomy between the A- and B-series on the one hand and the D-series on the other also occurs in other contexts, e. g., in the problem of counting reduced decompositions of the longest element in the corresponding Coxeter groups (see [St] for the initial paper). In contrast, in the Lie theory one has a different dichotomy, namely, between the simply laced (like A and D) and the non-simply-laced (like B and C) types.

Finally, an obvious generalization, which, however, we do not go into, concerns hyperplane arrangements for the infinite families of unitary reflection groups.

Hyperplane arrangements and their intersection lattices

Let A = {H_{1}, …, H_{N}} be a collection of subspaces of codimension 1 in the vector space ℝ^{n}. We let L(A) denote the poset of all intersections H_{i_{1}} ∩⋯∩H_{i_{r}}, ordered by reverse inclusion. This poset L(A) is actually a geometric lattice. Its bottom element ˆ0 is the intersection over the empty index set, i. e., ℝ^{n}. The atoms are the hyperplanes H_{1}, …, H_{N}, and the top element ˆ1 is H_{1} ∩ ⋯ ∩ H_{N}. For many further details the reader is referred to Cartier’s Bourbaki talk [Ca], Björner’s exposition [Bj] for more general subspace arrangements, and the monograph by Orlik and Terao [OT] for a thorough exposition of the theory.

A theorem due to Orlik and Solomon states that for a finite irreducible Coxeter group W with Coxeter arrangement A = A(W) we have the equality

|A^{H}| = |A| + 1 − h (1)

where H ∈ A is any hyperplane of the arrangement, h is the Coxeter number of W, and A^{H} is the hyperplane arrangement in H with the hyperplanes H ∩ H′ for H′ ∈ A − {H}. In other words, (1) says that each atom in the intersection lattice L(A) is covered by |A| + 1 − h elements. One may wonder what can be said about the number of elements that cover an arbitrary element in L(A).

The intersection lattices that concern us here come from the following hyperplanes in ℝ^{n}.

type of A  elements of A
(A_{1})^{n} {x_{a} = 0}_{a=1,...,n}
A_{n−1}  {x_{b} = x_{c}}_{1⩽b<c⩽n}
B_{n}  {x_{a} = 0}_{a=1,...,n}, {x_{b} = x_{c}}_{1⩽b<c⩽n}, {x_{b} = −x_{c}}_{1⩽b<c⩽n}
D_{n}  {x_{b} = x_{c}}_{1⩽b<c⩽n}, {x_{b} = −x_{c}}_{1⩽b<c⩽n}

Note that ⋂_{H∈A} H is the line x_{1} = ⋯ = x_{n} for type A_{n−1} (so the rank is

n − 1 in this case if n > 0) whereas for the other types the hyperplanes only meet in the zero vector. We agree to let A_{−1} denote the empty hyperplane arrangement in 0. So the intersection lattices for A_{−1} and A_{0} are isomorphic. Also there is a slight abuse of notation for type A_{1} because it can be considered as (A_{1})^{1} or as A_{2−1}. But this will not cause trouble.

For each subspace E ∈ L(A) we define the subset B_{E} ⊆ [n] = {1, …, n} by the property that

C_{E} := ⋂_{a∈[n]−B_{E}}{x_{a} = 0}

is the smallest intersection of coordinate hyperplanes that contains E. For instance if A is of type A_{n−1}, we have B_{E} = [n] for all E ∈ L(A). For the hyperplane E = {x_{1} = x_{2}} ∩ {x_{2} = x_{3}} ∩ {x_{1} = −x_{3}} ∩ {x_{4} = x_{7}} ∩ {x_{5} =x_{8}} ∩ {x_{8} =0} ⊆ ℝ^{8} we get B_{E} = {4, 6, 7}.

Regarded as a subspace of C_{E}, E is described by a partition of B_{E} together with a function ζ : B_{E} → {±1}. If {B_{1}, …, B_{k}} is a partition of B_{E} into k blocks, then E is the k-dimensional subspace

E = {(x_{1}, …, x_{n}) ∈ C_{E} | b, c ∈ B_{j} for some j ⟹ ζ(b) x_{b} = ζ(c) x_{c}}.

Clearly, the correspondence between E and ({B_{1}, …, B_{k}}, ζ) is 1 to 2^{k} because for each block there is a choice of sign.

This correspondence gives us a convenient notation for the subspaces in L(A). We write down a partition of some B ⊆ [n] and decorate the numbers a ∈ B with ζ(a) = −1 with an overbar. Having the possibility of choosing an overall sign for each block, we agree that the smallest number in each block does not have an overbar. As an example take the Coxeter arrangement of type B_{3}. There are 24 subspaces to be considered. Their representations as “signed permutations” are shown in the vertices (boxes) of the following Hasse diagram.

3 123 1\overline{2}3 13 12 1\overline{2} 2 2\overline{3} 23 1\overline{3} 12\overline{3} 1\overline{2}\overline{3} 1 2|3 12|3 1\overline{2}|3 13|2 1|3 1\overline{3}|2 1|2\overline{3} 1|23 1|2 1|2|3

Figure 1. Hasse diagram of the B_{3} lattice

For instance 3 stands for the line x_{1} = x_{2} = 0, 1\overline{2}3 is for x_{1} = −x_{2} = x_{3}, 1|2\overline{3} denotes the plane x_{2} = −x_{3}, 1|2 means x_{3} = 0 etc.

Vertices in the Hasse diagrams

Lemma 1. For a partition {B_{1}, …, B_{k}} of a subset B ⊆ [n] and a function ζ : B → {±1} the k-dimensional subspace

\{(x_{1}, …, x_{n}) ∈ ℝ^{n} | \begin{matrix}a ∈ [n] − B ⟹ x_{a} = 0 \\ b, c ∈ B_{j} for some j ⟹ ζ(b) x_{b} = ζ(c) x_{c} \end{matrix} \}

belongs to L(A) according to the following table.

type of A condition
(A_{1})^{n} |B| = k, ζ = 1
A_{n−1} B = [n], ζ = 1
B_{n}  —
D_{n}  |[n] − B| ≠ 1

Proof. The conditions in the table above should be clear. For the types (A_{1})^{n} and A_{n−1} we put ζ = 1 for simplicity (literally, ζ must only be constant on each block B_{j}). The condition for D_{n} simply takes into account that the hyperplanes x_{a} = 0 do not belong to L(A). But for instance x_{1} = ⋯ = x_{r} = 0 for r ⩾ 2 can be written as x_{1} = −x_{2}, x_{1} = ⋯ = x_{r} and hence this subspace is an element of L(A).

For integers n, k ⩾ 0 and b > 0 let S_{b}(n, k) denote the number of partitions of [n] into k blocks each containing at least b elements. So S_{1}(n, k) = S(n, k) is a Stirling number of the second kind. Besides b = 1 we shall only need the case where b = 2, which one knows from Pólya-Szegő [PS, Part I, Chap. 4, § 3; Part VIII, Chap. 1, No. 22.3]. Nevertheless we state the following more general proposition.

Proposition 2. For every integer b > 0 the generating function for the numbers S_{b}(n, k) of partitions of [n] into k blocks of length at least b is

∑_{n,k⩾0}S_{b}(n, k)\frac{x^{n}}{n!} y^{k} = exp (y · (e^{x} − 1 − x − \frac{x^{2}}{2!} − ⋯ − \frac{x^{b−1}}{(b − 1)!})) .

Proof. For k ⩾ 1 we have the recurrence relation

S_{b}(n, k) = k S_{b}(n − 1, k) + \binom{n−1}{b−1} S_{b}(n − b, k − 1). (2)

In fact, to obtain a partition of [n] into k blocks of lengths at least b, we can either take a partition of [n − 1] into k blocks of lengths at least b and append the element n to any one of the k blocks, or we can take b − 1 elements from [n − 1] which together with n constitute a block with b elements and partition the remaining n − b elements into k − 1 blocks of lengths at least b.

To prove the proposition we must show that for every integer k ⩾ 0

f_{k}(x) := ∑_{n⩾0}S_{b}(n, k)\frac{x^{n}}{n!} = \frac{1}{k!}(e^{x} − 1 − x − \frac{x^{2}}{2!} − ⋯ − \frac{x^{b−1}}{(b − 1)!})^{k}. (3)

This follows by induction on k. The case k = 0 is clear: S_{b}(n, 0) = δ_{n,0}. For k ⩾ 1 we get a differential equation for f_{k}(x), namely

f′_{k}(x) = ∑_{n} S_{b}(n, k)\frac{x^{n−1}}{(n − 1)!}

=^{(2)} ∑_{n} k S_{b}(n − 1, k)\frac{x^{n−1}}{(n − 1)!} + ∑_{n} \binom{n−1}{b−1} S_{b}(n − b, k − 1)\frac{x^{n−1}}{(n − 1)!}

= k f_{k}(x) + \frac{x^{b−1}}{(b − 1)!} f_{k−1}(x)

= k f_{k}(x) + \frac{x^{b−1}}{(b − 1)!} \frac{1}{(k − 1)!}(e^{x} − 1 − x − \frac{x^{2}}{2!} − ⋯ − \frac{x^{b−1}}{(b − 1)!})^{k−1}

whose unique solution satisfying f_{k}(0) = 0 is in fact given by the right hand side in equation (3).

The lattices L(A) are graded posets with rank function the codimension. The rth Whitney number of the second kind of a graded poset is by definition the number of elements of rank r. We begin by making the Whitney numbers quite explicit. We fix one of our hyperplane arrangements A in ℝ^{n} and let W (n, r) be the rth Whitney number (of the second kind) of the intersection lattice L(A). The Whitney numbers W (n, n − k) when written in an array can be seen as a generalization of Pascal’s triangle. In fact, Pascal’s triangle arises for the Boolean lattices of type (A_{1})^{n}.

Let us digress for a moment to consider such generalized Pascal triangles or arrays. The (upper left) corner in the arrays that follow carry the Whitney number W (0, 0), and the entries (p, q) for the other Whitney numbers W (p, q) are in accordance with the following diagram.

W (n, n − k) ⟶ W (n + 1, n − k + 1)
↓
W (n + 1, n − k)

• Pascal arrangements = Coxeter arrangements of type (A_{1})^{n}. W (n, n − k) = \binom{n}{k}.

1 ⟶ 1 ⟶ 1 ⟶ 1 ⟶ ⋯
↓ ↓ ↓ ↓
1 ⟶ 2 ⟶ 3 ⟶ 4 ⟶ ⋯
↓ ↓ ↓ ↓
1 ⟶ 3 ⟶ 6 ⟶ 10 ⟶ ⋯
↓ ↓ ↓ ↓
1 ⟶ 4 ⟶ 10 ⟶ 20 ⟶ ⋯
↓  ↓  ↓  ↓
⋮  ⋮  ⋮  ⋮

• Stirling arrangements = Coxeter arrangements of type A_{n−1}. W (n, n − k) = S(n, k). For the A_{n−1} lattices the analogue of the equation \binom{n}{k} = \binom{n−1}{k}+\binom{n−1}{k−1} reads S(n, k) = k S(n−1, k)+S(n− 1, k − 1), the case b = 1 of (2).

1 ⟶^{·0} 0 ⟶ 0 ⟶ 0 ⟶ ⋯
↓ ↓ ↓ ↓
1 ⟶ 1 ⟶ 1 ⟶ 1 ⟶ ⋯
↓ ↓ ↓ ↓
1 ⟶^{·2} 3 ⟶^{·2} 7 ⟶^{·2} 15 ⟶^{·2} ⋯
↓ ↓ ↓ ↓
1 ⟶^{·3} 6 ⟶^{·3} 25 ⟶^{·3} 90 ⟶^{·3} ⋯
↓ ↓ ↓ ↓
1 ⟶^{·4} 10 ⟶^{·4} 65 ⟶^{·4} 350 ⟶^{·4} ⋯
↓  ↓  ↓  ↓
⋮  ⋮  ⋮  ⋮

• 2-Dowling arrangements = Coxeter arrangements of type B_{n}. W (n, n − k) = T (n, k). For the B_{n} lattices the Whitney numbers satisfy the relation T (n, k) = (2k + 1) T (n − 1, k) + T (n − 1, k − 1) (see Corollary 5).

1 ⟶ 1 ⟶ 1 ⟶ 1 ⟶ ⋯
↓  ↓  ↓  ↓
1 ⟶^{·3} 4 ⟶^{·3} 13 ⟶^{·3} 40 ⟶^{·3} ⋯
↓  ↓  ↓  ↓
1 ⟶^{·5} 9 ⟶^{·5} 58 ⟶^{·5} 330 ⟶^{·5} ⋯
↓  ↓  ↓  ↓
1 ⟶^{·7} 16 ⟶^{·7} 170 ⟶^{·7} 1520 ⟶^{·7} ⋯
↓  ↓  ↓  ↓
⋮  ⋮  ⋮  ⋮

Continuing in the obvious way, one gets Whitney numbers of Dowling lattices corresponding to the complete monomial groups (ℤ/mℤ) ≀ 𝔖_{n}, the wreath product of the symmetric group of degree n acting on (ℤ/mℤ)^{n}. This is straightforward, and calculations can be found in [Be1, Be2]. For the D_{n} lattices the situation is more subtle. The following table suggests why this is so.

type  exponents
(A_{1})^{n} 1, 1, …, 1
A_{n} 1, 2, …, n
B_{n} 1, 3, …, 2n − 1
D_{n} 1, 3, …, 2n − 3, n − 1

The maverick exponent n − 1 for type D_{n} reveals the fact that the determinant of a 2n×2n skew-symmetric matrix is the square of a polynomial in the matrix entries.

This ends our digression. Also from now on we will neglect the nearly trivial case of type (A_{1})^{n}.

Proposition 3. The Whitney numbers W (n, n − k) are given by the following formulae.

\begin{matrix}type & W (n, n − k) \\ A_{n−1} & S(n, k) \\ B_{n} & ∑_{j=k}^{n} 2^{j−k}\binom{n}{j} S(j, k) \\ D_{n} & ∑_{j=k}^{n} 2^{j−k}\binom{n}{j} S(j, k) − 2^{n−1−k}n S(n − 1, k) \end{matrix}

Proof. The proof follows by elementary combinatorial reasoning from the table in Lemma 1. (Recall that S(n, k) is a Stirling number of the second kind.)

The table in Proposition 3 can also be found in the last corollary of [Za].

Theorem 4. The generating functions for the Whitney numbers are as given in the following table.

type ∑_{n,k⩾0}W (n, n − k)\frac{x^{n}}{n!} y^{k}
A exp(y · (e^{x} − 1))
B e^{x} exp(\frac{y}{2} · (e^{2x} − 1))
D (e^{x} − x) exp(\frac{y}{2} · (e^{2x} − 1))

Proof. For type A this is Proposition 2 with b = 1. For type B the coefficients

a_{n}(y) = ∑_{k⩾0} ∑_{j=k}^{n} 2^{j−k}\binom{n}{j} S(j, k) y^{k} ∈ ℤ[y]

are the binomial transforms of

b_{j}(y) = ∑_{k⩾0}2^{j−k}S(j, k) y^{k} ∈ ℤ[y].

Hence

∑_{n⩾0}a_{n}(y)\frac{x^{n}}{n!} = e^{x} ∑_{j⩾0}b_{j}(y)\frac{x^{j}}{j!}

= e^{x} ∑_{j,k} S(j, k)\frac{(2x)^{j}}{j!} (\frac{y}{2})^{k} = e^{x} exp(\frac{y}{2} · (e^{2x} − 1)).

Finally, for type D we need to subtract

∑_{n,k} 2^{n−1−k}n S(n − 1, k)\frac{x^{n}}{n!} y^{k} = x ∑_{n,k} S(n − 1, k)\frac{(2x)^{n−1}}{(n − 1)!}(\frac{y}{2})^{k}

= x exp(\frac{y}{2} · (e^{2x} − 1))

from the generating function for type B.

Setting y = 1 in Theorem 4 we get the exponential generating function for the numbers of vertices in the Hasse diagrams. The coefficients in this exponential generating function are the Bell numbers for type A and the Dowling numbers for type B. For type D these numbers are apparently unnamed.

Corollary 5. The Whitney numbers T (n, k) = W (n, n − k) for the 2-Dowling arrangements satisfy the recurrence relation

T (n, k) = (2k + 1) T (n − 1, k) + T (n − 1, k − 1).

Proof. (\frac{∂}{∂x} − 2 y \frac{∂}{∂y} − 1 − y) e^{x} exp(\frac{y}{2} · (e^{2x} − 1)) = 0.

Edges in the Hasse diagrams

There are two obvious ways to count edges in a Hasse diagram. Namely, go through all vertices and add up the numbers of edges that go upwards, or, dually, that go downwards. As the result of Orlik and Solomon for the elements of rank 1 suggests, it is easier here to count edges corresponding to vertices that cover a given vertex than to count those edges corresponding to vertices that are covered by a given vertex.

An edge in the Hasse diagram for L(A) emanating in an upward direction from E ∈ L(A) corresponds to a subspace E′ ∈ L(A) of codimension 1 in E. We shall count how many such subspaces are contained in E.

Schematically, we have

({B_{1}, …, B_{k}}, ζ) ⇝ ({B′_{1}, …, B′_{k−1}}, ζ′)

with

E = \{(x_{1}, …, x_{n}) ∈ ℝ^{n} | \begin{matrix}a ∈ [n] − B ⟹ x_{a} = 0 \\ b, c ∈ B_{j} for some j ⟹ ζ(b) x_{b} = ζ(c) x_{c} \end{matrix} \}

where B = B_{1} ∪ ⋯ ∪ B_{k}, and E′ is obtained by imposing a further equation,

E′ = \{(x_{1}, …, x_{n}) ∈ ℝ^{n} | \begin{matrix}a ∈ [n] − B′ ⟹ x_{a} = 0 \\ b, c ∈ B′_{j} for some j ⟹ ζ′(b) x_{b} = ζ′(c) x_{c} \end{matrix} \}

where B′ = B′_{1} ∪ ⋯ ∪ B′_{k−1}.

Imposing a further equation may have two different types of incarnations in terms of normal forms. (As usual, B̂_{k} means that B_{k} is omitted.)

• Fusing two blocks. Choose 1 ⩽ i < j ⩽ k, ε ∈ {±1}.

| \begin{matrix}\{B′_{1}, …, B′_{k−1}\} := \{B_{1}, …, B̂_{i}, …, B̂_{j}, …, B_{k}, B_{i} ∪ B_{j}\} \\ ζ′(a) := \begin{cases}ζ(a) & if a ∈ B − B_{j} \\ ε · ζ(a) & if a ∈ B_{j} \end{cases} \end{matrix}

• Dropping one block. Choose 1 ⩽ i ⩽ k.

| \begin{matrix}\{B′_{1}, …, B′_{k−1}\} := \{B_{1}, …, B̂_{i}, …, B_{k}\} \\ ζ′(a) := ζ(a) for all a ∈ B − B_{i} \end{matrix}

Lemma 6. For

({B_{1}, …, B_{k}}, ζ) ⇝ ({B′_{1}, …, B′_{k−1}}, ζ′)

with fixed ({B_{1}, …, B_{k}}, ζ) there are the following numbers of possibilities for fusing two blocks or dropping one block.

type  conditions fusing  dropping
A_{n−1} \begin{matrix}B = [n], ζ = 1 \\ B′ = [n], ζ′ = 1 \end{matrix} \binom{k}{2}  0
B_{n}  —  \binom{k}{2} · 2 k

D_{n}  \begin{matrix}|[n] − B| ≠ 1 \\ |[n] − B′| ≠ 1 \end{matrix} \binom{k}{2} · 2 \begin{cases}k & if B ≠ [n] \\ #\{i | |B_{i}| ⩾ 2\} & if B = [n] \end{cases}

The total number of subspaces of dimension k − 1 in L(A) lying in some fixed subspace E ∈ L(A) of dimension k is thus \binom{k}{2} for type A and k^{2} for type B, while for type D this number is not specified by the dimension alone and can vary between k^{2} − k and k^{2}.

The following diagrams give a rough idea of how the Hasse diagrams look for the first few lattices in the D-series. The first diagram abbreviates the relevant piece of information for the Hasse diagram of the B_{3} lattice, whose full form was given earlier. For instance the Hasse diagram for D_{4} contains

1 · 12 + 12 · 7 + 16 · 3 + 18 · 4 + 24 · 1 + 1 · 0 = 240

edges.

B_{3} {0 \atop 1} {1 \atop 13} {4 \atop 9} {9 \atop 1}  D_{2} = (A_{1})^{2} {0 \atop 1} {1 \atop 2} {2 \atop 1}  D_{3} = A_{3} {0 \atop 1} {1 \atop 7} {3 \atop 6} {6 \atop 1}  D_{4} {0 \atop 1} {1 \atop 24} {3 \atop 16} {4 \atop 18} {7 \atop 12} {12 \atop 1}

D_{5} {0 \atop 1} {1 \atop 81} {3 \atop 40} {4 \atop 150} {7 \atop 40} {8 \atop 60}  {9 \atop 10} {13 \atop 20} {20 \atop 1}  D_{6} {0 \atop 1} {1 \atop 268} {3 \atop 96} {4 \atop 955} {7 \atop 120} {8 \atop 480} {9 \atop 320} {13 \atop 80} {14 \atop 180}  {16 \atop 15} {21 \atop 30} {30 \atop 1}

Figure 2. Abbreviated Hasse diagrams

Theorem 7. The exponential generating functions for the numbers of edges in the Hasse diagrams for types (A_{n−1})_{n⩾0}, (B_{n})_{n⩾0}, and (D_{n})_{n⩾0} are as given in the following table.

type

exponential generating function

A \frac{1}{2}(e^{x} − 1)^{2} exp(e^{x} − 1)

B e^{x} \frac{1}{4}(e^{4x} − 1) exp(\frac{1}{2}(e^{2x} − 1))

D (e^{x} − 1 − x)\frac{1}{4}(e^{4x} − 1) exp(\frac{1}{2}(e^{2x} − 1))

+ e^{x} \frac{1}{4} (e^{4x} − 1 − 4x) exp(\frac{1}{2}(e^{2x} − 1 − 2x))

Proof. For type A_{n−1} there are S(n, k) k-dimensional subspaces each containing \binom{k}{2} subspaces in L(A) of codimension 1. Thus we get the generating function

∑_{n,k} S(n, k)\binom{k}{2} \frac{x^{n}}{n!} = \frac{1}{2} \frac{∂^{2}}{∂y^{2}} ∑_{n,k} S(n, k)\frac{x^{n}}{n!} y^{k}|_{y=1}

= \frac{1}{2} \frac{∂^{2}}{∂y^{2}} exp(y · (e^{x} − 1))|_{y=1} = \frac{1}{2}(e^{x} − 1)^{2} exp(e^{x} − 1).

For type B_{n} there are ∑_{j=k}^{n} 2^{j−k}\binom{n}{j} S(j, k) k-dimensional subspaces

each containing k^{2} subspaces in L(A) of codimension 1. Thus we get the generating function

∑_{n,k} ∑_{j=k}^{n} 2^{j−k}\binom{n}{j} S(j, k) k^{2} \frac{x^{n}}{n!}

= ∑_{j,n} \frac{x^{n−j}}{(n − j)!} \frac{∂}{∂y} y \frac{∂}{∂y} ∑_{k} 2^{j−k}S(j, k)\frac{x^{j}}{j!} y^{k}|_{y=1}

= ∑_{m⩾0} \frac{x^{m}}{m!} \frac{∂}{∂y} y \frac{∂}{∂y} ∑_{j,k} 2^{j−k}S(j, k)\frac{x^{j}}{j!} y^{k}|_{y=1}

= ∑_{m⩾0} \frac{x^{m}}{m!} \frac{∂}{∂y} y \frac{∂}{∂y} exp(\frac{y}{2} · (e^{2x} − 1))|_{y=1}

= ∑_{m⩾0} \frac{x^{m}}{m!} \frac{1}{4}(e^{4x} − 1) exp(\frac{1}{2}(e^{2x} − 1))

= e^{x} \frac{1}{4}(e^{4x} − 1) exp(\frac{1}{2}(e^{2x} − 1)).

The reader may wonder why we did not insert the formula for

∑_{n,k} ∑_{j} 2^{j−k}\binom{n}{j} S(j, k)\frac{x^{n}}{n!} y^{k}

directly. The reason for going through the seemingly arcane substitution m = n − j is that we can then use this calculation for type D. Namely, for type D we must subtract the terms for j = n−1 and j = n, that is, for m = 1 and m = 0 in the generating function for B and then add the modified term corresponding to j = n.

Let us direct our attention to the case B = [n] for D_{n}. We get a partition of [n] into k blocks with exactly h blocks of length 1 by choosing h elements from [n] and partitioning the remaining set of n − h elements into k − h blocks of lengths at least 2. Taking into account also the choice of ζ : [n] → {±1}, we have

2^{n−k}\binom{n}{h} S_{2}(n − h, k − h)

elements of rank n − k in the Hasse diagram for D_{n} which are covered by k^{2} − h elements. The modified term corresponding to j = n is thus

∑_{n,k} ∑_{h} 2^{n−k}\binom{n}{h} S_{2}(n − h, k − h) (k^{2} − h)\frac{x^{n}}{n!}

= ∑_{n,k} ∑_{h} \frac{x^{h}}{h!} 2^{n−k}S_{2}(n − h, k − h) (k^{2} − h)\frac{x^{n−h}}{(n − h)!} y^{k}|_{y=1}

= ∑_{h} \frac{x^{h}}{h!} (\frac{∂}{∂y} y \frac{∂}{∂y} − h)y^{h} ∑_{n,k} 2^{n−k}S_{2}(n − h, k − h)\frac{x^{n−h}}{(n − h)!} y^{k−h}|_{y=1}

= ∑_{h} \frac{x^{h}}{h!} (\frac{∂}{∂y} y \frac{∂}{∂y} − h)y^{h} exp(\frac{y}{2} · (e^{2x} − 1 − 2x))|_{y=1}

= ∑_{h} \frac{x^{h}}{h!} (h^{2} − h + (2h + 1)\frac{1}{2}(e^{2x} − 1 − 2x) + \frac{1}{4}(e^{2x} − 1 − 2x)^{2})

× exp(\frac{1}{2}(e^{2x} − 1 − 2x))

= e^{x}(x^{2} + (2x + 1)\frac{1}{2}(e^{2x} − 1 − 2x) + \frac{1}{4}(e^{2x} − 1 − 2x)^{2})

× exp(\frac{1}{2}(e^{2x} − 1 − 2x))

= e^{x} \frac{1}{4}(e^{4x} − 1 − 4x) exp(\frac{1}{2}(e^{2x} − 1 − 2x)).

The exponential generating function for the numbers of edges for the D-series therefore takes the form

(e^{x}−1−x)\frac{1}{4}(e^{4x}−1) exp(\frac{1}{2}(e^{2x}−1))+e^{x} \frac{1}{4}(e^{4x}−1−4x) exp(\frac{1}{2}(e^{2x}−1−2x)).

A curious determinant

Apparently it was A. Lenard who discovered that the Hankel determinant with the Bell numbers as entries is a superfactorial (see the reference in [We]). Let us compute its B-analogue. So let the Dowling numbers D_{n} be given by

∑_{n⩾0}D_{n} \frac{x^{n}}{n!} = e^{x} exp(\frac{1}{2}(e^{2x} − 1)).

Proposition 8.

| \begin{matrix}D_{0} & D_{1} & … & D_{n} \\ D_{1} & D_{2} & … & D_{n+1} \\ ⋮ & ⋮ & & ⋮ \\ D_{n} & D_{n+1} & … & D_{2n} \end{matrix} | = 2^{n(n+1)/2} ∏_{k=1}^{n} k!

We shall prove the following generalization which involves the numbers G_{n} (for l = 0) that occurred in Kerber’s note [Ke, (7)] in connexion with multiply transitive groups and also in M. Bernstein’s and Sloane’s “eigen-sequence paper” [BeSl, Table 1(a)] in a new setting.

Proposition 9. Define the sequence of generalized Bell numbers (G_{n})_{n⩾0} depending on l and m by

∑_{n⩾0}G_{n} \frac{x^{n}}{n!} = e^{lx} exp(\frac{1}{m}(e^{mx} − 1)). (4)

Then

| \begin{matrix}G_{0} & G_{1} & … & G_{n} \\ G_{1} & G_{2} & … & G_{n+1} \\ ⋮ & ⋮ & & ⋮ \\ G_{n} & G_{n+1} & … & G_{2n} \end{matrix} | = m^{n(n+1)/2} ∏_{k=1}^{n} k! (5)

Proof. The statement in [Ko, p. 113/114] can be rephrased by saying that a Hankel determinant does not change its value when the matrix entries are subject to a binomial transform. Hence the determinant in (5) is independent of l ∈ ℤ and consequently also independent of l when l is considered as an indeterminate. Therefore we will assume that l = 0 in the definition (4) of the numbers G_{n}.

As an aside let us mention that the invariance under binomial transform gives the following identity between Hankel determinants with Bell numbers as entries.

| \begin{matrix}B_{0} & B_{1} & … & B_{n} \\ B_{1} & B_{2} & … & B_{n+1} \\ ⋮ & ⋮ & & ⋮ \\ B_{n} & B_{n+1} & … & B_{2n} \end{matrix} | = | \begin{matrix}B_{1} & B_{2} & … & B_{n+1} \\ B_{2} & B_{3} & … & B_{n+2} \\ ⋮ & ⋮ & & ⋮ \\ B_{n+1} & B_{n+2} & … & B_{2n+1} \end{matrix} |

To compute the determinant (5) we proceed by induction. Let us first define H_{n,k} ∈ ℚ[m] by

∑_{n⩾0}H_{n,k} \frac{y^{n}}{n!} = \frac{1}{k!} e^{−y} \frac{1}{m^{k}} (log(1 + my))^{k} (k = 0, 1, 2, …). (6)

Note that H_{n,n} = 1. Hence with

I_{h,n} = ∑_{k=0}^{n} G_{h+k} H_{n,k} (7)

we have

| \begin{matrix}G_{0} & G_{1} & … & G_{n} \\ G_{1} & G_{2} & … & G_{n+1} \\ ⋮ & ⋮ & & ⋮ \\ G_{n} & G_{n+1} & … & G_{2n} \end{matrix} | = | \begin{matrix}G_{0} & … & G_{n−1} & I_{0,n} \\ ⋮ & & ⋮ & ⋮ \\ G_{n−1} & … & G_{2n−2} & I_{n−1,n} \\ G_{n} & … & G_{2n−1} & I_{n,n} \end{matrix} | . (8)

From

∑_{h,n} I_{h,n} \frac{x^{h}}{h!} \frac{y^{n}}{n!} = exp(\frac{1}{m}(e^{mx} − 1)) exp(y · (e^{mx} − 1)) (9)

we see that I_{0,n} = ⋯ = I_{n−1,n} = 0 and I_{n,n} = m^{n} ·n!. Hence (5) follows from (8) by induction.

We must finally prove (9). So let us compute:

∑_{h,n} I_{h,n} \frac{x^{h}}{h!} \frac{y^{n}}{n!} =^{(7)} ∑_{h,k,n} G_{h+k} H_{n,k} \frac{x^{h}}{h!} \frac{y^{n}}{n!}

=^{(6)} ∑_{h,k} G_{h+k} \frac{x^{h}}{h!} \frac{1}{k!} e^{−y} \frac{1}{m^{k}} (log(1 + my))^{k}

= e^{−y} ∑_{h,k} G_{h+k} \frac{1}{(h + k)!} \binom{h+k}{h} x^{h} \frac{1}{m^{k}} (log(1 + my))^{k}

= e^{−y} ∑_{n} G_{n} \frac{1}{n!}(x + \frac{1}{m} log(1 + my))^{n}

=^{(4)} e^{−y} exp(\frac{1}{m} (e^{m(x+ \frac{1}{m} log(1+my))} − 1))

= exp(\frac{1}{m}(e^{mx} − 1)) exp(y · (e^{mx} − 1)).

We have thus verified equation (9).

Acknowledgements. Without Sloane’s integer sequence database I would probably never have come across the reference [Ri]. Also at one instance the gfun Maple package by Salvy and Zimmermann [SZ] was helpful.

References

[Be1] M. Benoumhani, On Whitney numbers of Dowling lattices, Discrete Math. 159 (1996), 13–33. MR 98a:06005

[Be2] , On some numbers related to Whitney numbers of Dowling lattices, Adv. in Appl. Math. 19 (1997), 106–116. MR 98f:05004

[BeSl] M. Bernstein, N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226/228 (1995), 57–72. MR 96i:05004 (Available electronically in pdf or postscript form.)

[Bj] A. Björner, Subspace arrangements, in: First European Congress of Mathematics, Vol. I (Paris, 1992), Progr. Math. 119, pp. 321–370, Birkhäuser, Basel 1994. MR 96h:52012

[BjSa] A. Björner, B. E. Sagan, Subspace arrangements of type B_{n} and D_{n}, J. Algebraic Combin. 5 (1996), 291–314. MR 97g:52028

[Ca] P. Cartier, Les arrangements d’hyperplans: un chapitre de géométrie combinatoire, in: Bourbaki Seminar, Vol. 1980/81, Lecture Notes in Math. 901, pp. 1–22, Springer, Berlin, New York 1981. MR 84d:32017

[Do] T. A. Dowling, A class of geometric lattices based on finite groups, J. Combin. Theory Ser. B 14 (1973), 61–86; Erratum, J. Combin. Theory Ser. B 15 (1973), 211. MR 46:7066, MR 47:8369

[EIS] N. J. A. Sloane, S. Plouffe, The encyclopedia of integer sequences, Academic Press, San Diego 1995. MR 96a:11001

[HIS] N. J. A. Sloane, A handbook of integer sequences, Academic Press, New York 1973. MR 50:9760

[Ke] A. Kerber, A matrix of combinatorial numbers related to the symmetric groups, Discrete Math. 21 (1978), 319–321. MR 80h:20008

[Ko] G. Kowalewski, Einführung in die Determinantentheorie, Verlag von Veit & Comp., Leipzig 1909.

[OIS] N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://www.research.att.com/∼njas/sequences/

[OS] P. Orlik, L. Solomon, Coxeter arrangements, in: Singularities, Proc. Symp. Pure Math. 40 Part 2, pp. 269–291, Amer. Math. Soc., Providence 1983. MR 85b:32016

[OT] P. Orlik, H. Terao, Arrangements of hyperplanes Grundlehren 300, Springer, Berlin 1992. MR 94e:52014

[PS] G. Pólya, G. Szegő, Problems and theorems in analysis, Grundlehren 193, 216, Springer, Berlin 1972, 1976. MR 49:8782, MR 53:2

[Ri] J. Riordan, The number of impedances of an n-terminal network, Bell System Technical Journal 18 (1939), 300–314.

[St] R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin. 5 (1984), 359–372. MR 86i:05011

[SZ] B. Salvy, P. Zimmermann, Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (1994), 163–177.

[We] E. W. Weisstein, CRC concise encyclopedia of mathematics, CRC Press, Boca Raton 1999.

[Za] T. Zaslavsky, The geometry of root systems and signed graphs, Amer. Math. Monthly 88 (1981), 88–105. MR 82g:05012

(Concerned with sequences A003128, A039755, A039756, A039757, A039758, A039759, A039760, A039761, A039762, A039763, A039764, A039765.)

Received Jan. 13, 2000; published in Journal of Integer Sequences March 10, 2000.

Return to Journal of Integer Sequences home page.