Publ. I.R.M.A. Strasbourg, 1984, 229/S–08 Actes 8^{e} Séminaire Lotharingien, p. 87–89

A COMMON GENERALIZATION OF BINOMIAL

COEFFICIENTS, STIRLING NUMBERS AND

GAUSSIAN COEFFICIENTS

BY

Bernd VOIGT

Let A_{0}, A_{1}, A_{2}, … be finite sets. For nonnegative integers n and k denote by S_{k}^{n}(a_{0}, a_{1}, a_{2}, …), where a_{i} = |A_{i}|, the number of words w = (w_{0}, …, w_{n−1}) such that

(1) w contains k labels, say at positions i_{0}, …, i_{k−1},

(2) all entries in w before position i_{0} belong to A_{0}, all entries in w between positions i_{l} and i_{l+1}, where l = 0, …, k − 2, belong to A_{l+1}, all entries after position i_{k−1} belong to A_{k}.

A_{0}  A_{1}  A_{l+1}  A_{k}
×  × . . . . . . . . . ×  × . . . . . . . . . ×
i_{0}  i_{1}  i_{l}  i_{l+1}  i_{k−1}

As S_{n}^{k}(a⃗) = ∑_{0≤i_{0}<i_{1}<···<i_{k−1}<n} a_{0}^{i_{0}} · a_{1}^{i_{1}−i_{0}−1} ⋯ a_{k}^{n−i_{k−1}−1}, the numbers

S_{k}^{n} can be obviously defined for sequences of complex numbers.

Examples.

(1) S_{n}^{k}(1, 1, …) = \binom{n}{k}  (Binomial coefficients)
(2) S_{k}^{n}(0, 1, 2, …) = S_{k}^{n}  (Stirling numbers of the second kind)
(3) S_{k}^{n}(1, q, q^{2}, …) = \binom{n}{k}_{q}  (Gaussian binomial coefficients)

(4) S_{k}^{n}(q, q^{2}, q^{3}, …) = number of affine k-dimensional subspaces in the n-dimensional affine space over GF (q).

B. VOIGT

(5) S_{k}^{n}(2, 3, 4, …) = number of Boolean sublattices P (k) in P (n) (P (n) ≡ lattice of subsets of an m-element set).

Pascal-identity : S_{k}^{n+1}(a⃗) = S_{k−1}^{n} + a_{k} · S_{k}^{n}.

explicitly : S_{k}^{n}(a⃗) = ∑_{i=0}^{k} a_{i}^{n} · ∏_{j=0 j≠i}(a_{i} − a_{j})^{−1}, provided a_{0}, …, a_{k} are

mutually distinct.

Let P a⃗ ; 0(x) = 1 and P a⃗ ; k+1(x) = (x − a_{k}) · P a⃗ ; k(x), i.e.

P a⃗ ; k(x) = (x − a_{k−1}) ⋯ (x − a_{0}).

Inversion, resp. interpolation formulae :

x^{n} = ∑_{k≥0} S_{k}^{n}(a⃗) · P a⃗ ; k(x).

Now one can introduce the inverse numbers s_{k}^{n}(a⃗) by ∑_{j} s_{j}^{n}(a⃗)·S_{k}^{j}(a⃗) = δ_{k}^{n} (Kronecker delta).

Recursion : s_{k}^{n+1}(a⃗) = s_{k−1}^{n} − a_{n} · s_{k}^{n}.

These numbers can be used in order to describe inversion for arbitrary ascending sequences of normalized polynomials : let

S_{k}^{n}(a⃗, b⃗) = ∑_{j} s_{j}^{n}(a⃗) · S_{k}^{j}(b⃗).

then

P a⃗ ; n(x⃗) = ∑_{k} S_{k}^{n}(a⃗, v⃗) · P b⃗ ; k(x).

Recursion : S_{k}^{n+1}(a⃗, b⃗) = S_{k−1}^{n}(a⃗, v⃗) + (b_{k} − a_{k}) · S_{k}^{n}(a⃗, b⃗).

Theorem. — Let a⃗ as before, l a complex number, then

(i) S_{k}^{n}(a⃗) = ∑_{j} \binom{n}{j} · l^{n−j} · S_{k}^{j}(a⃗ − l),

(ii) S_{k}^{n}(a⃗) = ∑_{j} \binom{j}{k} · l^{j−k} · S_{j}^{n}(a⃗ − l),

(iii) s_{k}^{n}(a⃗) = ∑_{j} \binom{n}{j} · l^{n−j} · s_{k}^{j}(a⃗ + l), (iv) s_{k}^{n}(a⃗) = ∑_{j} \binom{j}{k} · l^{j−k} · s_{j}^{n}(a⃗ + l).

COMMON GENERALIZATION OF COEFFICIENTS

Remark. — The case a⃗ = (1, q, q^{2}, …) and l = 1 is a theorem of

CARLITZ [1].

Corollary. — The number of Boolean sublattices of P (n) is equal to the (n + 2)-nd Bell number B_{n+2}.

REFERENCES

[1] CARLITZ (L.). — On abelian fields, Trans. Amer. Math. Soc., t. 35, 1933, p. 122– 126.

Bernd Voigt, Fakultät für Mathematik der Universität, Postfach 8640, D-48 Bielefeld.