Isometry Classes of Indecomposable Linear Codes

Harald Fripertinger, Adalbert Kerber

January 30, 1995

Abstract In the constructive theory of linear codes, we can restrict attention to the isometry classes of indecomposable codes, as it was shown by Slepian. We describe these classes as orbits and we demonstrate how they can be enumerated using cycle index polynomials and the tools already incorporated in SYMMETRICA, a computer algebra package devoted to representation theory and combinatorics of symmetric groups and of related classes of groups. Moreover, we describe how systems of representatives of these classes can be evaluated using double coset methods.

1 Notation

Suppose we are given a permutation group G on a set X. It induces interesting structures both on X and on G that are closely related (for more details cf. [7]). To begin with, there are the orbits of the elements x ∈ X: G(x): = {gx | g ∈ G} ⊆ X, two of which are either identical or disjoint. Therefore, the set

G\\X: = {G(x) | x ∈ X} .

of all the orbits is a set-partition of X. To the orbits there correspond the stabilizers (which are in fact subgroups): G_{x} := {g ∈ G | gx = x}, and the close relationship between orbits and stabilizers is the existence of the following natural bijection between an orbit of an element and the set of left cosets of its stabilizer:

G(x) → G/G_{x}, gx ↦ gG_{x}.

The cycle index of G is the following polynomial Z(G) in the indeterminates x_{1}, x_{2}, …, x_{|X|} over IQ, defined by

Z(G) := \frac{1}{|G|} ∑_{g∈G} ∏_{i=1}^{|X|} x_{i}^{a_{i}(g)},

where (a_{1}(g), …, a_{|X|}(g)) is the cycle type of the permutation g ∈ G. This means, g decomposes into a_{i}(g) disjoint cycles of length i for i = 1, …, |X|. All elements of a conjugacy class have the same cycle type, so the cycle index can be computed in the following way:

Z(G) = \frac{1}{|G|} ∑_{C∈C} |C| ∏_{i=1}^{|X|} x_{i}^{a_{i}(g_{C})},  (1)

where C is the system of conjugacy classes of G and where g_{C} is a representative of the conjugacy class C. Let G and H denote permutation groups on X and Y, respectively. The wreath product H ≀_{X} G is a permutation group on the set Y^{X} := {f: X → Y }, defined by

H ≀_{X} G := H^{X} × G = {(ψ, g) | ψ ∈ H^{X}, g ∈ G}

with multiplication (ψ, g)(ψ′, g′) = (ψψ′_{g}, gg′), where ψψ′_{g}(x) := ψ(x)ψ′_{g}(x) and ψ′_{g}(x) := ψ′(g^{−1}x). In the case when G ≤ S_{n} and X = n := {0, 1, …, n − 1} we write H ≀ G instead of H ≀_{n} G. The wreath product H ≀_{X} G acts in a natural way on Y^{X}. The effect of the permutation (ψ, g) ∈ H ≀_{X} G on f ∈ Y^{X} is

(ψ, g)(f) =: f̃, where f̃(x) = ψ(g)f(g^{−1}x).  (2)

The following lemma ([10, 9]) reduces the action of a wreath product to the action of the group G on the set of all functions from X into the set of all orbits of H on Y:

1.1 Lehmann’s Lemma: If G and H denote permutation groups on X and Y, respectively, then G acts on (H\\Y)^{X} in the following way:

g(f) := f ∘ g^{−1}.

Moreover, the mapping

Φ: H ≀_{X} G\\Y^{X} → G\\(H\\Y)^{X}, (H ≀_{X} G(f)) ↦ G(F)

is a bijection if F ∈ (H\\Y)^{X} is given by F (x) = H(f(x)). There are many enumerative and constructive results dealing with various group actions on the set Y^{X} induced by permutation groups on the domain X and on the range Y. For example, S_{n} × H acts upon Y^{n} by

(π, h)(f) := h ∘ f ∘ π^{−1}.

The corresponding generating function for the numbers of S_{n} × H-orbits on Y^{n} is given by (see [1]):

∑_{n=0}^{∞} |(S_{n} × H)\\Y^{n}| x^{n} = Z(H)|_{x_{i}=∑_{j=0}^{∞} x^{ij}} = Z(H)|_{x_{i}= \frac{1}{1−x^{i}}} .  (3)

The group action of above can be restricted to the set of all injective mappings from n to Y, the corresponding generating function is

∑_{n=0}^{∞} |(S_{n} × H)\\Y_{inj}^{n}| x^{n} = Z(H)|_{x_{i}=1+x^{i}}.  (4)

2 Isometry classes of linear codes

A linear (n, k)-code over the Galois field GF (q) is a k-dimensional subspace of the vector space Y^{X} := GF (q)^{n}. As usual codewords will be written as rows x = (x_{0}, …, x_{n−1}). A k × n-matrix Γ over GF (q) is called a generator matrix of the linear (n, k)-code C, if and only if the rows of Γ form a basis of C, so that C = {x · Γ | x ∈ GF (q)^{k}}. Two linear (n, k)-codes C_{1}, C_{2} are called equivalent, if and only if there is an isometry (with respect to the Hamming metric) which maps C_{1} onto C_{2}. Using the notion of finite group actions one can easily express equivalence of codes in terms of the wreath product action introduced above: C_{1} and C_{2} are equivalent, if and only if there exist (ψ, π) ∈ GF (q)^{∗} ≀ S_{n} (where GF (q)^{∗} denotes the multiplicative group of the Galois field) such that (ψ, π)(C_{1}) = C_{2}. The complete monomial group GF (q)^{∗} ≀ S_{n} of degree n over GF (q)^{∗} acts on GF (q)^{n} as it was described above (see equation (2)) in the more general case of H ≀_{X} G on Y^{X}:

(ψ, π)(f)(x) = ψ(x)f(π^{−1}x).  (5)

In order to apply the results of the theory of finite group actions, this equivalence relation for linear (n, k)-codes is translated into an equivalence relation for generator matrices of linear codes, and these generator matrices are considered to be functions Γ: n → GF (q)^{k} \ {0} where Γ(i) is the i-th column of the generator matrix Γ. (We exclude 0-columns for obvious reasons.)

2.1 Theorem The matrices corresponding to the two functions Γ_{1} and Γ_{2} from n to GF (q)^{k} \ {0} are generator matrices of two equivalent codes, if and only if Γ_{1} and Γ_{2} lie in the same orbit of the following action of GL_{k}(q) × GF (q)^{∗} ≀ S_{n} as permutation group on (GF (q)^{k} \ {0})^{n}:

(A, (ψ, π))(Γ) = Aψ(·)Γ(π^{−1}·),

or, more explicitly,

(A, (ψ, π))(Γ)(i) := Aψ(i)Γ(π^{−1}(i)).

Following Slepian, we use the following notation:

T_{nkq} := the number of orbits of functions Γ: n → GF (q)^{k} \ {0} under the group action of 2.1, i.e. T_{nkq} = |(GL_{k}(q) × GF (q)^{∗} ≀ S_{n})\\(GF (q)^{k} \ {0})^{n}|.

T̄_{nkq} := the number of orbits of functions Γ: n → GF (q)^{k} \ {0} under the group action of 2.1, such that for all i, j ∈ n, i ≠ j and all α ∈ GF (q)^{∗} the value of Γ(i) is different from αΓ(j). (In the case q = 2, this is the number of injective functions G.)

S_{nkq} := the number of equivalence classes of linear (n, k)-codes over GF (q) with no columns of zeros. (A linear (n, k)-code has columns of zeros, if and only if there is some i ∈ n such that x_{i} = 0 for all codewords x, and so we should exclude such columns.)

S̄_{nkq} := the number of classes of injective linear (n, k)-codes over GF (q) with no columns of zeros. (A linear (n, k)-code is called injective, if and only if for all i, j ∈ n, i ≠ j and α ∈ GF (q)^{∗} there is some codeword x such that x_{i} ≠ αx_{j}.)

R_{nkq} := the number of classes of indecomposable linear (n, k)-codes over GF (q) with no columns of zeros. (The definition of an indecomposable code will be given later.)

R̄_{nkq} := the number of classes of indecomposable, injective linear (n, k)-codes over GF (q) with no columns of zeros.

W_{nkq} := be the number of classes of linear (n, k)-codes over GF (q) with columns of zeros allowed.

The following formulae hold:

W_{nkq} = ∑_{i=k}^{n} S_{ikq}, S_{nkq} = T_{nkq} − T_{n,k−1,q}, S̄_{nkq} = T̄_{nkq} − T̄_{n,k−1,q}. (6)

As initial values we have S_{n1q} = 1 for n ∈ IN, S̄_{11q} = 1 and S̄_{n1q} = 0 for n > 1. It is important to realize that

• T_{nkq} is the number of orbits of functions from n to GF (q)^{k} \ {0} without any restrictions on the rank of the induced matrix.

• All matrices which are induced from functions Γ of the same orbit have the same rank.

• The number of orbits of functions Γ which induce matrices of rank less or equal k − 1 is T_{n,k−1,q}. (This proposition holds for T̄_{nkq} as well.)

In the next section we will show that the R_{nkq} or R̄_{nkq} can be computed from the S_{nkq} or S̄_{nkq} respectively, so the main problem is the computation of the T_{nkq} or T̄_{nkq}.

In the case q = 2 the wreath product GF (q)^{∗} ≀ S_{n} becomes the group S_{n}, and so there is the group GL_{k}(2) acting on GF (2)^{k} \ {0} and the symmetric group S_{n} acting on n. Applying the formulae (3) and (4) we get

∑_{n=0}^{∞} T_{nk2}x^{n} = Z(GL_{k}(2))|_{x_{i}=∑_{j=0}^{∞} x^{ij}} = Z(GL_{k}(2))|_{x_{i}= \frac{1}{1−x^{i}}}  (7)

and

∑_{n=0}^{∞} T̄_{nk2}x^{n} = Z(GL_{k}(2))|_{x_{i}=1+x^{i}}.  (8)

In the case q ≠ 2 the wreath product GF (q)^{∗}≀S_{n} acts both on range and domain of the functions Γ. Applying Lehmann’s Lemma 1.1 there is the bijection

Φ: GF (q)^{∗} ≀ S_{n}\\(GF (q)^{k} \ {0})^{n} → S_{n}\\ (GF (q)^{∗}\\(GF (q)^{k} \ {0}))^{n} ,
GF (q)^{∗} ≀ S_{n}(Γ) ↦ S_{n}(Γ̄)

where

Γ̄: n → GF (q)^{∗}\\(GF (q)^{k} \ {0}), i ↦ GF (q)^{∗}(Γ(i))

and S_{n} acts on (GF (q)^{∗}\\(GF (q)^{k} \ {0}))^{n} by π(Γ̄) = Γ̄ ∘ π^{−1}. Using this bijection we have to investigate the following action of S_{n} × GL_{k}(q):

(π, A)(Γ̄) = AΓ̄π^{−1},

where GL_{k}(q) acts on GF (q)^{∗}\\(GF (q)^{k}\{0}) by A(GF (q)^{∗}(v)) = GF (q)^{∗}(Av). The set of the GF (q)^{∗}-orbits GF (q)^{∗}\\(GF (q)^{k} \ {0}) is the (k − 1)-dimensional projective space:

GF (q)^{∗}\\GF (q)^{k} = P G_{k−1}(q)

and the representation of GL_{k}(q) as a permutation group is the projective linear group P GL_{k}(q). This proves in fact the following to be true:

2.2 Theorem The isometry classes of linear (n, k)-codes over GF (q) are the orbits of GL_{k}(q) × S_{n} on the set of mappings P G_{k−1}(q)^{n}. This set of orbits is equal to the set of orbits of GL_{k}(q) on the set S_{n}\\P G_{k−1}(q)^{n}, which can be represented by a complete set of mappings of different content, if the content of f ∈ P G_{k−1}(q)^{n} is defined to be the sequence of orders of inverse images |f^{−1}(x)|. Thus the set of isometry classes of linear (n, k)-codes over GF (q) is equal to the set of orbits of GL_{k}(q) on the set of mappings f ∈ P G_{k−1}(q) of different content that form k × n-matrices of rank k. The particular classes of elements with orders of inverse images |f^{−1}(x)| ≤ 1 are the classes consisting of Hamming codes.

Knowing the cycle index of P GL_{k}(q) acting on P G_{k−1}(q) the equations (3) and (4) can be applied again. In [13] Slepian explained how the cycle index of GL_{k}(2) can be computed using results of Elspas [3]. The first author [4] generalized this concept for computing the cycle indices of GL_{k}(q) and P GL_{k}(q) acting on GF (q)^{k} or P G_{k−1}(q) respectively. The steps of the method used were the following ones:

1. Determination of the conjugacy classes of GL_{k}(q) by applying the theory of normal forms of matrices (or vector space endomorphisms). This theory can be found in many textbooks of algebra.

2. Determination of the order of the conjugacy classes, which can be found in Dickson, Green or Kung [2, 5, 8].

3. Determination of the cycle type of a linear map or of a projectivity respectively. Since normal forms of regular matrices are strongly connected with companion and hypercompanion matrices (see [6]) of monic, irreducible polynomials over GF (q) it is important to know the exponent or subexponent of such polynomials (see [11, 6]). The exponent of such a polynomial f(x) ∈ GF (q)[x] is defined to be

exp(f(x)) := min {n ∈ IN | f(x) | x^{n} − 1}

and the subexponent is

subexp(f(x)) := min {n ∈ IN | ∃α ∈ GF (q)^{∗} : f(x) | x^{n} − α} .

This element α ∈ F_{q}^{∗} is uniquely defined, and it is called the integral element of f(x). The exponent of f(x) can be used to compute the cycle type of the companion or hypercompanion matrices of a monic, irreducible polynomial f(x), and by a direct product formula for cycle indices the cycle types of the normal forms in GL(k, F_{q}) can be derived. Using the subexponent of f(x) and defining a formula similar to the direct product formula of cycle indices, which depends on the integral element of f(x) as well, the cycle type of a projectivity can be computed.

4. Determination of the cycle index by applying formula (1).

These cycle indices are now available in the computer algebra package SYM-METRICA. Tables obtained this way are shown lower down.

3 Indecomposability

In order to minimize the number of orbits that must be enumerated or represented, and following Slepian again, we can restrict attention to indecomposable linear (n, k)-codes. Let C_{1} be a linear (n_{1}, k_{1})-code over GF (q) with generator matrix Γ_{1} and let C_{2} be a linear (n_{2}, k_{2})-code over GF (q) with generator matrix Γ_{2}, then the code C with generator matrix

Γ := ( \begin{matrix}Γ_{1} & 0 \\ 0 & Γ_{2} \end{matrix} )

is called the direct sum of the codes C_{1} and C_{2}, and it will be denoted by C = C_{1} ⊕ C_{2}. A code C is called decomposable, if and only if it is equivalent to a code which is the direct sum of two or more linear codes. Otherwise it is called indecomposable. In [13] Slepian proves that every decomposable linear (n, k)-code is equivalent to a direct sum of indecomposable codes, and that this decomposition is unique up to equivalence and order of the summands. Slepian used a generating function scheme for computing the numbers R_{nk2} and R̄_{nk2}. However after constructing these codes the authors realized that in some situations this formula doesn’t work correctly. For that reason we are giving another formula to determine the numbers R_{nkq} and R̄_{nkq}. For the rest of this section let n ≥ 2.

3.1 Theorem The number R_{nkq} is equal to

S_{nkq} − ∑_{a} ∑_{b} ∏_{{j=1 \atop a_{j} ≠0}}^{n−1} ( ∑_{{c=(c_{1},...,ca_{j} )∈IN^{a_{j}} \atop j≥c_{1}≥...≥ca_{j} ≥1, ∑ c_{i}=b_{j}}} U(j, a, c)) ,

where

U(j, a, c) = ∏_{i=1}^{j} Z(S_{ν(i,a_{j},c)})|_{x_{ℓ}=R_{jiq}}, ν(i, a_{j}, c) = |{1 ≤ l ≤ a_{j} | c_{l} = i}| ,

and where the first sum is taken over the cycle types a = (a_{1}, …, a_{n−1}) of n, (which means that a_{i} ∈ IN_{0} and ∑ ia_{i} = n) such that ∑ a_{i} ≤ k, while the second sum is over the (n − 1)-tuples b = (b_{1}, …, b_{n−1}) ∈ IN_{0}^{n−1}, for which a_{i} ≤ b_{i} ≤ ia_{i}, and ∑ b_{i} = k. In the same way the R̄_{nkq} can be computed from the S̄_{nkq}. The numerical results show that for fixed q and n the sequence of R_{nkq} is unimodal and symmetric. (It is easy to prove that this sequence must be symmetric, but the proof of the unimodality is still open.) Proof: In order to evaluate the values R_{nkq} the number of all classes of decomposable linear (n, k)-codes must be subtracted from S_{nkq}. In other words one has to find all possibilities of decomposing a linear (n, k)-code into a direct sum of indecomposable linear (n_{i}, k_{i})-codes such that

∑_{i=1}^{l} n_{i} = n,  ∑_{i=1}^{l} k_{i} = k,  1 ≤ k_{i} ≤ n_{i},  2 ≤ l ≤ k.  (9)

According to Slepians theorem the (n_{i}, k_{i})-codes can be arranged such that n_{1} ≥ n_{2} ≥ … ≥ n_{l} and in the case that n_{i} = n_{i+1} the inequality k_{i} ≥ k_{i+1} holds. At first all partitions of n into at least two parts and into at most k parts must be found. Let n = n_{1} + n_{2} + … + n_{l} be such a partition with n_{i} ≥ 1 and 2 ≤ l ≤ k. Then the cycle type of λ is (a_{1}, a_{2}, …, a_{n−1}), where a_{i} = |{1 ≤ j ≤ l | n_{j} = i}|. Two decomposable codes which determine two different partitions of n are not equivalent. In the second step to each partition of n one has to find all sequences (k_{1}, …, k_{l}) such that (9) is fulfilled, and such that codes belonging to different sequences are not equivalent. In order to do this we start with such a sequence (k_{1}, …, k_{l}) and define

b_{i} := ∑_{j:n_{j}=i} k_{j},

then

∑_{i=1}^{n−1} b_{i} = ∑_{i=1}^{l} k_{i} = k and a_{i} ≤ b_{i} ≤ ia_{i}.

Two decomposable codes which on the one hand belong to one partition of n but on the other hand define two different vectors b and b′ are not in the same equivalence class. Now the other way round we start with a sequence (b_{1}, …, b_{n−1}) and try to determine all sequences (k_{1}, …, k_{l}) which define non equivalent codes such that b_{i} = ∑_{j:n_{j}=i} k_{j}. Again by Slepian’s theorem we must find all partitions of b_{j} ≠ 0 (this implies a_{j} ≠ 0) into exacyly a_{j} parts of the form

b_{j} = ∑_{i=1}^{a_{j}} c_{i}, j ≥ c_{1} ≥ … ≥ c_{a_{j}} ≥ 1.

In the last step U(j, a, c) must be evaluated. This is the the number of classes of linear (j · a_{j}, b_{j})-codes, which have a decomposition into a direct sum of indecomposable (j, c_{i})-codes for 1 ≤ i ≤ a_{j} to a given partition c of b_{j} into exactly a_{j} parts. We already know that there are R_{j,c_{i},q} classes of indecomposable linear (j, c_{i})-codes. In the case that all the c_{i} are distinct, this number is given by

∏_{i=1}^{a_{j}} R_{j,c_{i},q}.

Otherwise there exist i, l such that i < l and c_{i} = c_{l}. Then c_{i} = c_{i+1} = … = c_{l} and permuting the corresponding summands in the direct sum may lead to equivalent codes. For 1 ≤ i ≤ j let ν(i) = ν(i, a_{j}, c) be the cardinality of {t | c_{t} = i}. Now there is a bijection between the classes of codes, which are a direct sum of ν(i) (j, i)-codes and the orbits of the symmetric group S_{ν(i)} on the set of all mappings from ν(i) into a set of R_{jiq} elements, where the action of S_{ν(i)} is given by:

S_{ν(i)} × R_{jiq}^{ν(i)} → R_{jiq}^{ν(i)}, (π, f) ↦ f ∘ π^{−1}.

By Pólyas theorem [12] one has to compute the cycle index S_{ν(i)} and each variable must be substituted by R_{jiq}. Doing this for all possible values of i we get

U(j, a, c) = ∏_{i=1}^{j} Z(S_{ν(i)})|_{x_{ℓ}=R_{jiq}}.

Using the computer algebra system SYMMETRICA, among many other ones the tables of numbers of indecomposable codes which are shown below were computed.

4 Construction

Methods for constructing representatives of classes of linear (n, k)-codes obviously do not reach as far as the enumerative methods, but the use of computers allows to get a complete overview of linear (n, k)-codes over GF (q) for quite a number of parameter triples (n, k, q). We have seen before that the isometry classes can be described as orbits of GL_{k}(q) on sets of mappings into the projective space. A very interesting and helpful constructive method for discrete structures which can be defined as orbits of finite groups on finite sets is based on the following fact. If G is a transitive permutation group on X, then the orbits of a subgroup U ≤ G on X can be bijectively mapped onto double cosets as follows: For any x ∈ X the mapping

U\\X → U\G/G_{x}, U(gx) ↦ UgG_{x}

is a bijection. In the case of the (n, k)-codes we can use the fact that the general linear group GL_{n}(q) is transitive on the set S(n, k, q) of subspaces of dimension k in GF (q)^{n}, so that the isometry classes of linear (n, k)-codes turn out to be in one-one-correspondence with the set of double cosets

GF (q)^{∗} ≀ S_{n}\GL_{n}(q)/GL_{n}(q)_{C_{0}},

where C_{0} is any linear (n, k)-code. A computer program due to Weinrich ([14]) allows to evaluate complete sets of representatives, and it was recently improved by using, besides of double cosets the combinatorial method of orderly generation. The work in this field of constructive theory is still in rapid progress, so that we cannot tell yet how far we can reach.

References

[1] N.G. De Bruijn. Pólya’s Theory of Counting. In E.F. Beckenbach, editor, Applied Combinatorial Mathematics, chapter 5, pages 144 – 184. Wiley, New York, 1964.

[2] L.E. Dickson. Linear Groups. Dover Publications, Inc., New York, 1958.

[3] B. Elspas. The Theory of Autonomous Linear Sequential Networks. IRE Transactions on Circuit Theory, CT–6:45 – 60, 1959.

[4] H. Fripertinger. Cycle indices of linear, affine and projective groups. to be published.

[5] J.A. Green. The characters of the finite general linear groups. Trans. Amer. Math. Soc., 80:402 – 447, 1955.

[6] J.W.P. Hirschfeld. Projective Geometries over Finite Fields. Clarendon Press, Oxford, 1979. ISBN 0-19-853526-0.

[7] A. Kerber. Algebraic Combinatorics via Finite Group Actions. B. I. Wissenschaftsverlag, Mannheim, Wien, Zürich, 1991. ISBN 3-411-14521-8.

[8] J.P.S. Kung. The Cycle Structure of a Linear Transformation over a Finite Field. Linear Algebra and its Applications, 36:141 – 155, 1981.

[9] H. Lehmann. Das Abzähltheorem der Exponentialgruppe in gewichteter Form. Mitteilungen aus dem Mathem. Seminar Giessen, 112:19 – 33, 1974.

[10] H. Lehmann. Ein vereinheitlichender Ansatz für die REDFIELD – PÓLYA – de BRUIJNSCHE Abzähltheorie. PhD thesis, Universität Giessen, 1976.

[11] R. Lidl and H. Niederreiter. Finite Fields, volume 20 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Company, London, Amsterdam, Don Mills – Ontario, Sydney, Tokyo, 1983. ISBN 0-201-13519-1.

[12] G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68:145 – 254, 1937.

[13] D. Slepian. Some Further Theory of Group Codes. The Bell System Technical Journal, 39:1219 – 1252, 1960.

[14] St. Weinrich. Konstruktionsalgorithmen für diskrete Strukturen und ihre Implementierung. Master’s thesis, Universität Bayreuth, July 1993.

Table 1: R_{nk2} \begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 5 & 1 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 6 & 1 & 3 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 7 & 1 & 4 & 10 & 10 & 4 & 1 & 0 & 0 & 0 & 0 \\ 8 & 1 & 5 & 18 & 28 & 18 & 5 & 1 & 0 & 0 & 0 \\ 9 & 1 & 7 & 31 & 71 & 71 & 31 & 7 & 1 & 0 & 0 \\ 10 & 1 & 8 & 51 & 165 & 250 & 165 & 51 & 8 & 1 & 0 \\ 11 & 1 & 10 & 79 & 361 & 809 & 809 & 361 & 79 & 10 & 1 \\ 12 & 1 & 12 & 121 & 754 & 2484 & 3759 & 2484 & 754 & 121 & 12 \end{matrix}

Table 2: R_{nk3} \begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 1 & 3 & 3 & 1 & 0 & 0 & 0 \\ 6 & 1 & 5 & 10 & 5 & 1 & 0 & 0 \\ 7 & 1 & 7 & 24 & 24 & 7 & 1 & 0 \\ 8 & 1 & 10 & 55 & 105 & 55 & 10 & 1 \\ 9 & 1 & 13 & 116 & 403 & 403 & 116 & 13 \\ 10 & 1 & 17 & 231 & 1506 & 3000 & 1506 & 231 \\ 11 & 1 & 21 & 438 & 5425 & 23579 & 23579 & 5425 \\ 12 & 1 & 27 & 813 & 19440 & 199473 & 469473 & 199473 \end{matrix}

Table 3: R_{nk4} \begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 1 & 4 & 4 & 1 & 0 & 0 & 0 \\ 6 & 1 & 6 & 14 & 6 & 1 & 0 & 0 \\ 7 & 1 & 9 & 38 & 38 & 9 & 1 & 0 \\ 8 & 1 & 13 & 104 & 238 & 104 & 13 & 1 \\ 9 & 1 & 18 & 276 & 1573 & 1573 & 276 & 18 \\ 10 & 1 & 25 & 711 & 11566 & 34288 & 11566 & 711 \\ 11 & 1 & 32 & 1793 & 88140 & 909664 & 909664 & 88140 \\ 12 & 1 & 42 & 4446 & 665736 & 25.020688 & 90.186547 & 25.020688 \end{matrix}

Table 4: R_{nk5} \begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 2 & 1 & 0 & 0 & 0 \\ 5 & 1 & 4 & 4 & 1 & 0 & 0 \\ 6 & 1 & 8 & 18 & 8 & 1 & 0 \\ 7 & 1 & 11 & 62 & 62 & 11 & 1 \\ 8 & 1 & 18 & 222 & 659 & 222 & 18 \\ 9 & 1 & 26 & 800 & 8232 & 8232 & 800 \\ 10 & 1 & 38 & 2805 & 117351 & 483955 & 117351 \\ 11 & 1 & 51 & 9642 & 1674434 & 32.156437 & 32.156437 \end{matrix}

Table 5: R_{nk7} \begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 & 0 \\ 4 & 1 & 3 & 1 & 0 & 0 \\ 5 & 1 & 5 & 5 & 1 & 0 \\ 6 & 1 & 11 & 32 & 11 & 1 \\ 7 & 1 & 18 & 165 & 165 & 18 \\ 8 & 1 & 33 & 1006 & 4741 & 1006 \\ 9 & 1 & 50 & 6362 & 179586 & 179586 \\ 10 & 1 & 83 & 39417 & 7.058258 & 45.507354 \\ 11 & 1 & 123 & 233578 & 260.571116 & 11419.262502 \end{matrix}