# Zeons, Permanents, the Johnson Scheme, and Generalized Derangements

Authors: Philip Feinsilver; John McSorley
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

Starting with the zero-square “zeon algebra,” the connection with permanents is shown. Permanents of submatrices of a linear combination of the identity matrix and all-ones matrix lead to moment polynomials with respect to the exponential distribution. A permanent trace formula analogous to MacMahon's master theorem is presented and applied. Connections with permutation groups acting on sets and the Johnson association scheme arise. The families of numbers appearing as matrix entries turn out to be related to interesting variations on derangements. These generalized derangements are considered in detail as an illustration of the theory.


---

## Body

## 1. Introduction

Functions acting on a finite set can be conveniently expressed using matrices, whereby the composition of functions corresponds to multiplication of the matrices. Essentially, one is considering the induced action on the vector space with the elements of the set acting as a basis. This action extends to tensor powers of the vector space. One can take symmetric powers, antisymmetric powers, and so forth, that yield representations of the multiplicative semigroup of functions. An especially interesting representation occurs by taking nonreflexive, symmetric powers. Identifying the underlying set of cardinalityn with {1,2,…,n}, the vector space has basis e1,e2,…. The action we are interested in may be found by saying that the elements ei generate a “zeon algebra,” the relations being that the ei commute, with ei2=0, 1≤i≤n. To get a feeling for this, first we recall the action on Grassmann algebra where the matrix elements of the induced action arise as determinants. For the zeon case, permanents appear.An interesting connection with the centralizer algebra of the action of the symmetric group comes up. For the defining action on the set{1,…,n}, represented as 0-1 permutation matrices, the centralizer algebra of n×n matrices commuting with the entire group is generated by I, the identity matrix, and J, the all-ones matrix. The question was if they would help determine the centralizer algebra for the action on subsets of a fixed size, ℓ-sets, for ℓ>1. It is known that the basis for the centralizer algebra is given by the adjacency matrices of the Johnson scheme. Could one find this working solely with I and J? The result is that by computing the “zeon powers”, that is, the action of sI+tJ, linear combinations of I and J, on ℓ-sets, the Johnson scheme appears naturally. The coefficients are polynomials in s and t occurring as moments of the exponential distribution. And they turn out to count derangements and related generalized derangements. The occurrence of Laguerre polynomials in the combinatorics of derangements is well known. Here, the 2F1 hypergeometric function, which is closely related to Poisson-Charlier polynomials, arises rather naturally.Here is an outline of the paper. Section2 introduces zeons and permanents. The trace formula is proved. Connections with the centralizer algebra of the action of the symmetric group on sets are detailed. Section 3 is a study of exponential polynomials needed for the remainder of the paper. Zeon powers of sI+tJ are found in Section 4 where the spectra of the matrices are found via the Johnson scheme. Section 5 presents a combinatorial approach to the zeon powers of sI+tJ, including an interpretation of exponential moment polynomials by elementary subgraphs. In Section 6, generalized derangement numbers, specifically counting derangements and counting arrangements, are considered in detail. The Appendix has some derangement numbers and arrangement numbers for reference, as well as a page of exponential polynomials. An example expressing exponential polynomials in terms of elementary subgraphs is given there.


## 2. Representations of Functions Acting on Sets

Let𝒱 denote the vector space ℚn or ℝn. We will look at the action of a linear map on 𝒱 extended to quotients of tensor powers 𝒱⊗ℓ. We work with coordinates rather than vectors. First, recall the Grassmann case. To find the action on 𝒱∧ℓ consider an algebra generated by n variables ei satisfying eiej=-ejei. In particular, ei2=0.Notation 2.
The standardn-set {1,…,n} will be denoted [n]. Roman caps I, J, A, and so forth denote subsets of [n]. We will identify them with the corresponding ordered tuples. Generally, given an n-tuple (x1,…,xn) and a subset I⊂[n], we denote products
(2.1)xI=∏j∈Ixj,
where the indices are in increasing order if the variables are not assumed to commute.
As an index, we will useU to denote the full set [n].
ItalicI and J will denote the identity matrix and all-ones matrix, respectively.For a matrixXIJ, say, where the labels are subsets of fixed size l, dictionary ordering is used. That is, convert to ordered tuples and use dictionary ordering. For example, for n=4, l=2, we have labels 12,13,14,23,24,and34 for rows one through six, respectively.A basis for𝒱∧ℓ is given by products (2.2)eI=ei1ei2⋯eil,I⊂[n], where we consider I as an ordered ℓ-tuple. Given a matrix X acting on 𝒱, let (2.3)yi=∑jXijej,
with corresponding products yI, then the matrix X∧ℓ has entries given by the coefficients in the expansion (2.4)yI=∑J(X∧l)IJeJ
where the anticommutation rules are used to order the factors in eJ. Note that the coefficient of ej in yi is Xij itself. And for n>3, the coefficient of e34 in y12 is (2.5)det⁡(X13X14X23X24).
We see that in general the IJ entry of X∧ℓ is the minor of X with row labels I and column labels J. A standard term for the matrix X∧ℓ is a compound matrix. Noting that X∧ℓ is (nℓ)×(nℓ), in particular, ℓ=n yields the one-by-one matrix with entry equal to (X∧n)UU=detX.In this work, we will use the algebra ofzeons, standing for “zero-ons”, or more specifically, “zero-square bosons”. That is, we assume that the variables ei satisfy the properties (2.6)eiej=ejei,ei2=0.
A basis for the algebra is again given by eI, I⊂[n]. At level ℓ, the induced matrix X∨ℓ has IJ entries according to the expansion of yI,(2.7)yi=∑jXijej⟶yI=∑J(X∨l)IJeJ
similar to the Grassmann case. Since the variables commute, we see that the IJ entry of X∨ℓ is the permanent of the submatrix with rows I and columns J. In particular, (X∨n)UU=perX. We refer to the matrix X∨ℓ as the “ℓth zeon power of X.”


### 2.1. Functions on the Power Set of[n]

Note thatX∨ℓ is indexed by ℓ-sets. Suppose that Xf represents a function f:[n]→[n]. So it is a zero-one matrix with (Xf)ij=1, the single entry in row i if f maps i to j. The ℓth zeon power of X is the matrix of the induced map on ℓ-sets. If f maps an ℓ-set I to one of lower cardinality, then the corresponding row in X∨ℓ has all zero entries. Thus, the induced matrices in general correspond to “partial functions”.However, ifX is a permutation matrix, then X∨ℓ is a permutation matrix for all 0≤ℓ≤n. So, given a group of permutation matrices, the map X→X∨ℓ is a representation of the group.


### 2.2. Zeon Powers ofsI+tX

Our main theorem computes theℓth zeon power of sI+tX for an n×n matrix X, where s and t are scalar variables. Figure 1 illustrates the proof.Figure 1
Configuration of sets:B=I∖A, C=J∖A.Theorem 2.1.
For a given matrixX, for 0≤ℓ≤n, and indices |I|=|J|=ℓ,
(2.8)((sI+tX)∨l)IJ=∑0≤j≤lsl-jtj∑A⊂I∩J|A|=l-j(X∨j)I∖A,J∖A.Proof.
Start withyi=sei+tξi, where ξi=∑jXijej. Given I=(i1,…,iℓ), we want the coefficient of eJ in the expansion of the product yI=yi1⋯yiℓ. Now,
(2.9)yI=(sei1+tξi1)⋯(seil+tξil).
Choose A⊂I with |A|=ℓ-j, 0≤j≤ℓ. A typical term of the product has the form
(2.10)sl-jtjeAξB
where A∩B=∅, B=I∖A. ξB denotes the product of terms ξi with indices in B. Expanding, we have
(2.11)ξB=∑C(X∨j)BCeC,eAξB=∑C(X∨j)BCeAeC.
Thus, for a contribution to the coefficient of eJ, we have A∪C=J, where A∩C=∅. That is, C=J∖A and A⊂I∩J. So, the coefficient of sℓ-jtj is as stated.


### 2.3. Trace Formula

Another main feature is thetrace formula which shows the permanent of I+tX as the generating function for the traces of the zeon powers of X. This is the zeon analog of the theorem of MacMahon for representations on symmetric tensors.Theorem 2.2.
One has the formula(2.12)per(sI+tX)=∑jsn-jtjtr⁡X∨j.Proof.
The permanent ofsI+tX is the UU entry of (sI+tX)∨n. Specialize I=J=U in Theorem 2.1. So A is any (n-j)-set with I∖A=J∖A=A′, its complement in [n]. Thus,
(2.13)per(sI+tX)=((sI+tX)∨n)UU=∑0≤j≤nsn-jtj∑|A|=n-j(X∨j)A′,A′=∑0≤j≤nsn-jtjtr⁡X∨j,
as required.


### 2.4. Permutation Groups

LetX be an n×n permutation matrix. We can express per(I+tX) in terms of the cycle decomposition of the associated permutation.Proposition 2.3.
For a permutation matrixX,
(2.14)per(I+tX)=∏0≤l≤n(1+tl)nX(l),
where nX(ℓ) is the number of cycles of length ℓ in the cycle decomposition of the corresponding permutation.Proof.
Decomposing the permutation associated toX yields a decomposition into invariant subspaces of the underlying vector space 𝒱. So per(I+tX) will be the product of per(I+tXc) as c runs through the corresponding cycles with Xc the restriction of X to the invariant subspace for each c. So we have to check that if X acts on 𝒱ℓ as a cycle of length ℓ, then per(I+tX)=1+tℓ. For this, apply Theorem 2.2. Apart from level zero, there is only one set fixed by any X∨j, namely when j=ℓ. So the trace of X∨j is zero unless j=ℓ and then it is one. The result follows.


#### 2.4.1. Cycle Index: Orbits onℓ-sets

Now, consider a group,G, of permutation matrices. We have the cycle index (2.15)ZG(z1,z2,…,zn)=1|G|∑X∈Gz1nX(1)z2nX(2)⋯znnX(n),
each zℓ corresponding to ℓ-cycles in the cycle decomposition associated to the Xs. From Proposition 2.3, we have an expression in terms of permanents. Combining with the trace formula, we get the following.Theorem 2.4.
LetG be a permutation group of matrices, then one has
(2.16)1|G|∑X∈Gper(I+tX)=ZG(1+t,1+t2,…,1+tn)=∑ltl#(orbits onl-sets).Remark 2.5.
This result refers to three essential theorems in group theory acting on sets. Equality of the first and last expressions is the “permanent” analog of Molien's theorem, which is the case for a group acting on the symmetric tensor algebra, that the cycle index counts orbits on subsets is an instance of Polya Counting, with two colors. The last expression is followed by the Cauchy-Burnside lemma applied to the groupsG∨ℓ={X∨ℓ}X∈G.


#### 2.4.2. Centralizer Algebra and Johnson Scheme

Given a group,G, of permutation matrices, an important question is to determine the set (among all matrices) of matrices commuting with all of the matrices in G. This is the centralizer algebra of the group. For the symmetric group, the only matrices are I and J. For the action of the symmetric group on ℓ-sets, a basis for the centralizer algebra is given by the incidence matrices for the Johnson distance. These are the same as the adjacency matrices for the Johnson (association) scheme. Recall that the Johnson distance between two ℓ-sets I and J is (2.17)distJS(I,J)=12|IΔJ|=|I∖J|=|J∖I|.
The corresponding matrices JSknℓ are defined by (2.18)(JSknl)IJ={1ifdistJS(I,J)=k,0,otherwise.
As it is known, [1, page 36], that a basis for the centralizer algebra is given by the orbits of the group G2, acting on pairs, the Johnson basis is a basis for the centralizer algebra. Since the Johnson distance is symmetric, it suffices to look at G∨2.Now, we come to the question that is a starting point for this work. IfI and J are the only matrices commuting with all elements (as matrices) of the symmetric group, then since the map G→G∨ℓ is a homomorphism, we know that I∨ℓ and J∨ℓ are in the centralizer algebra of G∨ℓ. The question is how to obtain the rest? The, perhaps surprising, answer is that in fact one can obtain the complete Johnson basis from I and J alone. This will be one of the main results, Theorem 4.1.


#### 2.4.3. Permanent ofsI+tJ

First, let us considersI+tJ.Proposition 2.6.
One has the formula(2.19)per(sI+tJ)=n!∑0≤l≤nsltn-ll!.Proof.
ForX=J, we see directly, since all entries equal one in all submatrices, that
(2.20)(J∨l)IJ=l!
for all I and J. Taking traces,
(2.21)tr⁡J∨l=(nl)l!,
and by the trace formula, Theorem 2.2,
(2.22)per(sI+tJ)=∑l(nl)l!sn-ltl=∑ln!(n-l)!sn-ltl.
Reversing the order of summation yields the result stated.Corollary 2.7.
For varyingn, one will explicitly denote pn(s,t)=per(sIn+tJn), then, with            p0(s,t)=1,
(2.23)∑n=0∞znn!pn(s,t)=esz1-tz.The Corollary exhibits the operational formula(2.24)pn(s,t)=11-tDssn,
where Ds=d/ds. By inspection, this agrees with (2.19) as well.Observe that (2.19) can be rewritten as (2.25)per(sI+tJ)=∫0∞(s+ty)ne-ydy,
that is, these are “moment polynomials” for the exponential distribution with an additional scale parameter.We proceed to examine these moment polynomials in detail.


## 2.1. Functions on the Power Set of[n]

Note thatX∨ℓ is indexed by ℓ-sets. Suppose that Xf represents a function f:[n]→[n]. So it is a zero-one matrix with (Xf)ij=1, the single entry in row i if f maps i to j. The ℓth zeon power of X is the matrix of the induced map on ℓ-sets. If f maps an ℓ-set I to one of lower cardinality, then the corresponding row in X∨ℓ has all zero entries. Thus, the induced matrices in general correspond to “partial functions”.However, ifX is a permutation matrix, then X∨ℓ is a permutation matrix for all 0≤ℓ≤n. So, given a group of permutation matrices, the map X→X∨ℓ is a representation of the group.


## 2.2. Zeon Powers ofsI+tX

Our main theorem computes theℓth zeon power of sI+tX for an n×n matrix X, where s and t are scalar variables. Figure 1 illustrates the proof.Figure 1
Configuration of sets:B=I∖A, C=J∖A.Theorem 2.1.
For a given matrixX, for 0≤ℓ≤n, and indices |I|=|J|=ℓ,
(2.8)((sI+tX)∨l)IJ=∑0≤j≤lsl-jtj∑A⊂I∩J|A|=l-j(X∨j)I∖A,J∖A.Proof.
Start withyi=sei+tξi, where ξi=∑jXijej. Given I=(i1,…,iℓ), we want the coefficient of eJ in the expansion of the product yI=yi1⋯yiℓ. Now,
(2.9)yI=(sei1+tξi1)⋯(seil+tξil).
Choose A⊂I with |A|=ℓ-j, 0≤j≤ℓ. A typical term of the product has the form
(2.10)sl-jtjeAξB
where A∩B=∅, B=I∖A. ξB denotes the product of terms ξi with indices in B. Expanding, we have
(2.11)ξB=∑C(X∨j)BCeC,eAξB=∑C(X∨j)BCeAeC.
Thus, for a contribution to the coefficient of eJ, we have A∪C=J, where A∩C=∅. That is, C=J∖A and A⊂I∩J. So, the coefficient of sℓ-jtj is as stated.


## 2.3. Trace Formula

Another main feature is thetrace formula which shows the permanent of I+tX as the generating function for the traces of the zeon powers of X. This is the zeon analog of the theorem of MacMahon for representations on symmetric tensors.Theorem 2.2.
One has the formula(2.12)per(sI+tX)=∑jsn-jtjtr⁡X∨j.Proof.
The permanent ofsI+tX is the UU entry of (sI+tX)∨n. Specialize I=J=U in Theorem 2.1. So A is any (n-j)-set with I∖A=J∖A=A′, its complement in [n]. Thus,
(2.13)per(sI+tX)=((sI+tX)∨n)UU=∑0≤j≤nsn-jtj∑|A|=n-j(X∨j)A′,A′=∑0≤j≤nsn-jtjtr⁡X∨j,
as required.


## 2.4. Permutation Groups

LetX be an n×n permutation matrix. We can express per(I+tX) in terms of the cycle decomposition of the associated permutation.Proposition 2.3.
For a permutation matrixX,
(2.14)per(I+tX)=∏0≤l≤n(1+tl)nX(l),
where nX(ℓ) is the number of cycles of length ℓ in the cycle decomposition of the corresponding permutation.Proof.
Decomposing the permutation associated toX yields a decomposition into invariant subspaces of the underlying vector space 𝒱. So per(I+tX) will be the product of per(I+tXc) as c runs through the corresponding cycles with Xc the restriction of X to the invariant subspace for each c. So we have to check that if X acts on 𝒱ℓ as a cycle of length ℓ, then per(I+tX)=1+tℓ. For this, apply Theorem 2.2. Apart from level zero, there is only one set fixed by any X∨j, namely when j=ℓ. So the trace of X∨j is zero unless j=ℓ and then it is one. The result follows.


### 2.4.1. Cycle Index: Orbits onℓ-sets

Now, consider a group,G, of permutation matrices. We have the cycle index (2.15)ZG(z1,z2,…,zn)=1|G|∑X∈Gz1nX(1)z2nX(2)⋯znnX(n),
each zℓ corresponding to ℓ-cycles in the cycle decomposition associated to the Xs. From Proposition 2.3, we have an expression in terms of permanents. Combining with the trace formula, we get the following.Theorem 2.4.
LetG be a permutation group of matrices, then one has
(2.16)1|G|∑X∈Gper(I+tX)=ZG(1+t,1+t2,…,1+tn)=∑ltl#(orbits onl-sets).Remark 2.5.
This result refers to three essential theorems in group theory acting on sets. Equality of the first and last expressions is the “permanent” analog of Molien's theorem, which is the case for a group acting on the symmetric tensor algebra, that the cycle index counts orbits on subsets is an instance of Polya Counting, with two colors. The last expression is followed by the Cauchy-Burnside lemma applied to the groupsG∨ℓ={X∨ℓ}X∈G.


### 2.4.2. Centralizer Algebra and Johnson Scheme

Given a group,G, of permutation matrices, an important question is to determine the set (among all matrices) of matrices commuting with all of the matrices in G. This is the centralizer algebra of the group. For the symmetric group, the only matrices are I and J. For the action of the symmetric group on ℓ-sets, a basis for the centralizer algebra is given by the incidence matrices for the Johnson distance. These are the same as the adjacency matrices for the Johnson (association) scheme. Recall that the Johnson distance between two ℓ-sets I and J is (2.17)distJS(I,J)=12|IΔJ|=|I∖J|=|J∖I|.
The corresponding matrices JSknℓ are defined by (2.18)(JSknl)IJ={1ifdistJS(I,J)=k,0,otherwise.
As it is known, [1, page 36], that a basis for the centralizer algebra is given by the orbits of the group G2, acting on pairs, the Johnson basis is a basis for the centralizer algebra. Since the Johnson distance is symmetric, it suffices to look at G∨2.Now, we come to the question that is a starting point for this work. IfI and J are the only matrices commuting with all elements (as matrices) of the symmetric group, then since the map G→G∨ℓ is a homomorphism, we know that I∨ℓ and J∨ℓ are in the centralizer algebra of G∨ℓ. The question is how to obtain the rest? The, perhaps surprising, answer is that in fact one can obtain the complete Johnson basis from I and J alone. This will be one of the main results, Theorem 4.1.


### 2.4.3. Permanent ofsI+tJ

First, let us considersI+tJ.Proposition 2.6.
One has the formula(2.19)per(sI+tJ)=n!∑0≤l≤nsltn-ll!.Proof.
ForX=J, we see directly, since all entries equal one in all submatrices, that
(2.20)(J∨l)IJ=l!
for all I and J. Taking traces,
(2.21)tr⁡J∨l=(nl)l!,
and by the trace formula, Theorem 2.2,
(2.22)per(sI+tJ)=∑l(nl)l!sn-ltl=∑ln!(n-l)!sn-ltl.
Reversing the order of summation yields the result stated.Corollary 2.7.
For varyingn, one will explicitly denote pn(s,t)=per(sIn+tJn), then, with            p0(s,t)=1,
(2.23)∑n=0∞znn!pn(s,t)=esz1-tz.The Corollary exhibits the operational formula(2.24)pn(s,t)=11-tDssn,
where Ds=d/ds. By inspection, this agrees with (2.19) as well.Observe that (2.19) can be rewritten as (2.25)per(sI+tJ)=∫0∞(s+ty)ne-ydy,
that is, these are “moment polynomials” for the exponential distribution with an additional scale parameter.We proceed to examine these moment polynomials in detail.


## 2.4.1. Cycle Index: Orbits onℓ-sets

Now, consider a group,G, of permutation matrices. We have the cycle index (2.15)ZG(z1,z2,…,zn)=1|G|∑X∈Gz1nX(1)z2nX(2)⋯znnX(n),
each zℓ corresponding to ℓ-cycles in the cycle decomposition associated to the Xs. From Proposition 2.3, we have an expression in terms of permanents. Combining with the trace formula, we get the following.Theorem 2.4.
LetG be a permutation group of matrices, then one has
(2.16)1|G|∑X∈Gper(I+tX)=ZG(1+t,1+t2,…,1+tn)=∑ltl#(orbits onl-sets).Remark 2.5.
This result refers to three essential theorems in group theory acting on sets. Equality of the first and last expressions is the “permanent” analog of Molien's theorem, which is the case for a group acting on the symmetric tensor algebra, that the cycle index counts orbits on subsets is an instance of Polya Counting, with two colors. The last expression is followed by the Cauchy-Burnside lemma applied to the groupsG∨ℓ={X∨ℓ}X∈G.


## 2.4.2. Centralizer Algebra and Johnson Scheme

Given a group,G, of permutation matrices, an important question is to determine the set (among all matrices) of matrices commuting with all of the matrices in G. This is the centralizer algebra of the group. For the symmetric group, the only matrices are I and J. For the action of the symmetric group on ℓ-sets, a basis for the centralizer algebra is given by the incidence matrices for the Johnson distance. These are the same as the adjacency matrices for the Johnson (association) scheme. Recall that the Johnson distance between two ℓ-sets I and J is (2.17)distJS(I,J)=12|IΔJ|=|I∖J|=|J∖I|.
The corresponding matrices JSknℓ are defined by (2.18)(JSknl)IJ={1ifdistJS(I,J)=k,0,otherwise.
As it is known, [1, page 36], that a basis for the centralizer algebra is given by the orbits of the group G2, acting on pairs, the Johnson basis is a basis for the centralizer algebra. Since the Johnson distance is symmetric, it suffices to look at G∨2.Now, we come to the question that is a starting point for this work. IfI and J are the only matrices commuting with all elements (as matrices) of the symmetric group, then since the map G→G∨ℓ is a homomorphism, we know that I∨ℓ and J∨ℓ are in the centralizer algebra of G∨ℓ. The question is how to obtain the rest? The, perhaps surprising, answer is that in fact one can obtain the complete Johnson basis from I and J alone. This will be one of the main results, Theorem 4.1.


## 2.4.3. Permanent ofsI+tJ

First, let us considersI+tJ.Proposition 2.6.
One has the formula(2.19)per(sI+tJ)=n!∑0≤l≤nsltn-ll!.Proof.
ForX=J, we see directly, since all entries equal one in all submatrices, that
(2.20)(J∨l)IJ=l!
for all I and J. Taking traces,
(2.21)tr⁡J∨l=(nl)l!,
and by the trace formula, Theorem 2.2,
(2.22)per(sI+tJ)=∑l(nl)l!sn-ltl=∑ln!(n-l)!sn-ltl.
Reversing the order of summation yields the result stated.Corollary 2.7.
For varyingn, one will explicitly denote pn(s,t)=per(sIn+tJn), then, with            p0(s,t)=1,
(2.23)∑n=0∞znn!pn(s,t)=esz1-tz.The Corollary exhibits the operational formula(2.24)pn(s,t)=11-tDssn,
where Ds=d/ds. By inspection, this agrees with (2.19) as well.Observe that (2.19) can be rewritten as (2.25)per(sI+tJ)=∫0∞(s+ty)ne-ydy,
that is, these are “moment polynomials” for the exponential distribution with an additional scale parameter.We proceed to examine these moment polynomials in detail.


## 3. Exponential Polynomials

For the exponential distribution, with densitye-y on (0,∞), the moment polynomials are defined as (3.1)hn(x)=∫0∞(x+y)ne-ydy.
The exponential embeds naturally into the family of weights of the form xme-x on (0,∞) as for generalized Laguerre polynomials. We define correspondingly(3.2)hn,m(x,t)=∫0∞(x+ty)n(ty)me-ydy,
for nonnegative integers n,m, introducing a factor of ym and a scale factor of t. We refer to these as exponential moment polynomials.Proposition 3.1.
Observe the following properties of the exponential moment polynomials.(1)
The generating function(3.3)1tmm!∑n=0∞znn!hn,m(x,t)=ezx(1-tz)1+m,
for |tz|<1.(2)
The operational formula(3.4)1tmm!hn,m(x,t)=(I-tD)-(m+1)xn,
where I is the identity operator and D=d/dx. (3)
The explicit form(3.5)hn,m(x,t)=∑j=0n(nj)(m+j)!xn-jtm+j.Proof.
For the first formula, multiply the integral byzn/n! and sum to get
(3.6)∫0∞ymezx+zty-ydy=ezx∫0∞yme-y(1-tz)dy,
which yields the stated result.
For the second, write(3.7)tmm!(I-tD)-(m+1)xn=tm∫0∞yme-(I-tD)yxndy=∫0∞(ty)me-y(x+ty)ndy,
using the shift formula eaDf(x)=f(x+a).
For the third, expand(x+ty)n by the binomial theorem and integrate.A variation we will encounter in the following is(3.8)hn-m,m(x,t)=∑j=0n-m(n-mj)(m+j)!xn-m-jtm+j(3.9)=∑j=mn(n-mj-m)j!xn-jtj(3.10)=∑j=mn(n-mn-j)j!xn-jtj(3.11)=∑j=0n-m(n-mj)(n-j)!xjtn-j,
replacing the index j←j-m for (3.9) and reversing the order of summation for the last line. And for future reference, consider the integral formula(3.12)hn-m,m(x,t)=∫0∞(x+ty)n-m(ty)me-ydy.


### 3.1. Hypergeometric Form

Generalized hypergeometric functions provide expressions for the exponential moment polynomials that are often convenient. In the present context, we will use2F0 functions, defined by (3.13)2F0(a,b—a,b—|xa,b—)=∑j=0∞(a)j(b)jj!xj,
where (a)j=Γ(a+j)/Γ(a) is the usual Pochhammer symbol. In particular, if a, for example, is a negative integer, the series reduces to a polynomial. Rearranging factors in the expressions for hn,m, via (3) in Proposition 3.1, and hn-m,m, (3.8), we can formulate these as 2F0 hypergeometric functions.Proposition 3.2.
One has the following expressions for exponential moment polynomials:(3.14)hn,m(x,t)=xntmm!2F0(a,b—-n,1+m—|-txa,b—),hn-m,m(x,t)=xn-mtmm!2F0(a,b—m-n,1+m—|-txa,b—).


## 3.1. Hypergeometric Form

Generalized hypergeometric functions provide expressions for the exponential moment polynomials that are often convenient. In the present context, we will use2F0 functions, defined by (3.13)2F0(a,b—a,b—|xa,b—)=∑j=0∞(a)j(b)jj!xj,
where (a)j=Γ(a+j)/Γ(a) is the usual Pochhammer symbol. In particular, if a, for example, is a negative integer, the series reduces to a polynomial. Rearranging factors in the expressions for hn,m, via (3) in Proposition 3.1, and hn-m,m, (3.8), we can formulate these as 2F0 hypergeometric functions.Proposition 3.2.
One has the following expressions for exponential moment polynomials:(3.14)hn,m(x,t)=xntmm!2F0(a,b—-n,1+m—|-txa,b—),hn-m,m(x,t)=xn-mtmm!2F0(a,b—m-n,1+m—|-txa,b—).


## 4. Zeon Powers ofsI+tJ

We want to calculate(sI+tJ)∨ℓ, that is, the (nℓ)×(nℓ) matrix with rows and columns labelled by ℓ-subsets I,J⊂{1,…,n} with the IJ entry equal to the permanent of the corresponding submatrix of sI+tJ. This is equivalent to the induced action of the original matrix sI+tJ on the ℓth zeon space 𝒱∨ℓ.Theorem 4.1.
Theℓth zeon power of sI+tJ is given by
(4.1)(sI+tJ)∨l=∑k∑j=kl(l-kl-j)j!sl-jtjJSknl=∑khl-k,k(s,t)JSknl,
where the h’s are exponential moment polynomials.Proof.
ChooseI and J with |I|=|J|=ℓ. By Theorem 2.1, we have, using the fact that all of the entries of J∨j are equal to j!,
(4.2)((sI+tJ)∨l)IJ=∑0≤j≤lsl-jtj∑A⊂I∩J|A|=l-j(J∨j)I∖A,J∖A=∑0≤j≤lsl-jtj∑A⊂I∩J|A|=l-jj!.
Now, if distJS(I,J)=k, then |I∩J|=ℓ-k, and there are (ℓ-kℓ-j) subsets A of I∩J satisfying the conditions of the sum. Hence the result.Note that the specializationℓ=n, k=0, recovers (2.19).We can write the above expansion using the hypergeometric form of the exponential moment polynomials, Proposition3.2, (4.3)(sI+tJ)∨l=∑ksl-ktkk!2F0(a,b—k-l,1+k—|-tsa,b—)JSknl.


### 4.1. Spectrum of the Johnson Matrices

Recall, for example, [2, page 220], that the spectrum of the Johnson matrices for given n and ℓ is the set of numbers(4.4)Λknl(α)=∑i(l-αi)(n-l-α+ii)(l-ik-i)(-1)k-i,
where the eigenvalue for given α has multiplicity (nα)-(nα-1).Forℓ-sets, the Johnson distance takes values from 0 to min(ℓ,n-ℓ), with α taking values from that same range.


### 4.2. The Spectrum of(sI+tJ)∨ℓ

Recall that as the Johnson matrices are symmetric and generate a commutative algebra, they are simultaneously diagonalizable by an orthogonal transformation of the underlying vector space. Diagonalizing the equation in Theorem4.1, we see that the spectrum of (sI+tJ)∨ℓ is given by (4.5)∑khl-k,k(s,t)Λknl(α).Proposition 4.2.
The spectrum of(sI+tJ)∨ℓ is given by
(4.6)sαtn-l-α(n-l-α)!hl-α,n-l-α(s,t)=∑isl-iti(l-αi)(n-l-α+ii)i!,
for 0≤α≤min(ℓ,n-ℓ), with respective multiplicities (nα)-(nα-1).Proof.
In the sum overi in (4.4), only the last two factors involve k. We have
(4.7)∑khl-k,k(s,t)(-1)k-i(l-ik-i)=∑k∫0∞(s+ty)l-k(ty)k(-1)k-i(l-ik-i)e-ydysettingk=i+m=∑m∫0∞(s+ty)l-i-m(ty)i+m(-1)m(l-im)e-ydy=∫0∞(s+ty-ty)l-i(ty)ie-ydy=sl-itii!,
using the binomial theorem to sum out m. Filling in the additional factors yields
(4.8)∑khl-k,k(s,t)Λknl(α)=∑isl-itii!(l-αi)(n-l-α+ii),
Taking out a denominator factor of (n-ℓ-α)! and multiplying by s-αtn-ℓ-α gives
(4.9)∑isl-α-itn-l-α+i(l-αi)(n-l-α+i)!,
which is precisely hℓ-α,n-ℓ-α as in the third statement of Proposition 3.1.As in Proposition3.2, we can express the eigenvalues as follows.Corollary 4.3.
The spectrum of(sI+tJ)∨ℓ consists of the eigenvalues
(4.10)sl2F0(a,b—α-l,1+n-l-α—|-tsa,b—),
for 0≤α≤min(ℓ,n-ℓ), with corresponding multiplicities as indicated above.


### 4.3. Row Sums and Trace Identity

For the row sums, we know that the all-ones vector is a common eigenvector of the Johnson basis corresponding toα=0. These are the valencies Λk(0). For the Johnson scheme, we have (4.11)Λknl(0)=(lk)(n-lk).
for example, see [2, page 219], which can be checked directly from the formula for Λknℓ(α), (4.4), with α set to zero. Setting α=0 in Proposition 4.2 gives(4.12)1tn-l(n-l)!hl,n-l(s,t)=∑i(li)(n-l+ii)i!sl-iti,
for the row sums of (sI+tJ)∨ℓ.


#### 4.3.1. Trace Identity

Terms on the diagonal are the coefficient ofJS0nℓ, which is the identity matrix. So, the trace is (4.13)tr⁡(sI+tJ)∨l=(nl)hl,0(s,t)=(nl)∑k(lk)k!sl-ktk.
Cancelling factorials and reversing the order of summation on k yields the following  formula.(4.14)tr⁡(sI+tJ)∨l=n!(n-l)!∑0≤k≤lsktl-kk!.Now, Proposition4.2 gives the trace (4.15)tr⁡(sI+tJ)∨l=∑0≤α≤min⁡(l,n-l)[(nα)-(nα-1)]∑isl-iti(l-αi)(n-l-α+ii)i!.Proposition 4.4.
Equating the above expressions for the trace yields the identity(4.16)∑0≤α≤min⁡(l,n-l)[(nα)-(nα-1)]∑isl-iti(l-αi)(n-l-α+ii)i!=n!(n-l)!∑0≤j≤lsjtl-jj!.Example 4.5.
Forn=4, ℓ=2, we have
(4.17)[s2+2st+2t2st+2t2st+2t2st+2t2st+2t22t2st+2t2s2+2st+2t2st+2t2st+2t22t2st+2t2st+2t2st+2t2s2+2st+2t22t2st+2t2st+2t2st+2t2st+2t22t2s2+2st+2t2st+2t2st+2t2st+2t22t2st+2t2st+2t2s2+2st+2t2st+2t22t2st+2t2st+2t2st+2t2st+2t2s2+2st+2t2].
One can check that the entries are in agreement with Theorem 4.1. The trace is 6s2+12st+12t2. The spectrum is
(4.18)eigenvalues2+6st+12t2,withmultiplicity1,eigenvalues2+2st,withmultiplicity3,eigenvalues2,withmultiplicity2,
and the trace can be verified from these as well.Remark 4.6.
What is interesting is that these matrices have polynomial entries with all eigenvalues polynomials as well, and furthermore, the exact same set of polynomials produces the eigenvalues as well as the entries. Specializings and t to integers, a similar statement holds. All of these matrices will have integer entries with integer eigenvalues, all of which belong to closely related families of numbers. We will examine interesting cases of this phenomenon later on in this paper.


## 4.1. Spectrum of the Johnson Matrices

Recall, for example, [2, page 220], that the spectrum of the Johnson matrices for given n and ℓ is the set of numbers(4.4)Λknl(α)=∑i(l-αi)(n-l-α+ii)(l-ik-i)(-1)k-i,
where the eigenvalue for given α has multiplicity (nα)-(nα-1).Forℓ-sets, the Johnson distance takes values from 0 to min(ℓ,n-ℓ), with α taking values from that same range.


## 4.2. The Spectrum of(sI+tJ)∨ℓ

Recall that as the Johnson matrices are symmetric and generate a commutative algebra, they are simultaneously diagonalizable by an orthogonal transformation of the underlying vector space. Diagonalizing the equation in Theorem4.1, we see that the spectrum of (sI+tJ)∨ℓ is given by (4.5)∑khl-k,k(s,t)Λknl(α).Proposition 4.2.
The spectrum of(sI+tJ)∨ℓ is given by
(4.6)sαtn-l-α(n-l-α)!hl-α,n-l-α(s,t)=∑isl-iti(l-αi)(n-l-α+ii)i!,
for 0≤α≤min(ℓ,n-ℓ), with respective multiplicities (nα)-(nα-1).Proof.
In the sum overi in (4.4), only the last two factors involve k. We have
(4.7)∑khl-k,k(s,t)(-1)k-i(l-ik-i)=∑k∫0∞(s+ty)l-k(ty)k(-1)k-i(l-ik-i)e-ydysettingk=i+m=∑m∫0∞(s+ty)l-i-m(ty)i+m(-1)m(l-im)e-ydy=∫0∞(s+ty-ty)l-i(ty)ie-ydy=sl-itii!,
using the binomial theorem to sum out m. Filling in the additional factors yields
(4.8)∑khl-k,k(s,t)Λknl(α)=∑isl-itii!(l-αi)(n-l-α+ii),
Taking out a denominator factor of (n-ℓ-α)! and multiplying by s-αtn-ℓ-α gives
(4.9)∑isl-α-itn-l-α+i(l-αi)(n-l-α+i)!,
which is precisely hℓ-α,n-ℓ-α as in the third statement of Proposition 3.1.As in Proposition3.2, we can express the eigenvalues as follows.Corollary 4.3.
The spectrum of(sI+tJ)∨ℓ consists of the eigenvalues
(4.10)sl2F0(a,b—α-l,1+n-l-α—|-tsa,b—),
for 0≤α≤min(ℓ,n-ℓ), with corresponding multiplicities as indicated above.


## 4.3. Row Sums and Trace Identity

For the row sums, we know that the all-ones vector is a common eigenvector of the Johnson basis corresponding toα=0. These are the valencies Λk(0). For the Johnson scheme, we have (4.11)Λknl(0)=(lk)(n-lk).
for example, see [2, page 219], which can be checked directly from the formula for Λknℓ(α), (4.4), with α set to zero. Setting α=0 in Proposition 4.2 gives(4.12)1tn-l(n-l)!hl,n-l(s,t)=∑i(li)(n-l+ii)i!sl-iti,
for the row sums of (sI+tJ)∨ℓ.


### 4.3.1. Trace Identity

Terms on the diagonal are the coefficient ofJS0nℓ, which is the identity matrix. So, the trace is (4.13)tr⁡(sI+tJ)∨l=(nl)hl,0(s,t)=(nl)∑k(lk)k!sl-ktk.
Cancelling factorials and reversing the order of summation on k yields the following  formula.(4.14)tr⁡(sI+tJ)∨l=n!(n-l)!∑0≤k≤lsktl-kk!.Now, Proposition4.2 gives the trace (4.15)tr⁡(sI+tJ)∨l=∑0≤α≤min⁡(l,n-l)[(nα)-(nα-1)]∑isl-iti(l-αi)(n-l-α+ii)i!.Proposition 4.4.
Equating the above expressions for the trace yields the identity(4.16)∑0≤α≤min⁡(l,n-l)[(nα)-(nα-1)]∑isl-iti(l-αi)(n-l-α+ii)i!=n!(n-l)!∑0≤j≤lsjtl-jj!.Example 4.5.
Forn=4, ℓ=2, we have
(4.17)[s2+2st+2t2st+2t2st+2t2st+2t2st+2t22t2st+2t2s2+2st+2t2st+2t2st+2t22t2st+2t2st+2t2st+2t2s2+2st+2t22t2st+2t2st+2t2st+2t2st+2t22t2s2+2st+2t2st+2t2st+2t2st+2t22t2st+2t2st+2t2s2+2st+2t2st+2t22t2st+2t2st+2t2st+2t2st+2t2s2+2st+2t2].
One can check that the entries are in agreement with Theorem 4.1. The trace is 6s2+12st+12t2. The spectrum is
(4.18)eigenvalues2+6st+12t2,withmultiplicity1,eigenvalues2+2st,withmultiplicity3,eigenvalues2,withmultiplicity2,
and the trace can be verified from these as well.Remark 4.6.
What is interesting is that these matrices have polynomial entries with all eigenvalues polynomials as well, and furthermore, the exact same set of polynomials produces the eigenvalues as well as the entries. Specializings and t to integers, a similar statement holds. All of these matrices will have integer entries with integer eigenvalues, all of which belong to closely related families of numbers. We will examine interesting cases of this phenomenon later on in this paper.


## 4.3.1. Trace Identity

Terms on the diagonal are the coefficient ofJS0nℓ, which is the identity matrix. So, the trace is (4.13)tr⁡(sI+tJ)∨l=(nl)hl,0(s,t)=(nl)∑k(lk)k!sl-ktk.
Cancelling factorials and reversing the order of summation on k yields the following  formula.(4.14)tr⁡(sI+tJ)∨l=n!(n-l)!∑0≤k≤lsktl-kk!.Now, Proposition4.2 gives the trace (4.15)tr⁡(sI+tJ)∨l=∑0≤α≤min⁡(l,n-l)[(nα)-(nα-1)]∑isl-iti(l-αi)(n-l-α+ii)i!.Proposition 4.4.
Equating the above expressions for the trace yields the identity(4.16)∑0≤α≤min⁡(l,n-l)[(nα)-(nα-1)]∑isl-iti(l-αi)(n-l-α+ii)i!=n!(n-l)!∑0≤j≤lsjtl-jj!.Example 4.5.
Forn=4, ℓ=2, we have
(4.17)[s2+2st+2t2st+2t2st+2t2st+2t2st+2t22t2st+2t2s2+2st+2t2st+2t2st+2t22t2st+2t2st+2t2st+2t2s2+2st+2t22t2st+2t2st+2t2st+2t2st+2t22t2s2+2st+2t2st+2t2st+2t2st+2t22t2st+2t2st+2t2s2+2st+2t2st+2t22t2st+2t2st+2t2st+2t2st+2t2s2+2st+2t2].
One can check that the entries are in agreement with Theorem 4.1. The trace is 6s2+12st+12t2. The spectrum is
(4.18)eigenvalues2+6st+12t2,withmultiplicity1,eigenvalues2+2st,withmultiplicity3,eigenvalues2,withmultiplicity2,
and the trace can be verified from these as well.Remark 4.6.
What is interesting is that these matrices have polynomial entries with all eigenvalues polynomials as well, and furthermore, the exact same set of polynomials produces the eigenvalues as well as the entries. Specializings and t to integers, a similar statement holds. All of these matrices will have integer entries with integer eigenvalues, all of which belong to closely related families of numbers. We will examine interesting cases of this phenomenon later on in this paper.


## 5. Permanents fromsI+tJ

Here, we present a proof via recursion of the subpermanents ofsI+tJ, thereby recovering Theorem 4.1 from a different perspective.Remark 5.1.
For the remainder of this paper, we will work with ann×n matrix corresponding to an ℓ×ℓ submatrix of the above discussion. Here, we have blown up the submatrix to full size as the object of consideration.LetMn,ℓ denote the n×n matrix with n-ℓ entries equal to s+t on the main diagonal, and t’s elsewhere. Note that Mn,0=sI+tJ and Mn,n=tJ, where I and J are n×n. Define(5.1)Pn,l=per(Mn,l)
to be the permanent of Mn,ℓ.Forℓ=0, define P0,0=1, and, recalling (2.19),(5.2)Pn,0=per(sI+tJ)=∑j=0nn!j!sjtn-j=∑j=0nn!(n-j)!sn-jtj.
We have also Pn,n=per(tJ)=n!tn for J of order n×n. These agree at P0,0=1.Theorem 5.2.
Forn≥1, 1≤ℓ≤n, one has the recurrence
(5.3)Pn,l=Pn,l-1-sPn-1,l-1.Proof.
We have0≤ℓ≤n so n-(ℓ-1)=n-ℓ+1≥1, that is, the matrix Mn,ℓ-1 contains at least 1 entry on its main diagonal equal to s+t. Write the block form
(5.4)Mn,l-1=[s+tAATMn-1,l-1],
with A=[t,t,…,t] the 1×(n-1) row vector of all ts, and AT is its transpose. Now, compute the permanent of Mn,ℓ-1 expanding along the first row. We get
(5.5)Pn,l-1=per(Mn,l-1)=(s+t)per(Mn-1,l-1)+F(A,AT,Mn-1,l-1),
where F(A,AT,Mn-1,ℓ-1) is the contribution to Pn,ℓ-1 involving A. Now,
(5.6)tper(Mn-1,l-1)+F(A,AT,Mn-1,l-1)=per([tAATMn-1,l-1])=per([ATMn-1,l-1tA])=per([Mn-1,l-1ATAt])=Pn,l.
Thus, from (5.5),
(5.7)Pn,l-1=sper(Mn-1,l-1)+tper(Mn-1,l-1)+F(A,AT,Mn-1,l-1)=sPn-1,l-1+Pn,l,
and hence the result.We arrange the polynomialsPn,ℓ in a triangle, with the columns labelled by ℓ≥0 and rows by n≥0, starting with P0,0=1 at the top vertex(5.8)P0,0P1,0P1,1P2,0P2,1P2,2⋮⋱⋱Pn-1,0⋯Pn-1,n-2Pn-1,n-1Pn,0Pn,1⋯Pn,n-1Pn,n
The recurrence says that to get the n,ℓ entry, you combine elements in column ℓ-1 in rows n and n-1, forming an  L-shape. Thus, given the first column {Pn,0}n≥0, the table can be generated in full.Now, we check that these are indeed our exponential moment polynomials. Additionally, we derive an expression forPn,ℓ in terms of the initial sequence Pn,0. For clarity, we will explicitly denote the dependence of Pn,ℓ on (s,t).Theorem 5.3.
Forℓ≥0, one has (1)
the permanent of then×n matrix with n-ℓ entries on the diagonal equal to s+t and all other entries equal to t is(5.9)Pn,l(s,t)=hn-l,l(s,t)=∑j=ln(n-ln-j)j!sn-jtj,(2)
(5.10)Pn,l(s,t)=∑j=0l(lj)(-1)jsjPn-j,0(s,t),(3)
the complementary sum is(5.11)sn=∑j=0n(nl)(-1)lPn,l(s,t).Proof.
The initial sequencePn,0=hn,0 as noted in (5.2). We check that hn-ℓ,ℓ satisfies recurrence (5.3). Starting from the integral representation for hn-ℓ+1,ℓ-1, (3.2), we have
(5.12)hn-l+1,l-1=∫0∞(s+ty)n-l+1(ty)l-1e-ydy=∫0∞(s+ty)(s+ty)n-l(ty)l-1e-ydy=shn-l,l-1+hn-l,l,
as required, where we now identify hn-ℓ+1,ℓ-1=Pn,ℓ-1, hn-ℓ,ℓ-1=Pn-1,ℓ-1, and hn-ℓ,ℓ=Pn,ℓ. And (3.10) gives an explicit form for Pn,ℓ.
For (2), starting with the integral representation forPn,0=hn,0, we get
(5.13)∑j=0l(lj)(-1)jsj∫0∞(s+ty)n-je-ydy=∑j=0l(lj)(-1)jsj∫0∞(s+ty)n-l(s+ty)l-je-ydy=∫0∞(s+ty)n-l(s+ty-s)le-ydy=hn-l,l,
as required. The proof for (3) is similar, using (3.12),
(5.14)Pn,l=hn-l,l=∫0∞(s+ty)n-l(ty)le-ydy,
and the binomial theorem for the sum.


### 5.1.(sI+tJ)∨ℓ Revisited

Now, we have an alternative proof of Theorem4.1.Lemma 5.4.
LetI and J be ℓ-subsets of [n] with distJS(I,J)=k, then
(5.15)per(sI+tJ)IJ=Pl,k(s,t).Proof.
Now,|I∩J|=ℓ-k, so the submatrix (sI+tJ)IJ is permutationally equivalent to the ℓ×ℓ matrix with ℓ-k entries s+t on its main diagonal and ts elsewhere, that is, to the matrix Mℓ,k. Hence, by definition of Pℓ,k(s,t), (5.1), we have the result.Thus, the expansion in the Johnson basis is(5.16)(sI+tJ)∨l=∑khl-k,k(s,t)JSknl.Proof.
Let  I and  J beℓ-subsets of [n] with Johnson distance k. By definition, the IJ entry of the LHS of (5.16) equals the permanent of the submatrix from rows I and columns J, per(sI+tJ)IJ=Pℓ,k(s,t)=hℓ-k,k(s,t), by Lemma 5.4 and Theorem 5.3(1). Now, on the RHS of (5.16), if distJS(I,J)=k, the only nonzero contribution comes from the JSknℓ term. This yields hℓ-k,k(s,t)×1=hℓ-k,k(s,t) as required.


### 5.2. Elementary Subgraphs and Permanents

There is an approach to permanents ofsI+tJ via elementary subgraphs, based on that of Biggs [3] for determinants.Anelementary subgraph (see [3, page 44]) of a graph G is a spanning subgraph of G all of whose components are 0, 1, or 2 regular, that is, all of whose components are isolated vertices, isolated edges, or cycles of length j≥3.LetKn(ℓ) be a copy of the complete graph Kn with vertex set [n] in which the first n-ℓ vertices [n-ℓ]={1,2,…,n-ℓ} are distinguished. We may now consider the matrix Mn,ℓ as the weighted adjacency matrix of Kn(ℓ) in which the weights of the distinguished vertices are s+t, with all undistinguished vertices and all edges assigned a weight of t.LetE be an elementary subgraph of Kn(ℓ), then we describe E as having d(E) distinguished isolated vertices and c(E) cycles. The weight of E, wt(E), is defined as(5.17)wt(E)=(s+t)d(E)tn-d(E),
a homogeneous polynomial of degree n.This leads to an interpretation/derivation ofPn,ℓ(s,t) as the permanent per(Mn,ℓ).Theorem 5.5.
One has the expansion in elementary subgraphs(5.18)Pn,l(s,t)=∑E2c(E)wt(E).Proof.
Assign weights to the components ofE as follows:
each distinguished isolated vertex will have weights+t;
each undistinguished isolated vertex will have weightt;
each isolated edge will have weightt2;
and eachj-cycle, j≥3, will have weight tj.
To obtainwt(E) in agreement with (5.17), we form the product of these weights over all components in E. The proof then follows along the lines of Proposition 7.2 of [3, page 44], slightly modified to incorporate isolated vertices and with determinant, “det,” replaced by permanent, “per,” ignoring the minus signs. Effectively, each term in the permanent expansion thus corresponds to a weighted elementary subgraph E of the weighted Kn(ℓ).See Figure2 for an example with n=3.Figure 2
M3,ℓ, K3(ℓ), P3,ℓ, and the 5 weighted elementary subgraphs of K3(ℓ) for ℓ=0,1,2,3. Distinguished vertices are shown in bold.


### 5.3. Associated Polynomials and Some Asymptotics

Thinking ofs and t as parameters, we define the associated polynomials(5.19)Qn(x)=∑l=0n(nl)xlPn,l.
As in the proof of (3) above, using the integral formula (3.12), we have(5.20)Qn(x)=∫0∞(s+ty+xty)ne-ydy=∑j(nj)sj(1+x)n-jtn-j(n-j)!=n!∑jsj(1+x)n-jtn-jj!.
Comparing with (5.2), we have the following.Proposition 5.6.
Consider(5.21)Qn(x)=∑l=0n(nl)xlPn,l(s,t)=Pn,0(s,t+xt).And one has the following.Proposition 5.7.
Asn→∞, for x≠-1,
(5.22)Qn(x)~tn(1+x)nn!es/(t+tx),
with the special cases
(5.23)Qn(-1)=sn,Qn(0)=Pn,0~tnn!es/t,Qn(1)=∑l(nl)Pn,l~(2t)nn!es/(2t).Proof.
From (5.20),
(5.24)Qn(x)=n!∑jsj(1+x)n-jtn-jj!=tn(1+x)nn!∑j=0n1j!(s/t1+x)j,
from which the result follows.


## 5.1.(sI+tJ)∨ℓ Revisited

Now, we have an alternative proof of Theorem4.1.Lemma 5.4.
LetI and J be ℓ-subsets of [n] with distJS(I,J)=k, then
(5.15)per(sI+tJ)IJ=Pl,k(s,t).Proof.
Now,|I∩J|=ℓ-k, so the submatrix (sI+tJ)IJ is permutationally equivalent to the ℓ×ℓ matrix with ℓ-k entries s+t on its main diagonal and ts elsewhere, that is, to the matrix Mℓ,k. Hence, by definition of Pℓ,k(s,t), (5.1), we have the result.Thus, the expansion in the Johnson basis is(5.16)(sI+tJ)∨l=∑khl-k,k(s,t)JSknl.Proof.
Let  I and  J beℓ-subsets of [n] with Johnson distance k. By definition, the IJ entry of the LHS of (5.16) equals the permanent of the submatrix from rows I and columns J, per(sI+tJ)IJ=Pℓ,k(s,t)=hℓ-k,k(s,t), by Lemma 5.4 and Theorem 5.3(1). Now, on the RHS of (5.16), if distJS(I,J)=k, the only nonzero contribution comes from the JSknℓ term. This yields hℓ-k,k(s,t)×1=hℓ-k,k(s,t) as required.


## 5.2. Elementary Subgraphs and Permanents

There is an approach to permanents ofsI+tJ via elementary subgraphs, based on that of Biggs [3] for determinants.Anelementary subgraph (see [3, page 44]) of a graph G is a spanning subgraph of G all of whose components are 0, 1, or 2 regular, that is, all of whose components are isolated vertices, isolated edges, or cycles of length j≥3.LetKn(ℓ) be a copy of the complete graph Kn with vertex set [n] in which the first n-ℓ vertices [n-ℓ]={1,2,…,n-ℓ} are distinguished. We may now consider the matrix Mn,ℓ as the weighted adjacency matrix of Kn(ℓ) in which the weights of the distinguished vertices are s+t, with all undistinguished vertices and all edges assigned a weight of t.LetE be an elementary subgraph of Kn(ℓ), then we describe E as having d(E) distinguished isolated vertices and c(E) cycles. The weight of E, wt(E), is defined as(5.17)wt(E)=(s+t)d(E)tn-d(E),
a homogeneous polynomial of degree n.This leads to an interpretation/derivation ofPn,ℓ(s,t) as the permanent per(Mn,ℓ).Theorem 5.5.
One has the expansion in elementary subgraphs(5.18)Pn,l(s,t)=∑E2c(E)wt(E).Proof.
Assign weights to the components ofE as follows:
each distinguished isolated vertex will have weights+t;
each undistinguished isolated vertex will have weightt;
each isolated edge will have weightt2;
and eachj-cycle, j≥3, will have weight tj.
To obtainwt(E) in agreement with (5.17), we form the product of these weights over all components in E. The proof then follows along the lines of Proposition 7.2 of [3, page 44], slightly modified to incorporate isolated vertices and with determinant, “det,” replaced by permanent, “per,” ignoring the minus signs. Effectively, each term in the permanent expansion thus corresponds to a weighted elementary subgraph E of the weighted Kn(ℓ).See Figure2 for an example with n=3.Figure 2
M3,ℓ, K3(ℓ), P3,ℓ, and the 5 weighted elementary subgraphs of K3(ℓ) for ℓ=0,1,2,3. Distinguished vertices are shown in bold.


## 5.3. Associated Polynomials and Some Asymptotics

Thinking ofs and t as parameters, we define the associated polynomials(5.19)Qn(x)=∑l=0n(nl)xlPn,l.
As in the proof of (3) above, using the integral formula (3.12), we have(5.20)Qn(x)=∫0∞(s+ty+xty)ne-ydy=∑j(nj)sj(1+x)n-jtn-j(n-j)!=n!∑jsj(1+x)n-jtn-jj!.
Comparing with (5.2), we have the following.Proposition 5.6.
Consider(5.21)Qn(x)=∑l=0n(nl)xlPn,l(s,t)=Pn,0(s,t+xt).And one has the following.Proposition 5.7.
Asn→∞, for x≠-1,
(5.22)Qn(x)~tn(1+x)nn!es/(t+tx),
with the special cases
(5.23)Qn(-1)=sn,Qn(0)=Pn,0~tnn!es/t,Qn(1)=∑l(nl)Pn,l~(2t)nn!es/(2t).Proof.
From (5.20),
(5.24)Qn(x)=n!∑jsj(1+x)n-jtn-jj!=tn(1+x)nn!∑j=0n1j!(s/t1+x)j,
from which the result follows.


## 6. Generalized Derangement Numbers

The formula (2.19) is suggestive of the derangement numbers (see, e.g., [4, page 180]), (6.1)dn=n!∑j=0n(-1)jj!.
This leads to the following.Definition 6.1.
A family of numbers, depending onn and ℓ, arising as the values of Pn,ℓ(s,t) when s and t are assigned fixed integer values, are called generalized derangement numbers.We have seen that the assignments=-1,t=1 produces the usual derangement numbers when ℓ=0. In this section, we will examine in detail the cases s=-1,t=1, generalized derangements, and s=t=1, generalized arrangements.Remark 6.2.
Topics related to this material are discussed in Riordan [5]. The paper [6] is of related interest as well.


### 6.1. Generalized Derangements of[n]

To start, define(6.2)Dn,l=Pn,l(-1,1).
Equation (5.9) and Proposition 3.2 give(6.3)Dn,l=∑j=ln(-1)n-j(n-ln-j)j!=(-1)n-ll!2F0(a,b—l-n,1+l—|1a,b—).
Equation (5.2) reads as (6.4)per(J-I)=Dn,0=dn,
the number derangements of [n]. So we have a combinatorial interpretation of Dn,0.


#### 6.1.1. Combinatorial Interpretation ofDn,ℓ

We now give a combinatorial interpretation ofDn,ℓ for ℓ≥1.Whenℓ≥1, recurrence (5.3) for Pn,ℓ(-1,1) gives(6.5)Dn,l=Dn,l-1+Dn-1,l-1.
We say that a subset I of [n] is deranged by a permutation if no point of I is fixed by the permutation.Proposition 6.3.
Dn,0=dn, the number of derangements of [n]. In general, for ℓ≥0, Dn,ℓ is the number of permutations of [n] in which the set {1,2,…,n-ℓ} is deranged, with no restrictions on the ℓ-set {n-ℓ+1,…,n}.Proof.
Forℓ≥0, let Dn,ℓ* denote the set of permutations in the statement of the proposition. Let En,ℓ=|Dn,ℓ*|. We claim that En,ℓ=Dn,ℓ.
The caseℓ=0 is immediate. We show that En,ℓ satisfies recurrence (6.5).
Now, letℓ>0. Consider a permutation in Dn,ℓ*. The point n is either (1) deranged, or (2) not deranged (i.e., fixed). (1)
Ifn is deranged, then the (n-ℓ+1)-set {1,2,…,n-ℓ,n} is deranged. By switching n↔n-ℓ+1 in all permutations of Dn,ℓ*, we obtain a permutation in Dn,ℓ-1*. Conversely, given any permutation of Dn,ℓ-1*, we switch n↔n-ℓ+1 to obtain a permutation in Dn,ℓ* where n is deranged. Hence, the number of permutations in Dn,ℓ* with n deranged equals En,ℓ-1.(2)
Here,n is fixed, so if we remove n from any permutation in Dn,ℓ* we obtain a permutation in Dn-1,ℓ-1*. Conversely, given a permutation in Dn-1,ℓ-1*, we may include n as a fixed point to obtain a permutation in Dn,ℓ* with n fixed. Hence, the number of permutations in Dn,ℓ* with n fixed equals En-1,ℓ-1.Combining the above two paragraphs shows that En,ℓ satisfies recurrence (6.5).And a quick check,(6.6)Dn,n=n!,
there being no restrictions at all in the combinatorial interpretation, in agreement with (6.3) for ℓ=n.Example 6.4.
Whenn=3, we have d3=D3,0=2 corresponding to the 2 permutations of [1] in which {1,2,3} is moved: 231,312.
Then,D3,1=3 corresponding to the 3 permutations of [1] in which {1,2} is moved: 213,231,312.
Then,D3,2=4 corresponding to the 4 permutations of [1] in which {1} is moved: 213,231,312,321.
Finally,D3,3=3!=6 corresponding to the 3 permutations of [1] in which ∅ is moved: 123,132,213,231,312,321.Reversing the order of summation in (6.3) gives an alternative expression(6.7)Dn,l=∑j=0n-l(-1)j(n-lj)(n-j)!.Remark 6.5.
Formulation (6.7) may be proved directly by inclusion-exclusion on permutations fixing given points.Example 6.6.
Consider(6.8)D5,2=∑j=03(-1)j(3j)(5-j)!=(30)5!-(31)4!+(32)3!-(33)2!=120-72+18-2=64.Now, from (2) of Theorem5.3, s=-1, and t=1, we have(6.9)Dn,l=∑j=0l(lj)dn-j.
Here is a combinatorial explanation. To obtain a permutation in Dn,ℓ*, we first choose j points from {n-ℓ+1,…,n} to be fixed. Then, every derangement of the remaining (n-j) points will produce a permutation in Dn,ℓ*, and there are dn-j of such derangements.Example 6.7.
Consider(6.10)D5,2=∑j=02(2j)d5-j=(20)d5+(21)d4+(22)d3=1×44+2×9+1×2=44+18+2=64.


#### 6.1.2. Permanents fromJ-I

Theorem4.1 specializes to (6.11)(J-I)∨l=∑k=0min⁡(l,n-l)Dl,kJSknl.
This can be written using the hypergeometric form (6.12)(J-I)∨l=∑k=0min⁡(l,n-l)(-1)l-kk!2F0(a,b—k-l,1+k—|1a,b—)JSknl,
with spectrum (6.13)eigenvalue(-1)l2F0(a,b—α-l,-α+n-l+1—|1a,b—),occurringwithmultiplicity(nα)-(nα-1),
by Corollary 4.3 and Proposition 4.2.The entries of(J-I)∨ℓ are from the set of numbers Dn,ℓ. For the spectrum, start with α=0. From (6.3), we have (6.14)(-1)l2F0(a,b—-l,n-l+1—|1a,b—)=1(n-l)!Dn,n-l.
As α increases, we see that the spectrum consists of the numbers (6.15)(-1)α(n-l-α)!Dn-2α,n-l-α.
Think of moving in the derangement triangle, as in the appendix, starting from position n,n-ℓ, rescaling the values by the factorial of the column at each step, then the eigenvalues are found by successive knight's moves, up 2 rows and one column to the left, with alternating signs.Example 6.8.
Forn=5, ℓ=3, we have
(6.16)(J-I)∨3=[2333343344323343343433243343343342333443343323434343333244333343442333343434323343344333234443333332],
with characteristic polynomial
(6.17)λ5(λ-32)(λ+3)4.Remark 6.9.
Except forℓ=2, the coefficients in the expansion of (J-I)∨ℓ in the Johnson basis will be distinct. Thus, the Johnson basis itself can be read off directly from (J-I)∨ℓ. In this sense, the centralizer algebra of the action of the symmetric group on ℓ-sets is determined by knowledge of the action of just J-I on ℓ-sets.


### 6.2. Generalized Arrangements of[n]

Given[n], 0≤j≤n, a j-arrangement of [n] is a permutation of a j-subset of [n]. The number of j-arrangements of [n] is (6.18)A(n,j)=n!(n-j)!.
Note that there is a single 0-arrangement of [n], from the empty set.DefineAn,ℓ=Pn,ℓ(1,1). So, similar to the case for derangements, (5.9) gives(6.19)An,l=∑j=ln(n-ln-j)j!=l!2F0(a,b—l-n,1+l—|-1a,b—).
Now, define an=An,0, so (6.20)an=per(I+J)=∑j=0nn!(n-j)!=∑j=0nA(n,j)
is thetotal number of j-arrangements of [n] for j=0,1,…,n. Thus, we have a combinatorial interpretation of An,0.


#### 6.2.1. Combinatorial Interpretation ofAn,ℓ

We now give a combinatorial interpretation ofAn,ℓ for ℓ≥1.Whenℓ≥1, recurrence (5.3) for Pn,ℓ(1,1) gives(6.21)An,l=An,l-1-An-1,l-1.Proposition 6.10.
An,0=an, the total number of arrangements of [n]. In general, for ℓ≥0, An,ℓ is the number of arrangements of [n]  which contain {1,2,…,ℓ}.Proof.
Forℓ≥0, let An,ℓ* denote the set of arrangements of [n] which contain [ℓ]. With [0]=∅, we note that An,0* is the set of all arrangements. Let Bn,ℓ=|An,ℓ*|. We claim that Bn,ℓ=An,ℓ.
The initial values withℓ=0 are immediate. We show that Bn,ℓ satisfies recurrence (6.21).
ConsiderAn,ℓ-1*. Let A∈An,ℓ-1*, so A is an arrangement of [n] containing [ℓ-1]. If ℓ=1, then A∈An,0* is any arrangement. Now, either ℓ∈A or ℓ∉A.
Ifℓ∈A, then A∈An,ℓ*, and so the number of arrangements in An,ℓ-1* which contain ℓ equals Bn,ℓ.
Ifℓ∉A, then by subtracting 1 from all parts of A which are ≥ℓ+1, we obtain an arrangement of [n-1] which contains [ℓ-1], that is, an arrangement in An-1,ℓ-1*. Conversely, given an arrangement in An-1,ℓ-1*, adding 1 to all parts ≥ℓ yields an arrangement in An,ℓ-1* which does not contain ℓ. Hence, the number of arrangements in An,ℓ-1* which do not contain ℓ equals Bn-1,ℓ-1.
We conclude thatBn,ℓ-1=Bn,ℓ+Bn-1,ℓ-1; hence, This is the result.Example 6.11.
Whenn=3, we have a3=A3,0=16 corresponding to the 16 arrangements of [1]: [],1,2,3,12,21,13,31,23,32,123,132,213,231,312,321.
Then,A3,1=11 corresponding to the 11 arrangements of [1] which contain {1}: 1,12,21,13,31,123,132,213,231,312,321.
Then,A3,2=8 corresponding to the 8 arrangements of [1] which contain {1,2}: 12,21,123,132,213,231,312,321.
Finally,A3,3=3!=6 corresponding to the 6 arrangements of [1] which contain {1,2,3}: 123,132,213,231,312,321.Rearranging the factors in (5.9), we have (6.22)Pn,l(s,t)=∑j=lnA(j,l)A(n-l,j-l)sn-jtj,
With s=t=1, this gives(6.23)An,l=∑j=lnA(j,l)A(n-l,j-l).
Here is a combinatorial explanation of (6.23).For anyj≥ℓ, to obtain a j-arrangement A of [n] containing [ℓ], we may place the ℓ points of {1,2,…,ℓ} into these j positions in A(j,ℓ) ways. Then, the remaining (j-ℓ) positions in A can be filled in by a (j-ℓ)-arrangement of the unused (n-ℓ) points in A(n-ℓ,j-ℓ) ways.Example 6.12.
Consider(6.24)A5,2=∑j=25A(j,2)A(3,j-2)=A(2,2)A(3,0)+A(3,2)A(3,1)+A(4,2)A(3,2)+A(5,2)A(3,3)=2×1+6×3+12×6+20×6=2+18+72+120=212.
Finally, from (2) of Theorem 5.3, s=1, and t=1, we have
(6.25)An,l=∑j=0l(-1)j(lj)an-j.Example 6.13.
Consider(6.26)A5,2=∑j=02(-1)j(2j)a5-j=(20)a5-(21)a4+(22)a3=1×326-2×65+1×16=326-130+16=212.


#### 6.2.2. Permanents fromI+J

Theorem4.1 specializes to (6.27)(I+J)∨l=∑k=0min⁡(l,n-l)Al,kJSknl.
This can be written using the hypergeometric form (6.28)(I+J)∨l=∑k=0min⁡(l,n-l)k!2F0(a,b—k-l,1+k—|-1a,b—)JSknl,
with spectrum (6.29)eigenvalue2F0(a,b—α-l,-α+n-l+1—|-1a,b—),occurringwithmultiplicity(nα)-(nα-1),
by Corollary 4.3 and Proposition 4.2.Example 6.14.
Forn=5, ℓ=3, we have
(6.30)(I+J)∨3=[16111111118111188111611118111181181111168111181111811118161111118811118111116118118118111111111688111111118118816111111118118118111611118111188111111161188811111111111116],
with characteristic polynomial
(6.31)(λ-106)(λ-11)4(λ-2)5.
As for the case of derangements, the Johnson basis can be read off directly from the matrix (I+J)∨ℓ.


## 6.1. Generalized Derangements of[n]

To start, define(6.2)Dn,l=Pn,l(-1,1).
Equation (5.9) and Proposition 3.2 give(6.3)Dn,l=∑j=ln(-1)n-j(n-ln-j)j!=(-1)n-ll!2F0(a,b—l-n,1+l—|1a,b—).
Equation (5.2) reads as (6.4)per(J-I)=Dn,0=dn,
the number derangements of [n]. So we have a combinatorial interpretation of Dn,0.


### 6.1.1. Combinatorial Interpretation ofDn,ℓ

We now give a combinatorial interpretation ofDn,ℓ for ℓ≥1.Whenℓ≥1, recurrence (5.3) for Pn,ℓ(-1,1) gives(6.5)Dn,l=Dn,l-1+Dn-1,l-1.
We say that a subset I of [n] is deranged by a permutation if no point of I is fixed by the permutation.Proposition 6.3.
Dn,0=dn, the number of derangements of [n]. In general, for ℓ≥0, Dn,ℓ is the number of permutations of [n] in which the set {1,2,…,n-ℓ} is deranged, with no restrictions on the ℓ-set {n-ℓ+1,…,n}.Proof.
Forℓ≥0, let Dn,ℓ* denote the set of permutations in the statement of the proposition. Let En,ℓ=|Dn,ℓ*|. We claim that En,ℓ=Dn,ℓ.
The caseℓ=0 is immediate. We show that En,ℓ satisfies recurrence (6.5).
Now, letℓ>0. Consider a permutation in Dn,ℓ*. The point n is either (1) deranged, or (2) not deranged (i.e., fixed). (1)
Ifn is deranged, then the (n-ℓ+1)-set {1,2,…,n-ℓ,n} is deranged. By switching n↔n-ℓ+1 in all permutations of Dn,ℓ*, we obtain a permutation in Dn,ℓ-1*. Conversely, given any permutation of Dn,ℓ-1*, we switch n↔n-ℓ+1 to obtain a permutation in Dn,ℓ* where n is deranged. Hence, the number of permutations in Dn,ℓ* with n deranged equals En,ℓ-1.(2)
Here,n is fixed, so if we remove n from any permutation in Dn,ℓ* we obtain a permutation in Dn-1,ℓ-1*. Conversely, given a permutation in Dn-1,ℓ-1*, we may include n as a fixed point to obtain a permutation in Dn,ℓ* with n fixed. Hence, the number of permutations in Dn,ℓ* with n fixed equals En-1,ℓ-1.Combining the above two paragraphs shows that En,ℓ satisfies recurrence (6.5).And a quick check,(6.6)Dn,n=n!,
there being no restrictions at all in the combinatorial interpretation, in agreement with (6.3) for ℓ=n.Example 6.4.
Whenn=3, we have d3=D3,0=2 corresponding to the 2 permutations of [1] in which {1,2,3} is moved: 231,312.
Then,D3,1=3 corresponding to the 3 permutations of [1] in which {1,2} is moved: 213,231,312.
Then,D3,2=4 corresponding to the 4 permutations of [1] in which {1} is moved: 213,231,312,321.
Finally,D3,3=3!=6 corresponding to the 3 permutations of [1] in which ∅ is moved: 123,132,213,231,312,321.Reversing the order of summation in (6.3) gives an alternative expression(6.7)Dn,l=∑j=0n-l(-1)j(n-lj)(n-j)!.Remark 6.5.
Formulation (6.7) may be proved directly by inclusion-exclusion on permutations fixing given points.Example 6.6.
Consider(6.8)D5,2=∑j=03(-1)j(3j)(5-j)!=(30)5!-(31)4!+(32)3!-(33)2!=120-72+18-2=64.Now, from (2) of Theorem5.3, s=-1, and t=1, we have(6.9)Dn,l=∑j=0l(lj)dn-j.
Here is a combinatorial explanation. To obtain a permutation in Dn,ℓ*, we first choose j points from {n-ℓ+1,…,n} to be fixed. Then, every derangement of the remaining (n-j) points will produce a permutation in Dn,ℓ*, and there are dn-j of such derangements.Example 6.7.
Consider(6.10)D5,2=∑j=02(2j)d5-j=(20)d5+(21)d4+(22)d3=1×44+2×9+1×2=44+18+2=64.


### 6.1.2. Permanents fromJ-I

Theorem4.1 specializes to (6.11)(J-I)∨l=∑k=0min⁡(l,n-l)Dl,kJSknl.
This can be written using the hypergeometric form (6.12)(J-I)∨l=∑k=0min⁡(l,n-l)(-1)l-kk!2F0(a,b—k-l,1+k—|1a,b—)JSknl,
with spectrum (6.13)eigenvalue(-1)l2F0(a,b—α-l,-α+n-l+1—|1a,b—),occurringwithmultiplicity(nα)-(nα-1),
by Corollary 4.3 and Proposition 4.2.The entries of(J-I)∨ℓ are from the set of numbers Dn,ℓ. For the spectrum, start with α=0. From (6.3), we have (6.14)(-1)l2F0(a,b—-l,n-l+1—|1a,b—)=1(n-l)!Dn,n-l.
As α increases, we see that the spectrum consists of the numbers (6.15)(-1)α(n-l-α)!Dn-2α,n-l-α.
Think of moving in the derangement triangle, as in the appendix, starting from position n,n-ℓ, rescaling the values by the factorial of the column at each step, then the eigenvalues are found by successive knight's moves, up 2 rows and one column to the left, with alternating signs.Example 6.8.
Forn=5, ℓ=3, we have
(6.16)(J-I)∨3=[2333343344323343343433243343343342333443343323434343333244333343442333343434323343344333234443333332],
with characteristic polynomial
(6.17)λ5(λ-32)(λ+3)4.Remark 6.9.
Except forℓ=2, the coefficients in the expansion of (J-I)∨ℓ in the Johnson basis will be distinct. Thus, the Johnson basis itself can be read off directly from (J-I)∨ℓ. In this sense, the centralizer algebra of the action of the symmetric group on ℓ-sets is determined by knowledge of the action of just J-I on ℓ-sets.


## 6.1.1. Combinatorial Interpretation ofDn,ℓ

We now give a combinatorial interpretation ofDn,ℓ for ℓ≥1.Whenℓ≥1, recurrence (5.3) for Pn,ℓ(-1,1) gives(6.5)Dn,l=Dn,l-1+Dn-1,l-1.
We say that a subset I of [n] is deranged by a permutation if no point of I is fixed by the permutation.Proposition 6.3.
Dn,0=dn, the number of derangements of [n]. In general, for ℓ≥0, Dn,ℓ is the number of permutations of [n] in which the set {1,2,…,n-ℓ} is deranged, with no restrictions on the ℓ-set {n-ℓ+1,…,n}.Proof.
Forℓ≥0, let Dn,ℓ* denote the set of permutations in the statement of the proposition. Let En,ℓ=|Dn,ℓ*|. We claim that En,ℓ=Dn,ℓ.
The caseℓ=0 is immediate. We show that En,ℓ satisfies recurrence (6.5).
Now, letℓ>0. Consider a permutation in Dn,ℓ*. The point n is either (1) deranged, or (2) not deranged (i.e., fixed). (1)
Ifn is deranged, then the (n-ℓ+1)-set {1,2,…,n-ℓ,n} is deranged. By switching n↔n-ℓ+1 in all permutations of Dn,ℓ*, we obtain a permutation in Dn,ℓ-1*. Conversely, given any permutation of Dn,ℓ-1*, we switch n↔n-ℓ+1 to obtain a permutation in Dn,ℓ* where n is deranged. Hence, the number of permutations in Dn,ℓ* with n deranged equals En,ℓ-1.(2)
Here,n is fixed, so if we remove n from any permutation in Dn,ℓ* we obtain a permutation in Dn-1,ℓ-1*. Conversely, given a permutation in Dn-1,ℓ-1*, we may include n as a fixed point to obtain a permutation in Dn,ℓ* with n fixed. Hence, the number of permutations in Dn,ℓ* with n fixed equals En-1,ℓ-1.Combining the above two paragraphs shows that En,ℓ satisfies recurrence (6.5).And a quick check,(6.6)Dn,n=n!,
there being no restrictions at all in the combinatorial interpretation, in agreement with (6.3) for ℓ=n.Example 6.4.
Whenn=3, we have d3=D3,0=2 corresponding to the 2 permutations of [1] in which {1,2,3} is moved: 231,312.
Then,D3,1=3 corresponding to the 3 permutations of [1] in which {1,2} is moved: 213,231,312.
Then,D3,2=4 corresponding to the 4 permutations of [1] in which {1} is moved: 213,231,312,321.
Finally,D3,3=3!=6 corresponding to the 3 permutations of [1] in which ∅ is moved: 123,132,213,231,312,321.Reversing the order of summation in (6.3) gives an alternative expression(6.7)Dn,l=∑j=0n-l(-1)j(n-lj)(n-j)!.Remark 6.5.
Formulation (6.7) may be proved directly by inclusion-exclusion on permutations fixing given points.Example 6.6.
Consider(6.8)D5,2=∑j=03(-1)j(3j)(5-j)!=(30)5!-(31)4!+(32)3!-(33)2!=120-72+18-2=64.Now, from (2) of Theorem5.3, s=-1, and t=1, we have(6.9)Dn,l=∑j=0l(lj)dn-j.
Here is a combinatorial explanation. To obtain a permutation in Dn,ℓ*, we first choose j points from {n-ℓ+1,…,n} to be fixed. Then, every derangement of the remaining (n-j) points will produce a permutation in Dn,ℓ*, and there are dn-j of such derangements.Example 6.7.
Consider(6.10)D5,2=∑j=02(2j)d5-j=(20)d5+(21)d4+(22)d3=1×44+2×9+1×2=44+18+2=64.


## 6.1.2. Permanents fromJ-I

Theorem4.1 specializes to (6.11)(J-I)∨l=∑k=0min⁡(l,n-l)Dl,kJSknl.
This can be written using the hypergeometric form (6.12)(J-I)∨l=∑k=0min⁡(l,n-l)(-1)l-kk!2F0(a,b—k-l,1+k—|1a,b—)JSknl,
with spectrum (6.13)eigenvalue(-1)l2F0(a,b—α-l,-α+n-l+1—|1a,b—),occurringwithmultiplicity(nα)-(nα-1),
by Corollary 4.3 and Proposition 4.2.The entries of(J-I)∨ℓ are from the set of numbers Dn,ℓ. For the spectrum, start with α=0. From (6.3), we have (6.14)(-1)l2F0(a,b—-l,n-l+1—|1a,b—)=1(n-l)!Dn,n-l.
As α increases, we see that the spectrum consists of the numbers (6.15)(-1)α(n-l-α)!Dn-2α,n-l-α.
Think of moving in the derangement triangle, as in the appendix, starting from position n,n-ℓ, rescaling the values by the factorial of the column at each step, then the eigenvalues are found by successive knight's moves, up 2 rows and one column to the left, with alternating signs.Example 6.8.
Forn=5, ℓ=3, we have
(6.16)(J-I)∨3=[2333343344323343343433243343343342333443343323434343333244333343442333343434323343344333234443333332],
with characteristic polynomial
(6.17)λ5(λ-32)(λ+3)4.Remark 6.9.
Except forℓ=2, the coefficients in the expansion of (J-I)∨ℓ in the Johnson basis will be distinct. Thus, the Johnson basis itself can be read off directly from (J-I)∨ℓ. In this sense, the centralizer algebra of the action of the symmetric group on ℓ-sets is determined by knowledge of the action of just J-I on ℓ-sets.


## 6.2. Generalized Arrangements of[n]

Given[n], 0≤j≤n, a j-arrangement of [n] is a permutation of a j-subset of [n]. The number of j-arrangements of [n] is (6.18)A(n,j)=n!(n-j)!.
Note that there is a single 0-arrangement of [n], from the empty set.DefineAn,ℓ=Pn,ℓ(1,1). So, similar to the case for derangements, (5.9) gives(6.19)An,l=∑j=ln(n-ln-j)j!=l!2F0(a,b—l-n,1+l—|-1a,b—).
Now, define an=An,0, so (6.20)an=per(I+J)=∑j=0nn!(n-j)!=∑j=0nA(n,j)
is thetotal number of j-arrangements of [n] for j=0,1,…,n. Thus, we have a combinatorial interpretation of An,0.


### 6.2.1. Combinatorial Interpretation ofAn,ℓ

We now give a combinatorial interpretation ofAn,ℓ for ℓ≥1.Whenℓ≥1, recurrence (5.3) for Pn,ℓ(1,1) gives(6.21)An,l=An,l-1-An-1,l-1.Proposition 6.10.
An,0=an, the total number of arrangements of [n]. In general, for ℓ≥0, An,ℓ is the number of arrangements of [n]  which contain {1,2,…,ℓ}.Proof.
Forℓ≥0, let An,ℓ* denote the set of arrangements of [n] which contain [ℓ]. With [0]=∅, we note that An,0* is the set of all arrangements. Let Bn,ℓ=|An,ℓ*|. We claim that Bn,ℓ=An,ℓ.
The initial values withℓ=0 are immediate. We show that Bn,ℓ satisfies recurrence (6.21).
ConsiderAn,ℓ-1*. Let A∈An,ℓ-1*, so A is an arrangement of [n] containing [ℓ-1]. If ℓ=1, then A∈An,0* is any arrangement. Now, either ℓ∈A or ℓ∉A.
Ifℓ∈A, then A∈An,ℓ*, and so the number of arrangements in An,ℓ-1* which contain ℓ equals Bn,ℓ.
Ifℓ∉A, then by subtracting 1 from all parts of A which are ≥ℓ+1, we obtain an arrangement of [n-1] which contains [ℓ-1], that is, an arrangement in An-1,ℓ-1*. Conversely, given an arrangement in An-1,ℓ-1*, adding 1 to all parts ≥ℓ yields an arrangement in An,ℓ-1* which does not contain ℓ. Hence, the number of arrangements in An,ℓ-1* which do not contain ℓ equals Bn-1,ℓ-1.
We conclude thatBn,ℓ-1=Bn,ℓ+Bn-1,ℓ-1; hence, This is the result.Example 6.11.
Whenn=3, we have a3=A3,0=16 corresponding to the 16 arrangements of [1]: [],1,2,3,12,21,13,31,23,32,123,132,213,231,312,321.
Then,A3,1=11 corresponding to the 11 arrangements of [1] which contain {1}: 1,12,21,13,31,123,132,213,231,312,321.
Then,A3,2=8 corresponding to the 8 arrangements of [1] which contain {1,2}: 12,21,123,132,213,231,312,321.
Finally,A3,3=3!=6 corresponding to the 6 arrangements of [1] which contain {1,2,3}: 123,132,213,231,312,321.Rearranging the factors in (5.9), we have (6.22)Pn,l(s,t)=∑j=lnA(j,l)A(n-l,j-l)sn-jtj,
With s=t=1, this gives(6.23)An,l=∑j=lnA(j,l)A(n-l,j-l).
Here is a combinatorial explanation of (6.23).For anyj≥ℓ, to obtain a j-arrangement A of [n] containing [ℓ], we may place the ℓ points of {1,2,…,ℓ} into these j positions in A(j,ℓ) ways. Then, the remaining (j-ℓ) positions in A can be filled in by a (j-ℓ)-arrangement of the unused (n-ℓ) points in A(n-ℓ,j-ℓ) ways.Example 6.12.
Consider(6.24)A5,2=∑j=25A(j,2)A(3,j-2)=A(2,2)A(3,0)+A(3,2)A(3,1)+A(4,2)A(3,2)+A(5,2)A(3,3)=2×1+6×3+12×6+20×6=2+18+72+120=212.
Finally, from (2) of Theorem 5.3, s=1, and t=1, we have
(6.25)An,l=∑j=0l(-1)j(lj)an-j.Example 6.13.
Consider(6.26)A5,2=∑j=02(-1)j(2j)a5-j=(20)a5-(21)a4+(22)a3=1×326-2×65+1×16=326-130+16=212.


### 6.2.2. Permanents fromI+J

Theorem4.1 specializes to (6.27)(I+J)∨l=∑k=0min⁡(l,n-l)Al,kJSknl.
This can be written using the hypergeometric form (6.28)(I+J)∨l=∑k=0min⁡(l,n-l)k!2F0(a,b—k-l,1+k—|-1a,b—)JSknl,
with spectrum (6.29)eigenvalue2F0(a,b—α-l,-α+n-l+1—|-1a,b—),occurringwithmultiplicity(nα)-(nα-1),
by Corollary 4.3 and Proposition 4.2.Example 6.14.
Forn=5, ℓ=3, we have
(6.30)(I+J)∨3=[16111111118111188111611118111181181111168111181111811118161111118811118111116118118118111111111688111111118118816111111118118118111611118111188111111161188811111111111116],
with characteristic polynomial
(6.31)(λ-106)(λ-11)4(λ-2)5.
As for the case of derangements, the Johnson basis can be read off directly from the matrix (I+J)∨ℓ.


## 6.2.1. Combinatorial Interpretation ofAn,ℓ

We now give a combinatorial interpretation ofAn,ℓ for ℓ≥1.Whenℓ≥1, recurrence (5.3) for Pn,ℓ(1,1) gives(6.21)An,l=An,l-1-An-1,l-1.Proposition 6.10.
An,0=an, the total number of arrangements of [n]. In general, for ℓ≥0, An,ℓ is the number of arrangements of [n]  which contain {1,2,…,ℓ}.Proof.
Forℓ≥0, let An,ℓ* denote the set of arrangements of [n] which contain [ℓ]. With [0]=∅, we note that An,0* is the set of all arrangements. Let Bn,ℓ=|An,ℓ*|. We claim that Bn,ℓ=An,ℓ.
The initial values withℓ=0 are immediate. We show that Bn,ℓ satisfies recurrence (6.21).
ConsiderAn,ℓ-1*. Let A∈An,ℓ-1*, so A is an arrangement of [n] containing [ℓ-1]. If ℓ=1, then A∈An,0* is any arrangement. Now, either ℓ∈A or ℓ∉A.
Ifℓ∈A, then A∈An,ℓ*, and so the number of arrangements in An,ℓ-1* which contain ℓ equals Bn,ℓ.
Ifℓ∉A, then by subtracting 1 from all parts of A which are ≥ℓ+1, we obtain an arrangement of [n-1] which contains [ℓ-1], that is, an arrangement in An-1,ℓ-1*. Conversely, given an arrangement in An-1,ℓ-1*, adding 1 to all parts ≥ℓ yields an arrangement in An,ℓ-1* which does not contain ℓ. Hence, the number of arrangements in An,ℓ-1* which do not contain ℓ equals Bn-1,ℓ-1.
We conclude thatBn,ℓ-1=Bn,ℓ+Bn-1,ℓ-1; hence, This is the result.Example 6.11.
Whenn=3, we have a3=A3,0=16 corresponding to the 16 arrangements of [1]: [],1,2,3,12,21,13,31,23,32,123,132,213,231,312,321.
Then,A3,1=11 corresponding to the 11 arrangements of [1] which contain {1}: 1,12,21,13,31,123,132,213,231,312,321.
Then,A3,2=8 corresponding to the 8 arrangements of [1] which contain {1,2}: 12,21,123,132,213,231,312,321.
Finally,A3,3=3!=6 corresponding to the 6 arrangements of [1] which contain {1,2,3}: 123,132,213,231,312,321.Rearranging the factors in (5.9), we have (6.22)Pn,l(s,t)=∑j=lnA(j,l)A(n-l,j-l)sn-jtj,
With s=t=1, this gives(6.23)An,l=∑j=lnA(j,l)A(n-l,j-l).
Here is a combinatorial explanation of (6.23).For anyj≥ℓ, to obtain a j-arrangement A of [n] containing [ℓ], we may place the ℓ points of {1,2,…,ℓ} into these j positions in A(j,ℓ) ways. Then, the remaining (j-ℓ) positions in A can be filled in by a (j-ℓ)-arrangement of the unused (n-ℓ) points in A(n-ℓ,j-ℓ) ways.Example 6.12.
Consider(6.24)A5,2=∑j=25A(j,2)A(3,j-2)=A(2,2)A(3,0)+A(3,2)A(3,1)+A(4,2)A(3,2)+A(5,2)A(3,3)=2×1+6×3+12×6+20×6=2+18+72+120=212.
Finally, from (2) of Theorem 5.3, s=1, and t=1, we have
(6.25)An,l=∑j=0l(-1)j(lj)an-j.Example 6.13.
Consider(6.26)A5,2=∑j=02(-1)j(2j)a5-j=(20)a5-(21)a4+(22)a3=1×326-2×65+1×16=326-130+16=212.


## 6.2.2. Permanents fromI+J

Theorem4.1 specializes to (6.27)(I+J)∨l=∑k=0min⁡(l,n-l)Al,kJSknl.
This can be written using the hypergeometric form (6.28)(I+J)∨l=∑k=0min⁡(l,n-l)k!2F0(a,b—k-l,1+k—|-1a,b—)JSknl,
with spectrum (6.29)eigenvalue2F0(a,b—α-l,-α+n-l+1—|-1a,b—),occurringwithmultiplicity(nα)-(nα-1),
by Corollary 4.3 and Proposition 4.2.Example 6.14.
Forn=5, ℓ=3, we have
(6.30)(I+J)∨3=[16111111118111188111611118111181181111168111181111811118161111118811118111116118118118111111111688111111118118816111111118118118111611118111188111111161188811111111111116],
with characteristic polynomial
(6.31)(λ-106)(λ-11)4(λ-2)5.
As for the case of derangements, the Johnson basis can be read off directly from the matrix (I+J)∨ℓ.



---

*Source: 539030-2011-06-02.xml*