The theory of q-analogs develops combinatorial formulas for finite vector spaces over a finite field with q elements–in analogy with formulas for finite sets (the limiting case q = 1). A direct-sum decomposition of a finite vector space is the vector-space analogue of a set partition. This paper uses elementary counting methods to derive direct formulas for the number of direct-sum decompositions (DSDs) that play the role of the Stirling and Bell numbers for set partitions. In particular, we give a signature-based counting formula for DSDs and recover the standard set-partition formulas in the limit q → 1. We also develop new companion formulas that enumerate DSDs with m blocks in an n-dimensional vector space over GF(q) such that a specified nonzero vector lies in one of the blocks, together with the corresponding totals over all numbers of blocks. Initial computations are included for the case q = 2, with hand-checkable low-dimensional examples, internal consistency checks, and applications to the pedagogical model of quantum mechanics over ℤ2 (QM/Sets). Four related sequences for q = 2 are recorded in the On-Line Encyclopedia of Integer Sequences
Ordinary logic started with the Boolean logic of subsets–although today it usually presented in the special case of propositional logic. But the formulation in terms of subsets is important because subsets (unlike propositions) are category-theoretically dual to partitions. In category theory, a subset (or, more generally, a subobject) is called a “ part” “The dual notion (obtained by reversing the arrows) of ‘part’ is the notion of partition” [1, p. 85]. Thus there is a dual logic of partitions at the same level of fundamentality as the logic of subsets ([2]; [3]; [4]). Subspaces are the vector space analog of subsets, so the Boolean logic of subsets has a quantum version as the logic of (closed) subspaces of Hilbert space [5]. The vector space analog of a partition is a direct-sum decomposition (DSD) of the vector space. Hence there is also quantum logic of direct-sum decompositions [6].
These developments have led to a renewed interest in direct-sum decompositions of vector spaces. In the case of finite vector spaces of cardinality \(q=p^{n}\) (\(p\) a prime), the vector space analogs are called “ \(q\)-analogs.” “One of the most intriguing notions to be developed is the \(q\)-analog of the notion of a partition of a set” [7, p. 257]. “Direct-sum decompositions are a \(q\)-analog of partitions of a finite set” [8, p. 764]. Using sophisticated techniques, the direct-sum decompositions of a finite vector space over \(GF\left( q\right)\) have been enumerated in the sense of giving the exponential generating function for the numbers ([8]; [9]). Our goal is to derive by elementary methods direct formulas for these \(q\)-analog DSD counts and to develop related new enumerations. More specifically, the total DSD counts and the \(m\)-block counts are known in the literature through generating-function methods ([8]; [9]), while the present paper emphasizes elementary signature-based derivations and explicit counting formulas. The genuinely new results in the paper are the designated-vector enumerations \(D_{q}^{\ast}\left( n,m\right)\) and \(D_{q}^{\ast}\left( n\right)\), together with their initial tables for \(q=2\). The new enumerations lead to a number of new integer sequences in On-Line Encyclopedia of Integer Sequences.
The theory of \(q\)-analogs shows how many “ classical” combinatorial formulas for finite sets can be extended to finite vector spaces where \(q\) is the cardinality of the finite base field \(GF(q)\), i.e., \(q=p^{n}\), a power of a prime.
The natural number \(n\) is replaced by:
\[\left[ n\right] _{q}=\frac{q^{n}-1}{q-1}=1+q+q^{2}+…+q^{n-1},\] so as \(q\rightarrow1\), then \(\left[ n\right] _{q}\rightarrow n\) in the passage from vector spaces to sets. The factorial \(n!\) is replaced, in the \(q\)-analog
\[\left[ n\right] _{q}!=\left[ n\right] _{q}\left[ n-1\right] _{q}…\left[ 1\right] _{q},\] where \(\left[ 1\right] _{q}=\left[ 0\right] _{q}=1\).
To obtain the Gaussian binomial coefficients we calculate with ordered bases of a \(k\)-dimensional subspace of an \(n\)-dimensional vector space over the finite field \(GF\left( q\right)\) with \(q\) elements. There are \(q^{n}\) elements in the space so the first choice for a basis vector has \(\left( q^{n}-1\right)\) (excluding \(0\)) possibilities, and since that vector generated a subspace of dimension \(q\), the choice of the second basis vector is limited to \(\left( q^{n}-q\right)\) elements, and so forth. Thus:
\[\begin{aligned} \left( q^{n}-1\right) \left( q^{n}-q\right) \left( q^{n}-q^{2}\right) …\left( q^{n}-q^{k-1}\right)=&\left( q^{n}-1\right) q^{1}\left( q^{n-1}-1\right) q^{2}\left( q^{n-2}-1\right) …q^{k-1}\left( q^{n-k+1}-1\right)\\ =&\frac{\left[ n\right] _{q}!\left( q-1\right) ^{k}}{\left[ n-k\right] _{q}!}q^{\left( 1+2+…+\left( k-1\right) \right) }\\ =&\frac{\left[ n\right] _{q}!\left( q-1\right) ^{k}}{\left[ n-k\right] _{q}!}q^{k\left( k-1\right) /2}\\ =&\frac{\left[ n\right] _{q}!\left( q-1\right) ^{k}}{\left[ n-k\right] _{q}!}q^{\binom{k}{2}}. \end{aligned}\]
Number of ordered bases for a \(k\)-dimensional subspace in an \(n\)-dimensional space.
But for a space of dimension \(k\), the number of ordered bases are: \[\begin{aligned} \left( q^{k}-1\right) \left( q^{k}-q\right) \left( q^{k}-q^{2}\right) …\left( q^{k}-q^{k-1}\right)=&\left( q^{k}-1\right) q^{1}\left( q^{k-1}-1\right) q^{2}\left( q^{k-2}-1\right) …q^{k-1}\left( q^{k-k+1}-1\right)\\ =&\left[ k\right] _{q}!\left( q-1\right) ^{k}q^{k\left( k-1\right) /2}=\left[ k\right] _{q}!\left( q-1\right) ^{k}q^{\binom{k}{2}}. \end{aligned}\]
Number of ordered bases for a \(k\)-dimensional space.
Thus the number of subspaces of dimension \(k\) is the ratio: \[\binom{n}{k}_{q}=\frac{\left[ n\right] _{q}!\left( q-1\right) ^{k}q^{k\left( k-1\right) /2}}{\left[ n-k\right] _{q}!\left[ k\right] _{q}!\left( q-1\right) ^{k}q^{k\left( k-1\right) /2}}=\frac{\left[ n\right] _{q}!}{\left[ n-k\right] _{q}!\left[ k\right] _{q}!}.\]
Gaussian binomial coefficient where \(\binom{n}{k}_{q}\rightarrow\binom{n}{k}\) as \(q\rightarrow1\), i.e., the number of \(k\)-dimensional subspaces \(\rightarrow\) number of \(k\)-element subsets. Many classical identities for binomial coefficients generalize to Gaussian binomial coefficients [7].
Two subspaces of a vector space are said to be disjoint if their intersection is the zero subspace \(0\). A direct-sum decomposition (DSD) of a finite-dimensional vector space \(V\) over a base field \(F\) is a set of (nonzero) pair-wise disjoint subspaces, called blocks (as with partitions), \(\left\{ V_{i}\right\} _{i=1,…,m}\) that span the space. Then each vector \(v\in V\) has a unique expression \(v=\sum\limits_{i=1}^{m}v_{i}\) with each \(v_{i}\in V_{i}\). Since a direct-sum decomposition can be seen as the vector-space version of a set partition, we begin with counting the number of partitions on a set.
Each set partition \(\left\{ B_{1},…,B_{m}\right\}\) of an \(n\)-element set has a “type” or “signature” number partition giving the cardinality of the blocks where they might be presented in nondecreasing order which we can assume to be: \(\left( \left\vert B_{1}\right\vert ,\left\vert B_{2} \right\vert ,…,\left\vert B_{m}\right\vert \right)\) which is a number partition of \(n\). For our purposes, there is another way to present number partitions, the part-count representation, where \(a_{k}\) is the number of times the integer \(k\) occurs in the number partition (and \(a_{k}=0\) if \(k\) does not appear) so that: \[a_{1}1+a_{2}2+…+a_{n}n=\sum\limits_{k=1}^{n}a_{k}k=n.\]
Part-count representation of number partitions keeping track of repetitions.
Each set partition \(\left\{ B_{1},…,B_{m}\right\}\) of an \(n\)-element set has a part-count signature \(a_{1},…,a_{n}\), and then there is a “classical” formula for the number of partitions with that signature ([10, p. 215]; [11, p. 427]).
Proposition 1. The number of set partitions for the given signature: \(a_{1},…,a_{n}\) where \(\sum\limits_{k=1}^{n}a_{k}k=n\) is:
\[\frac{n!}{a_{1}!a_{2}!…a_{n}!\left( 1!\right) ^{a_{1}}\left( 2!\right) ^{a_{2}}…\left( n!\right) ^{a_{n}}}.\]
Proof. Suppose we count the number of set partitions \(\left\{ B_{1},…,B_{m}\right\}\) of an \(n\)-element set when the blocks have the given cardinalities: \(n_{j}=\left\vert B_{j}\right\vert\) for \(j=1,…,m\) so \(\sum\limits_{j=1}^{m}n_{j}=n\). The first block \(B_{1}\) can be chosen in \(\binom {n}{n_{1}}\) ways, the second block in \(\binom{n-n_{1}}{n_{2}}\) ways and so forth, so the total number of ways is: \[\begin{aligned} \binom{n}{n_{1}}\binom{n-n_{1}}{n_{2}}…\binom{n-n_{1}-…-n_{m-1}}{n_{m} }=&\frac{n!}{n_{1}!\left( n-n_{1}\right) !}\frac{\left( n-n_{1}\right) !}{n_{2}!\left( n-n_{1}-n_{2}\right) !}…\frac{\left( n-n_{1}% -…-n_{m-1}\right) !}{n_{m}!\left( n-n_{1}-…-n_{m}\right) !}\\ =&\frac{n!}{n_{1}!…n_{m}!}=\binom{n}{n_{1},…,n_{m}}, \end{aligned}\] the multinomial coefficient. This formula can then be restated in terms of the part-count signature \(a_{1},…,a_{n}\) where \(\sum\limits_{k=1}^{n} a_{k}k=n\) as: \(\frac{n!}{\left( 1!\right) ^{a_{1}}\left( 2!\right) ^{a_{2}}…\left( n!\right) ^{a_{n}}}\). But that overcounts since the \(a_{k}\) blocks of size \(k\) can be permuted without changing the partition’s signature so one needs to divide by \(a_{k}!\) for \(k=1,…,n\) which yields the formula for the number of partitions with that signature. ◻
The Stirling numbers \(S\left( n,m\right)\) of the second kind are the number of partitions of an \(n\)-element set with \(m\) blocks. Since \(\sum\limits_{k=1}^{n}a_{k}=m\) is the number of blocks, the direct formula (as opposed to a recurrence formula) is: \[S\left( n,m\right) ={\textstyle\sum\limits_{\substack{1a_{1}+2a_{2}+…+na_{n}=n\\a_{1} +a_{2}+…+a_{n}=m}}} \frac{n!}{a_{1}!a_{2}!…a_{n}!\left( 1!\right) ^{a_{1}}\left( 2!\right) ^{a_{2}}…\left( n!\right) ^{a_{n}}}.\]
Direct formula for Stirling numbers of the second kind.
The Bell numbers \(B\left( n\right)\) are the total number of partitions on an \(n\)-element set so the direct formula is: \[B\left( n\right) =\sum\limits_{m=1}^{n}S\left( n,m\right) = {\textstyle\sum\limits_{1a_{1}+2a_{2}+…+na_{n}=n}} \frac{n!}{a_{1}!a_{2}!…a_{n}!\left( 1!\right) ^{a_{1}}\left( 2!\right) ^{a_{2}}…\left( n!\right) ^{a_{n}}}.\]
Direct formula for total number of partitions of an \(n\)-element set.
Each DSD \(\pi=\left\{ V_{i}\right\} _{i=1,…,m}\) of a finite vector space of dimension \(n\) also determines a number partition of \(n\) using the dimensions \(n_{i}=\dim\left( V_{i}\right)\) in place of the set cardinalities, and thus each DSD also has a signature \(a_{1},…,a_{n}\) where the subspaces are ordered by nondecreasing dimension and where \(\sum\limits_{k=1}% ^{n}a_{k}k=n\) and \(\sum\limits_{k=1}^{n}a_{k}=m\).
Proposition 2. The number of DSDs of a vector space \(V\) of dimension \(n\) over \(GF\left( q\right)\) with the part-count signature \(a_{1},…,a_{n}\) is:
\[\frac{1}{a_{1}!a_{2}!…a_{n}!}\frac{\left[ n\right] _{q}!}{\left( \left[ 1\right] _{q}!\right) ^{a_{1}}…\left( \left[ n\right] _{q}!\right) ^{a_{n}}}q^{\frac{1}{2}\left( n^{2}-\sum\limits_{k}a_{k}k^{2}\right)}.\]
Number of DSDs for the given signature \(a_{1},…,a_{n}\) where \(\sum\limits_{k=1}^{n}a_{k}k=n\).
Proof. Reasoning first in terms of the dimensions \(n_{i}\), we calculate the number of ordered bases in a subspace of dimension \(n_{1}\) of a vector space of dimension \(n\) over the finite field \(GF\left( q\right)\) with \(q\) elements. There are \(q^{n}\) elements in the space so the first choice for a basis vector is \(\left( q^{n}-1\right)\) (excluding \(0\)), and since that vector generates a 1-dimensional subspace, the choice of the second basis vector is limited to \(\left( q^{n}-q\right)\) elements, and so forth. Thus:
\[\begin{aligned} \left( q^{n}-1\right) \left( q^{n}-q\right) \left( q^{n}-q^{2}\right) …\left( q^{n}-q^{n_{1}-1}\right)=&\left( q^{n}-1\right) q^{1}\left( q^{n-1}-1\right) q^{2}\left( q^{n-1}-1\right) …q^{n_{1}-1}\left( q^{n-n_{1}+1}-1\right)\\ =&\left( q^{n}-1\right) \left( q^{n-1}-1\right) …\left( q^{n-n_{1} -1}-1\right) q^{\left( 1+2+…+\left( n_{1}-1\right) \right) }. \end{aligned}\]
Number of ordered bases for an \(n_{1}\)-dimensional subspace of an \(n\)-dimensional space.
If we then divide by the number of ordered bases for an \(n_{1}\)-dimension space: \[\left( q^{n_{1}}-1\right) \left( q^{n_{1}}-q\right) …\left( q^{n_{1} }-q^{n_{1}-1}\right) =\left( q^{n_{1}}-1\right) \left( q^{n_{1}% -1}-1\right) …\left( q-1\right) q^{\left( 1+2+…+\left( n_{1}% -1\right) \right) },\] we could cancel the \(q^{n_{1}\left( n_{1}-1\right) }\) terms to obtain the Gaussian binomial coefficient \[\frac{\left( q^{n}-1\right) \left( q^{n-1}-1\right) …\left( q^{n-n_{1}-1}-1\right) q^{\left( 1+2+…+\left( n_{1}-1\right) \right) } }{\left( q^{n_{1}}-1\right) \left( q^{n_{1}-1}-1\right) …\left( q-1\right) q^{\left( 1+2+…+\left( n_{1}-1\right) \right) }}=\binom {n}{n_{1}}_{q}=\frac{\left[ n\right] _{q}!}{\left[ n-n_{1}\right] _{q}!\left[ n_{1}\right] _{q}!}.\]
Number of different \(n_{1}\)-dimensional subspaces of an \(n\)-dimensional space.
If instead we continue to develop the numerator by multiplying by the number of ordered bases for an \(n_{2}\)-dimensional space that could be chosen from the remaining space of dimension \(n-n_{1}\) to obtain: \[\begin{aligned} \left( q^{n}-1\right) & \left( q^{n}-q\right) \left( q^{n}-q^{2}\right) …\left( q^{n}-q^{n_{1}-1}\right) \times\left( q^{n}-q^{n_{1}}\right) \left( q^{n}-q^{n_{1}+1}\right) …\left( q^{n}-q^{n_{1}+n_{2}-1}\right)\\ &=\left( q^{n}-1\right) \left( q^{n-1}-1\right) …\left( q^{n-n_{1} -n_{2}+1}-1\right) q^{\left( 1+2+…+\left( n_{1}+n_{2}-1\right) \right) }. \end{aligned}\]
Then dividing by the number of ordered bases of an \(n_{1}\)-dimensional space times the number of ordered bases of an \(n_{2}\)-dimensional space gives the number of different “disjoint” (i.e., only overlap is zero subspace) subspaces of \(n_{1}\)-dimensional and \(n_{2}\)-dimensional subspaces. \[=\frac{\left( q^{n}-1\right) \left( q^{n-1}-1\right) …\left( q^{n-n_{1}-n_{2}+1}-1\right) q^{\left( 1+2+…+\left( n_{1}+n_{2}-1\right) \right) }}{\left( q^{n_{1}}-1\right) \left( q^{n_{1}-1}-1\right) …\left( q-1\right) q^{\left( 1+2+…+\left( n_{1}-1\right) \right) }\times\left( q^{n_{2}}-1\right) \left( q^{n_{2}-1}-1\right) …\left( q-1\right) q^{1+2+…+\left( n_{2}-1\right) }}.\]
Continuing inductively, after choosing ordered basis sets for subspaces of dimensions \(n_{1},…,n_{j-1}\) whose internal direct sum has dimension \(n_{1}+…+n_{j-1}\), the next basis vector for the \(j\)th subspace must lie outside that already chosen sum, and the same counting pattern applies. Thus the product above generalizes to the number of ordered \(m\)-tuples \(\left( V_{1},…,V_{m}\right)\) of pairwise disjoint subspaces with \(\dim V_{i}=n_{i}\) and \(\bigoplus_{i=1}^{m}V_{i}=V\). Equivalently, we are counting ordered decompositions with prescribed dimension sequence \(\left( n_{1},…,n_{m}\right)\), so no additional overcounting occurs at this stage.
\[\begin{aligned} \frac{\left( q^{n}-1\right) \left( q^{n-1}-1\right) …\left( q-1\right) q^{\left( 1+2+…+\left( n-1\right) \right) }}{\prod \limits_{i=1,…,m}\left( q^{n_{i}}-1\right) \left( q^{n_{i}-1}-1\right) …\left( q-1\right) q^{\left( 1+2+…+\left( n_{i}-1\right) \right) } }=&\frac{\left[ n\right] _{q}!q^{n\left( n-1\right) /2}}{\left[ n_{1}\right] _{q}!q^{n_{1}\left( n_{1}-1\right) /2}\times…\times\left[ n_{m}\right] _{q}!q^{n_{m}\left( n_{m}-1\right) /2}}\\ =&\frac{\left[ n\right] _{q}!}{\left[ n_{1}\right] _{q}!…\left[ n_{m}\right] _{q}!}q^{\frac{1}{2}\left[ n\left( n-1\right) -\sum\limits_{i=1} ^{m}n_{i}\left( n_{i}-1\right) \right] }. \end{aligned}\]
There may be a number \(a_{k}\) of subspaces with the same dimension, e.g., if \(n_{j}=n_{j+1}=k\), then \(a_{k}=2\) so the term \(\left[ n_{j}\right] _{q}!q^{n_{j}\left( n_{j}-1\right) /2}\times\left[ n_{j+1}\right] _{q}!q^{n_{j+1}\left( n_{j+1}-1\right) /2}\) in the denominator could be replaced by \(\left( \left[ k\right] _{q}!\right) ^{a_{k}}q^{a_{k}k\left( k-1\right) /2}\). Hence the previous result could be rewritten in the part-count representation: \[\frac{\left[ n\right] _{q}!}{\left( \left[ 1\right] _{q}!\right) ^{a_{1}}…\left( \left[ n\right] _{q}!\right) ^{a_{n}}}q^{\frac{1} {2}\left[ n\left( n-1\right) -\sum\limits_{k}a_{k}k\left( k-1\right) \right] }.\]
And permuting subspaces of the same dimension \(k\) yields a DSD with the same signature, so we need to divide by \(a_{k}!\) for each \(k\). Since this is the only remaining symmetry after fixing the multiset of dimensions, the quotient counts each DSD with the prescribed signature exactly once: \[\frac{\left[ n\right] _{q}!}{a_{1}!…a_{n}!\left( \left[ 1\right] _{q}!\right) ^{a_{1}}…\left( \left[ n\right] _{q}!\right) ^{a_{n}} }q^{\frac{1}{2}\left[ n\left( n-1\right) -\sum\limits_{k}a_{k}k\left( k-1\right) \right] }.\]
The exponent on the \(q\) term can be simplified since \(\sum\limits_{k} a_{k}k=n\): \[\begin{aligned} \frac{1}{2}\left[ n\left( n-1\right) -\left( \sum\limits_{k}a_{k}k\left( k-1\right) \right) \right] =&\frac{1}{2}\left[ n^{2}-n-\left( \sum _{k}a_{k}k^{2}-\sum\limits_{k}a_{k}k\right) \right]\\ =&\frac{1}{2}\left[ n^{2}-n-\left( \sum\limits_{k}a_{k}k^{2}-n\right) \right]\\ =&\frac{1}{2}\left( n^{2}-\sum\limits_{k}a_{k}k^{2}\right). \end{aligned}\]
This yields the final formula for the number of DSDs with the part-count signature \(a_{1},…,a_{n}\): \[\frac{\left[ n\right] _{q}!}{a_{1}!…a_{n}!\left( \left[ 1\right] _{q}!\right) ^{a_{1}}…\left( \left[ n\right] _{q}!\right) ^{a_{n}} }q^{\frac{1}{2}\left( n^{2}-\sum\limits_{k}a_{k}k^{2}\right) }.\] ◻
Note that the formula is not obtained by a simple substitution of \(\left[ k\right] _{q}!\) for \(k!\) in the set partition formula due to the extra term \(q^{\frac{1}{2}\left( n^{2}-\sum\limits_{k}a_{k}k^{2}\right) }\), but that it still reduces to the classical formula for set partitions with that signature as \(q\rightarrow1\). This formula leads directly to the vector space version of the Stirling numbers of the second kind to count the DSDs with \(m\) parts and to the vector space version of the Bell numbers to count the total number of DSDs.
Before giving those formulas, it should be noted that there is another \(q\)-analog formula called “generalized Stirling numbers” (of the second kind)–but it generalizes only one of the recurrence formulas for \(S\left( n,m\right)\). It does not generalize the interpretation “number of set partitions on an \(n\)-element set with \(m\) parts” to count the vector space partitions (DSDs) of finite vector spaces of dimension \(n\) with \(m\) parts. The Stirling numbers satisfy the recurrence formula:
\(S\left( n+1,m\right) =mS\left( n,m\right) +S\left( n,m-1\right)\) with \(S\left( 0,m\right) =\delta_{0m}\).
Donald Knuth uses the braces notation for the Stirling numbers, \(\genfrac{\{}{\}}{0pt}{}{n}{m} =S\left( n,m\right)\), and then he defines the “generalized Stirling number” [11, p.436] \(\genfrac{\{}{\}}{0pt}{}{n}{m}_{q}\) by the \(q\)-analog recurrence relation: \[\genfrac{\{}{\}}{0pt}{}{n+1}{m}_{q}=\left( 1+q+…+q^{m-1}\right)\genfrac{\{}{\}}{0pt}{}{n}{m}_{q}+\genfrac{\{}{\}}{0pt}{}{n}{m-1}_{q}; \genfrac{\{}{\}}{0pt}{}{0}{m}_{q}=\delta_{0m}.\]
It is easy to generalize the direct formula for the Stirling numbers, and this formula generalizes the set-partition interpretation to vector-space partitions. This formula itself is not claimed as new here; rather, the point is to present an elementary signature-based derivation and notation that can be used later for the designated-vector extensions: \[D_{q}\left( n,m\right) ={\textstyle\sum\limits_{\substack{1a_{1}+2a_{2}+…+na_{n}=n\\a_{1}+a_{2}+…+a_{n}=m}}}\frac{\left[ n\right] _{q}!}{a_{1}!…a_{n}!\left( \left[ 1\right] _{q}!\right) ^{a_{1}}…\left( \left[ n\right] _{q}!\right) ^{a_{n}}% }q^{\frac{1}{2}\left( n^{2}-\sum\limits_{k}a_{k}k^{2}\right) }.\]
Number of DSDs of a finite vector space of dimension \(n\) over \(GF\left( q\right)\) with \(m\) parts.
The number \(D_{q}\left( n,m\right)\) is \(S_{nm}\) in [9]. Taking \(q\rightarrow1\) yields the Stirling numbers of the second kind, i.e., \(D_{1}\left( n,m\right) =S\left( n,m\right)\). Knuth’s generalized Stirling numbers \(\genfrac{\{}{\}}{0pt}{}{n}{m}_{q}\) and \(D_{q}\left( n,m\right)\) start off the same, e.g., \(\genfrac{\{}{\}}{0pt}{}{0}{0}_{q}=1=D_{q}\left( 0,0\right)\) and \(\genfrac{\{}{\}}{0pt}{}{1}{1}_{q}=1=D_{q}\left( 1,1\right)\), but then quickly diverge. For instance, all \(\genfrac{\{}{\}}{0pt}{}{n}{n}_{q}=1\) for all \(n\), whereas the special case of \(D_{q}(n,n)\) is the number of DSDs of \(1\)-dimensional subspaces in a finite vector space of dimension \(n\) over \(GF\left( q\right)\) (see table below for \(q=2\)). The formula \(D_{q}\left( n,n\right)\) is \(M\left( n\right)\) in [12, Example 5.5.2(b), pp. 45-6] or [9, Example 2.2, p. 75].
The number \(D_{q}(n,n)\) of DSDs of \(1\)-dimensional subspaces is closely related to the number of basis sets. The old formula for that number of bases is [13,p. 71]: \[\begin{aligned} \frac{1}{n!}\left( q^{n}-1\right) \left( q^{n}-q\right) …\left( q^{n}-q^{n-1}\right)=&\frac{1}{n!}\left( q^{n}-1\right) \left( q^{n-1}-1\right) …(q^{1}% -1)q^{\left( 1+2+…+\left( n-1\right) \right) }\\ =&\frac{1}{n!}\left[ n\right] _{q}!q^{\binom{n}{2}}\left( q-1\right) ^{n}, \end{aligned}\] since \(\left[ k\right] _{q}=\frac{q^{k}-1}{q-1}=1+q+q^{2}+…+q^{k-1}\) for \(k=1,…,n\).
In the formula for \(D_{q}\left( n,n\right)\), there is only one signature \(a_{1}=n\) and \(a_{k}=0\) for \(k=2,…,n\) which immediately gives the formula for the number of DSDs with \(n\) \(1\)-dimensional blocks and each \(1\) -dimensional block has \(q-1\) choices for a basis vector so the total number of sets of basis vectors is given by the same formula: \[D_{q}\left( n,n\right) \left( q-1\right) ^{n}=\frac{\left[ n\right] _{q}!}{a_{1}!}q^{\frac{1}{2}\left( n^{2}-a_{1}1^{2}\right) }\left( q-1\right) ^{n}=\frac{1}{n!}\left[ n\right] _{q}!q^{\binom{n}{2}}\left( q-1\right) ^{n}.\]
Note that for \(q=2\), \(\left( q-1\right) ^{n}=1\) so \(D_{2}\left( n,n\right)\) is the number of different basis sets.
Summing the \(D_{q}\left( n,m\right)\) for all \(m\) gives the vector space version of the Bell numbers \(B\left( n\right)\): \[D_{q}\left( n\right) =\sum\limits_{m=1}^{n}D_{q}\left( n,m\right) ={\textstyle\sum\limits_{1a_{1}+2a_{2}+…+na_{n}=n}} \frac{1}{a_{1}!a_{2}!…a_{n}!}\frac{\left[ n\right] _{q}!}{\left( \left[ 1\right] _{q}!\right) ^{a_{1}}…\left( \left[ n\right] _{q}!\right) ^{a_{n}}}q^{\frac{1}{2}\left( n^{2}-\sum\limits_{k}a_{k}k^{2}\right) }.\]
Number of DSDs of a vector space of dimension \(n\) over \(GF\left( q\right)\).
Our notation \(D_{q}\left( n\right)\) is \(D_{n}\left( q\right)\) in Bender and Goldman [8] and \(\left\vert Q_{n}\right\vert\) in Stanley ([9], [12]). Setting \(q=1\) gives the Bell numbers, i.e., \(D_{1}\left( n\right) =B\left( n\right)\).
Set partitions have a property not shared by vector space partitions, i.e., DSDs. Given a designated element \(u^{\ast}\) of the universe set \(U\), the element is contained in some block of every partition on \(U\). But given a nonzero vector \(v^{\ast}\) in a space \(V\), it is not necessarily contained in a block of any given DSD of \(V\). Some proofs of formulas use this property of set partitions so the proofs do not generalize to DSDs.
Consider one of the formulas for the Stirling numbers of the second kind: \[S\left( n,m\right) =\sum\limits_{k=0}^{n-1}\binom{n-1}{k}S\left( k,m-1\right).\]
Summation formula for \(S\left( n,m\right)\).
The proof using the designated-element \(u^{\ast}\) reasoning starts with the fact that any partition of \(U\) with \(\left\vert U\right\vert =n\) with \(m\) blocks will have one block containing \(u^{\ast}\) so we then only need to count the number of \(m-1\) blocks on the subset disjoint from the block containing \(u^{\ast}\). If the block containing \(u^{\ast}\) had \(n-k\) elements, there are \(\binom{n-1}{k}\) blocks that could be complementary to an \(\left( n-k\right)\)-element block containing \(u^{\ast}\) and each of those \(k\)-element blocks had \(S\left( k,m-1\right)\) partitions on it with \(m-1\) blocks. Hence the total number of partitions on an \(n\)-element set with \(m\) blocks is that sum.
This reasoning can be extended to DSDs over finite vector spaces, but it only counts the number of DSDs with a block containing a designated nonzero vector \(v^{\ast}\) (it doesn’t matter which one), not all DSDs. Furthermore, it is not a simple matter of substituting \(\binom{n-1}{k}_{q}\) for \(\binom{n-1}{k}\). Each \(\left( n-k\right)\)-element subset has a unique \(k\)-element subset disjoint from it (its complement), but the same does not hold in general vector spaces. Thus given a subspace with \(\left( n-k\right)\)-dimensions, we must compute the number of \(k\)-dimensional subspaces disjoint from it.
Let \(V\) be an \(n\)-dimensional vector space over \(GF\left( q\right)\) and let \(v^{\ast}\) be a specific nonzero vector in \(V\). In a DSD with an \(\left( n-k\right)\)-dimensional block containing \(v^{\ast}\), how many \(k\) -dimensional subspaces are there disjoint from the \(\left( n-k\right)\)-dimensional subspace containing \(v^{\ast}\)? The number of ordered basis sets for a \(k\)-dimensional subspace disjoint from the given \(\left( n-k\right)\)-dimensional space is: \[\begin{aligned} \left( q^{n}-q^{n-k}\right) \left( q^{n}-q^{n-k+1}\right) …\left( q^{n}-q^{n-1}\right) =&\left( q^{k}-1\right) q^{n-k}\left( q^{k-1} -1\right) q^{n-k+1}…\left( q-1\right) q^{n-1}\\ =&\left( q^{k}-1\right) \left( q^{k-1}-1\right) …\left( q-1\right) q^{\left( n-k\right) +\left( n-k+1\right) +…+\left( n-1\right) }\\ =&\left( q^{k}-1\right) \left( q^{k-1}-1\right) …\left( q-1\right) q^{k\left( n-k\right) +\frac{1}{2}k\left( k-1\right) }, \end{aligned}\] since we use the usual trick to evaluate twice the exponent: \[\begin{aligned} \left( n-k\right) +\left( n-k+1\right) +…+\left( n-1\right)+\underline{\left( n-1\right) +\left( n-2\right) +…+\left( n-k\right) }=&\left( 2n-k-1\right) +…+\left( 2n-k-1\right) \\ =&k\left( 2n-k-1\right)\\ =&2k\left( k+\left( n-k\right) \right) -k^{2}-k\\ =&2k\left( n-k\right) +k^{2}-k. \end{aligned}\]
Now the number of ordered basis set of a \(k\)-dimensional space is: \[\left( q^{k}-1\right) \left( q^{k-1}-1\right) …\left( q-1\right) q^{\frac{1}{2}k\left( k-1\right) },\] so dividing by that gives: \[q^{k\left( n-k\right) }.\]
The number of \(k\)-dimensional subspaces disjoint from any \(\left( n-k\right)\)-dimensional subspace.1
Note that taking \(q\rightarrow1\) yields the fact that an \(\left( n-k\right)\)-element subset of an \(n\)-element set has a unique \(k\)-element subset disjoint from it.
Hence in the \(q\)-analog formula, the binomial coefficient \(\binom{n-1}{k}\) is replaced by the Gaussian binomial coefficient \(\binom {n-1}{k}_{q}\) times \(q^{k\left( n-k\right) }\). To make the counting step explicit, fix a DSD of \(V\) with \(m\) blocks such that one block \(B\) contains the designated vector \(v^{\ast}\), and suppose \(\dim B=n-k\). Then \(B\) is obtained by choosing an \(\left( n-k\right)\)-dimensional subspace containing \(v^{\ast}\), equivalently a \(k\)-dimensional subspace of \(V/\left\langle v^{\ast}\right\rangle\), which can be done in \(\binom{n-1}{k}_{q}\) ways. For each such \(B\), the preceding calculation shows that there are exactly \(q^{k\left( n-k\right) }\) \(k\)-dimensional subspaces \(W\) disjoint from \(B\); each such \(W\) is a complement of \(B\) and any DSD of \(W\) with \(m-1\) blocks extends uniquely to a DSD of \(V\) by adjoining \(B\). Conversely, every DSD counted by \(D_{q}^{\ast}\left( n,m\right)\) determines a unique value of \(k\), a unique block \(B\) containing \(v^{\ast}\), a unique complementary \(k\)-dimensional subspace \(W\), and a DSD of \(W\) with \(m-1\) blocks. Summing over \(k\) yields the proposition below. Let \(D_{q}^{\ast}\left( n,m\right)\) denote the number of DSDs of \(V\) with \(m\) blocks with one block containing any designated \(v^{\ast}\).
Proposition 3. Given a designated nonzero vector \(v^{\ast}\in V\), the number of DSDs of \(V\) with \(m\) blocks one of which contains \(v^{\ast}\) is: \[D_{q}^{\ast}\left( n,m\right) =\sum\limits_{k=0}^{n-1} \binom{n-1}{k}_{q}q^{k\left( n-k\right) }D_{q}\left( k,m-1\right).\]
Note that it is \(D_{q}\left( k,m-1\right)\), and not \(D_{q}^{\ast }\left( k,m-1\right)\), on the right-hand side of the formula. Further note that \(D_{q}^{\ast}\left( n,m\right)\) is the \(q\)-analog of Stirling numbers of second kind \(S\left( n,m\right)\) in the sense that taking \(q=1\) gives the right-hand side of: \(\sum\limits_{k=0}^{n-1}\binom{n-1}{k}S\left( k,m-1\right)\) since \(D_{1}\left( k,m-1\right) =S\left( k,m-1\right)\), and the left-hand side is the same as \(S\left( n,m\right)\) since every set partition of an \(n\)-element with \(m\) blocks has to have a block containing some designated element \(u^{\ast}\). Thus both \(D_{q}\left( n,m\right)\) and \(D_{q}^{\ast}\left( n,m\right)\) can be seen as \(q\)-analogs of the Stirling numbers \(S\left( n,m\right)\).
Since the Bell numbers can be obtained from the Stirling numbers of the second time as: \(B\left( n\right) =\sum\limits_{m=1}^{n}S\left( n,m\right)\), there is clearly a similar formula for the Bell numbers: \[B\left( n\right) =\sum\limits_{k=0}^{n-1}\binom{n-1}{k}B\left( k\right).\]
Summation formula for \(B\left( n\right)\).
This formula can also be directly proven using the designated-element \(u^{\ast}\) reasoning. In the vector-space case, one may either repeat the same argument with \(B\left( k\right)\) replaced by \(D_{q}\left( k\right)\) and the factor \(\binom{n-1}{k}_{q}q^{k\left( n-k\right) }\), or sum the previous proposition over \(m\) and use \(D_{q}\left( k\right) =\sum\limits_{r=1}^{k}D_{q}\left( k,r\right)\). This yields the count \(D_{q}^{\ast}\left( n\right)\) of DSDs of \(V\) with a block containing a designated nonzero vector \(v^{\ast}\).
Proposition 4. Given any designated nonzero vector \(v^{\ast}\in V\), the number of DSDs of \(V\) with a block containing \(v^{\ast}\) is:
\[D_{q}^{\ast}\left( n\right) =\sum\limits_{k=0}^{n-1}\,\,\binom{n-1}{k}_{q}q^{k\left( n-k\right) }D_{q}\left( k\right).\]
Note that \(D_{q}^{\ast}\left( n\right)\) is the \(q\)-analog of the Bell numbers \(B\left( n\right)\) in the sense that taking \(q=1\) yields the classical summation formula for \(B\left( n\right)\) since \(D_{1}\left( k\right) =B\left( k\right)\) and every partition has to have a block containing a designated element \(u^{\ast}\). Thus both \(D_{q}\left( n\right)\) and \(D_{q}^{\ast}\left( n\right)\) can be seen as \(q\)-analogs of the Bell numbers \(B\left( n\right)\).
Furthermore the \(D^{\ast}\) numbers have the expected relation:
Corollary 1. \(D_{q}^{\ast}(n)=\sum\limits_{m=1}^{n}D_{q}^{\ast}\left( n,m\right)\).
Since we also have formulas for the total number of DSDs, we have the number of DSDs where the designated element is not in one of the blocks: \(D_{q}\left( n,m\right) -D_{q}^{\ast}\left( n,m\right)\) and \(D_{q}\left( n\right) -D_{q}^{\ast}\left( n\right)\).
For a natural interpretation for the \(D^{\ast}\)-numbers, consider the pedagogical model of quantum mechanics using finite-dimensional vector spaces \(V\) over \(GF\left( 2\right) =\mathbb{Z}_{2}\), called “quantum mechanics over sets,” QM/Sets [15]. The “observables” or attributes are defined by real-valued functions on basis sets. Given a basis set \(U=\left\{ u_{1},…,u_{n}\right\}\) for \(V=\mathbb{Z}_{2}^{n}\cong\wp\left( U\right)\), a real-valued attribute is a function \(f:U\rightarrow\mathbb{R}\). It determines a set partition \(\left\{ f^{-1}\left( r\right) \right\}_{r\in f\left( U\right) }\) on \(U\) and a DSD \(\left\{ \wp\left(f^{-1}\left( r\right) \right) \right\} _{r\in f\left( U\right) }\) on \(\wp\left( U\right)\). In full QM, the important thing about an “observable” is not the specific numerical eigenvalues, but its eigenspaces for distinct eigenvalues, and that information is in the DSD of its eigenspaces. The attribute \(f:U\rightarrow\mathbb{R}\) cannot be internalized as an operator on \(\wp\left( U\right) \cong\mathbb{Z}_{2}^{n}\) (unless its values are \(0,1\)), but it nevertheless determines the DSD \(\left\{ \wp\left( f^{-1}\left( r\right) \right) \right\} _{r\in f\left( U\right) }\) which is sufficient to pedagogically model many quantum results. Hence a DSD can be thought of an “abstract attribute” (without the eigenvalues) with its blocks serving as “eigenspaces.” Then a natural question to ask is given any nonzero vector \(v^{\ast}\in V=\mathbb{Z}_{2}^{n}\), how many “abstract attributes” are there where \(v^{\ast}\) is an “eigenvector”–and the answer is \(D_{2}^{\ast}\left( n\right)\). And \(D_{2}^{\ast}\left( n,m\right)\) is the number of “abstract attributes” with \(m\) distinct “eigenvalues” where \(v^{\ast}\) is an “eigenvector.”
In the case of \(n=1,2,3\), the DSDs can be enumerated “by hand” to check the formulas, and then the formulas can be used to compute higher values of \(D_{2}\left( n,m\right)\) or \(D_{2}\left( n\right)\).
The numerical tables reported below were generated directly from the formulas in this paper (the signature sum for \(D_{q}\left( n,m\right)\) and the recurrence formulas for \(D_{q}^{\ast}\left( n,m\right)\) and \(D_{q}^{\ast} \left( n\right)\)). For consistency, the computations were checked against three independent criteria: (i) explicit hand enumerations for \(n\leq3\), (ii) row-sum identities such as \(D_{2}\left( n\right) =\sum\limits_{m}D_{2}\left( n,m\right)\) and \(D_{2}^{\ast}\left( n\right) =\sum\limits_{m}D_{2}^{\ast}\left( n,m\right)\), and (iii) the specialization \(D_{2}\left( n,n\right) =\) the known number of unordered bases of \(\mathbb{Z}_{2}^{n}\).
All vectors in the \(n\)-dimensional vector space \(\mathbb{Z}_{2}^{n}\) over \(GF\left( 2\right) =\mathbb{Z}_{2}\) will be expressed in terms of a computational basis \(\left\{ a\right\},\left\{ b\right\} ,…,\left\{ c\right\}\) so any vector \(S\) in \(\mathbb{Z}_{2}^{n}\) would be represented in that basis as a subset \(S\subseteq U=\left\{ a,b,…,c\right\}\). The addition of subsets (expressed in the same basis) is the symmetric difference: for \(S,T\subseteq U\), \[S+T=\left( S-T\right) \cup\left( T-S\right) =\left( S\cup T\right) -\left( S\cap T\right) .\]
Since all subspaces contain the zero element which is the empty set \(\emptyset\), it will be usually suppressed when listing the elements of a subspace. And subsets like \(\left\{ a\right\}\) or \(\left\{ a,b\right\}\) will be denoted as just \(a\) and \(ab\). Thus the subspace \(\left\{ \emptyset,\left\{ a\right\} ,\left\{ b\right\} ,\left\{ a,b\right\} \right\}\) is denoted as \(\left\{ a,b,ab\right\}\). A \(k\)-dimensional subspace has \(2^{k}\) elements so only \(2^{k}-1\) are listed.
For \(n=1\), there is only one nonzero subspace \(\left\{ a\right\}\), i.e., \(\left\{ \emptyset,\left\{ a\right\} \right\}\), and \(D_{2}\left( 1,1\right) =D_{2}\left( 1\right) =1\).
For \(n=2\), the whole subspace is \(\left\{ a,b,ab\right\}\) and it has three bases \(\left\{ a,b\right\}\), \(\left\{ a,ab\right\}\), and \(\left\{ b,ab\right\}\). The formula for the number of bases gives \(D_{2}\left( 2,2\right) =3\). The only \(D_{2}\left( 2,1\right) =1\) DSD is the whole space.
For \(n=3\), the whole space \(\left\{ a,b,c,ab,ac,bc,abc\right\}\) is the only \(D_{2}\left( 3,1\right) =1\) and indeed for any \(n\) and \(q\), \(D_{q}\left( n,1\right) =1\). For \(n=3\) and \(m=3\), \(D_{2}\left( 3,3\right)\) is the number of (unordered) bases of \(\mathbb{Z}_{2}^{3}\) (recall \(\genfrac{\{}{\}}{0pt}{}{n}{n}_{q}=1\) for all \(q\)). Since we know the signature, i.e., \(a_{1}=3\) and otherwise \(a_{k}=0\), we can easily compute \(D_{2}\left( 3,3\right)\): \[\frac{1}{a_{1}!a_{2}!…a_{n}!}\frac{\left[ n\right] _{q}!}{\left( \left[ 1\right] _{q}!\right) ^{a_{1}}…\left( \left[ n\right] _{q}!\right) ^{a_{n}}}q^{\frac{1}{2}\left( n^{2}-\sum\limits_{k}a_{k}k^{2}\right) } =\frac{1}{3!}\frac{\left[ 3\right] _{2}!}{\left( \left[ 1\right] _{2}\right) ^{3}}2^{\frac{1}{2}\left( 3^{2}-3\right) }=\frac{1}{6} \frac{7\times3}{1}2^{\frac{1}{2}\left( 6\right) }=28=D_{2}(3,3).\]
And here they are.
| \(\left\{ a,b,c\right\}\) | \(\left\{ a,b,ac\right\}\) | \(\left\{ a,b,bc\right\}\) | \(\left\{ a,b,abc\right\}\) |
|---|---|---|---|
| \(\left\{ a,c,ab\right\}\) | \(\left\{ a,c,bc\right\}\) | \(\left\{ a,c,abc\right\}\) | \(\left\{ a,ab,ac\right\}\) |
| \(\left\{ a,ab,bc\right\}\) | \(\left\{ a,ab,abc\right\}\) | \(\left\{ a,ac,bc\right\}\) | \(\left\{ a,ac,abc\right\}\) |
| \(\left\{ b,c,ab\right\}\) | \(\left\{ b,c,ac\right\}\) | \(\left\{ b,c,abc\right\}\) | \(\left\{ b,ab,ac\right\}\) |
| \(\left\{ b,ab,bc\right\}\) | \(\left\{ b,ab,abc\right\}\) | \(\left\{ b,ac,bc\right\}\) | \(\left\{ b,bc,abc\right\}\) |
| \(\left\{ c,ab,ac\right\}\) | \(\left\{ c,ab,bc\right\}\) | \(\left\{ c,ac,bc\right\}\) | \(\left\{ c,ac,abc\right\}\) |
| \(\left\{ ab,ac,abc\right\}\) | \(\left\{ ab,bc,abc\right\}\) | \(\left\{ ac,bc,abc\right\}\) | \(\left\{ bc,ab,abc\right\}\) |
All bases of \(\mathbb{Z}_{2}^{3}\).
For \(n=3\) and \(m=2\), \(D_{2}\left( 3,2\right)\) is the number of binary DSDs, each of which has the signature \(a_{1}=a_{2}=1\) so the total number of binary DSDs is: \[D_{2}\left( 3,2\right) =\frac{1}{1!1!}\frac{\left[ 3\right] _{2} !}{\left( \left[ 1\right] !\right) ^{1}\left( \left[ 2\right] !\right) ^{1}}2^{\frac{1}{2}\left( 3^{2}-1-2^{2}\right) }=\frac{7\times3}{3} 2^{\frac{1}{2}\left( 4\right) }=7\times4=28.\]
And here they are:
| \(\left\{ \left\{ a\right\} ,\left\{ b,c,bc\right\} \right\}\) | \(\left\{ \left\{ a\right\} ,\left\{ ab,ac,bc\right\} \right\}\) | \(\left\{ \left\{ a\right\} ,\left\{ c,ab,abc\right\} \right\}\) | \(\left\{ \left\{ a\right\} ,\left\{ b,ac,abc\right\} \right\}\) |
|---|---|---|---|
| \(\left\{ \left\{ b\right\} ,\left\{ a,c,ac\right\} \right\}\) | \(\left\{ \left\{ b\right\} ,\left\{ ab,ac,bc\right\} \right\}\) | \(\left\{ \left\{ b\right\} ,\left\{ c,ab,abc\right\} \right\}\) | \(\left\{ \left\{ b\right\} ,\left\{ a,bc,abc\right\} \right\}\) |
| \(\left\{ \left\{ ab\right\} ,\left\{ b,c,bc\right\} \right\}\) | \(\left\{ \left\{ ab\right\} ,\left\{ a,bc,abc\right\} \right\}\) | \(\left\{ \left\{ ab\right\} ,\left\{ b,ac,abc\right\} \right\}\) | \(\left\{ \left\{ ab\right\} ,\left\{ a,c,ac\right\} \right\}\) |
| \(\left\{ \left\{ c\right\} ,\left\{ a,b,ab\right\} \right\}\) | \(\left\{ \left\{ c\right\} ,\left\{ ab,ac,bc\right\} \right\}\) | \(\left\{ \left\{ c\right\} ,\left\{ a,bc,abc\right\} \right\}\) | \(\left\{ \left\{ c\right\} ,\left\{ b,ac,abc\right\} \right\}\) |
| \(\left\{ \left\{ ac\right\} ,\left\{ a,b,ab\right\} \right\}\) | \(\left\{ \left\{ ac\right\} ,\left\{ a,bc,abc\right\} \right\}\) | \(\left\{ \left\{ ac\right\} ,\left\{ c,ab,abc\right\} \right\}\) | \(\left\{ \left\{ ac\right\} ,\left\{ b,c,bc\right\} \right\}\) |
| \(\left\{ \left\{ bc\right\} ,\left\{ a,b,ab\right\} \right\}\) | \(\left\{ \left\{ bc\right\} ,\left\{ b,ac,abc\right\} \right\}\) | \(\left\{ \left\{ bc\right\} ,\left\{ c,ab,abc\right\} \right\}\) | \(\left\{ \left\{ bc\right\} ,\left\{ a,c,ac\right\} \right\}\) |
| \(\left\{ \left\{ abc\right\} ,\left\{ a,b,ab\right\} \right\}\) | \(\left\{ \left\{ abc\right\} ,\left\{ b,c,bc\right\} \right\}\) | \(\left\{ \left\{ abc\right\} ,\left\{ a,c,ac\right\} \right\}\) | \(\left\{ \left\{ abc\right\} ,\left\{ ab,ac,bc\right\} \right\}\) |
All binary DSDs for \(\mathbb{Z}_{2}^{3}\).
The above table has been arranged to illustrate the result that any given \(k\)-dimensional subspaces has \(q^{k\left( n-k\right) }\) subspaces disjoint from it. For \(n=3\) and \(k=1\), each row gives the \(2^{2}=4\) subspaces disjoint from any given \(1\)-dimensional subspace represented by \(\left\{ a\right\}\), \(\left\{ b\right\}\),…, \(\left\{ abc\right\}\). For instance, the four subspaces disjoint from the subspace \(\left\{ ab\right\}\) (shorthand for \(\left\{ \emptyset,\left\{ a,b\right\} \right\}\)) are given in the third row since those are the “complementary” subspaces that together with \(\left\{ ab\right\}\) form a DSD.
For \(q=2\), the initial values up to \(n=6\) of \(D_{2}\left( n,m\right)\) are given in the following table.
| \(n\backslash m\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) |
|---|---|---|---|---|---|---|---|
| \(0\) | \(1\) | ||||||
| \(1\) | \(0\) | \(1\) | |||||
| \(2\) | \(0\) | \(1\) | \(3\) | ||||
| \(3\) | \(0\) | \(1\) | \(28\) | \(28\) | |||
| \(4\) | \(0\) | \(1\) | \(400\) | \(1,680\) | \(840\) | ||
| \(5\) | \(0\) | \(1\) | \(10,416\) | \(168,640\) | \(277,760\) | \(83,328\) | |
| \(6\) | \(0\) | \(1\) | \(525,792\) | \(36,053,248\) | \(159,989,760\) | \(139,991,040\) | \(27,998,208\) |
\(D_{2}\left( n,m\right)\) with \(n,m=1,2,…,6\).
The seventh row \(D_{2}\left( 7,m\right)\) for \(m=0,1,…,7\) is: \(0\), \(1\), \(51116992\), \(17811244032\), \(209056841728\), \(419919790080\), \(227569434624\), and \(32509919232\) which sum to \(D_{2}\left( 7\right)\).
The row sums give the values of \(D_{2}\left( n\right)\) for \(n=0,1,2,…,7\).
| \(n\) | \(D_{2}\left( n\right)\) |
|---|---|
| \(0\) | \(1\) |
| \(1\) | \(1\) |
| \(2\) | \(4\) |
| \(3\) | \(57\) |
| \(4\) | \(2,921\) |
| \(5\) | \(540,145\) |
| \(6\) | \(364,558,049\) |
| \(7\) | \(906,918,346,689\) |
\(D_{2}\left( n\right)\) for \(n=0,1,…,7\).
We can also compute the \(D^{\ast}\) examples of DSDs with a block containing a designated element. For \(q=2\), the \(D_{2}^{\ast}\left( n,m\right)\) numbers for \(n,m=0,1,…,7\) are given in the following table.
| \(n\backslash m\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) |
|---|---|---|---|---|---|---|---|---|
| \(0\) | \(1\) | |||||||
| \(1\) | \(0\) | \(1\) | ||||||
| \(2\) | \(0\) | \(1\) | \(2\) | |||||
| \(3\) | \(0\) | \(1\) | \(16\) | \(12\) | ||||
| \(4\) | \(0\) | \(1\) | \(176\) | \(560\) | \(224\) | |||
| \(5\) | \(0\) | \(1\) | \(3456\) | \(40000\) | \(53760\) | \(13440\) | ||
| \(6\) | \(0\) | \(1\) | \(128000\) | \(5848832\) | \(20951040\) | \(15554560\) | \(2666496\) | |
| \(7\) | \(0\) | \(1\) | \(9115648\) | \(1934195712\) | \(17826414592\) | \(30398054400\) | \(14335082496\) | \(1791885312\) |
Number of DSDs \(D_{2}^{\ast}\left( n,m\right)\) containing any given nonzero vector \(v^{\ast}\)
For \(n=3\) and \(m=2\), the table says there are \(D_{2}^{\ast}\left( 3,2\right) =16\) DSDs with \(2\) blocks one of which contains a given nonzero vector, say \(v^{\ast}=ab\) which represents \(\left\{ a,b\right\}\), and here they are.
| \(\left\{ \left\{ ab\right\} ,\left\{ b,c,bc\right\} \right\}\) | \(\left\{ \left\{ ab\right\} ,\left\{ a,bc,abc\right\} \right\}\) | \(\left\{ \left\{ ab\right\} ,\left\{ b,ac,abc\right\} \right\}\) | \(\left\{ \left\{ ab\right\} ,\left\{ a,c,ac\right\} \right\}\) |
|---|---|---|---|
| \(\left\{ \left\{ c\right\} ,\left\{ a,b,ab\right\} \right\}\) | \(\left\{ \left\{ c\right\} ,\left\{ ab,ac,bc\right\} \right\}\) | \(\left\{ \left\{ ac\right\} ,\left\{ c,ab,abc\right\} \right\}\) | \(\left\{ \left\{ bc\right\} ,\left\{ c,ab,abc\right\} \right\}\) |
| \(\left\{ \left\{ ac\right\} ,\left\{ a,b,ab\right\} \right\}\) | \(\left\{ \left\{ a\right\} ,\left\{ ab,ac,bc\right\} \right\}\) | \(\left\{ \left\{ a\right\} ,\left\{ c,ab,abc\right\} \right\}\) | \(\left\{ \left\{ abc\right\} ,\left\{ a,b,ab\right\} \right\}\) |
| \(\left\{ \left\{ bc\right\} ,\left\{ a,b,ab\right\} \right\}\) | \(\left\{ \left\{ b\right\} ,\left\{ ab,ac,bc\right\} \right\}\) | \(\left\{ \left\{ b\right\} ,\left\{ c,ab,abc\right\} \right\}\) | \(\left\{ \left\{ abc\right\} ,\left\{ ab,ac,bc\right\} \right\}\) |
Two-block DSDs of \(\wp\left( \left\{ a,b,c\right\} \right)\) with a block containing \(ab=\left\{ a,b\right\}\).
The table also says there are \(D_{2}^{\ast}\left( 3,3\right) =12\) basis sets containing any given nonzero vector which we could take to be \(v^{\ast}=abc=\left\{ a,b,c\right\}\), and here they are.
| \(\left\{ a,b,abc\right\}\) | \(\left\{ b,ab,abc\right\}\) | \(\left\{ a,c,abc\right\}\) | \(\left\{ b,bc,abc\right\}\) |
|---|---|---|---|
| \(\left\{ a,ab,abc\right\}\) | \(\left\{ a,ac,abc\right\}\) | \(\left\{ b,c,abc\right\}\) | \(\left\{ c,ac,abc\right\}\) |
| \(\left\{ ab,ac,abc\right\}\) | \(\left\{ ab,bc,abc\right\}\) | \(\left\{ ac,bc,abc\right\}\) | \(\left\{ bc,ab,abc\right\}\) |
Three-block DSDs (basis sets) of \(\wp\left( \left\{ a,b,c\right\} \right)\) with a basis element \(abc=\left\{ a,b,c\right\}\).
Summing the rows in the \(D_{2}^{\ast}\left( n,m\right)\) table gives the values for \(D_{2}^{\ast}\left( n\right)\) for \(n=0,1,…,7\).
| \(n\) | \(D_{2}^{\ast}\left( n\right)\) |
|---|---|
| \(0\) | \(1\) |
| \(1\) | \(1\) |
| \(2\) | \(3\) |
| \(3\) | \(29\) |
| \(4\) | \(961\) |
| \(5\) | \(110,657\) |
| \(6\) | \(45,148,929\) |
| \(7\) | \(66,294,748,161\) |
\(D_{2}^{\ast}\left( n\right)\) for \(n=0,1,…,7\).
The integer sequence \(D_{2}\left( n,n\right)\) for \(n=0,1,2,…\) is known as: \(A053601\) “Number of bases of an \(n\)-dimensional vector space over \(GF(2)\)” in the On-Line Encyclopedia of Integer Sequences (https://oeis.org/). The sequences defined and tabulated here for \(q=2\) have been added to the Encyclopedia as: \(A270880\) [\(D_{2}(n,m)\)], \(A270881\) [\(D_{2}\left( n\right)\)], \(A270882\) [\(D_{2}^{\ast}\left( n,m\right)\)], \(A270883\) [\(D_{2}^{\ast}\left( n\right)\)].
The main contributions of this paper may be summarized as follows: an elementary signature-based derivation of the direct counting formulas for DSDs that are otherwise known from generating-function treatments, and the new designated-vector enumerations \(D_{q}^{\ast}\left( n,m\right)\) and \(D_{q}^{\ast}\left( n\right)\), together with initial computed values for \(q=2\). These formulas provide a direct combinatorial bridge between classical set-partition counting and vector-space partitions, while also highlighting the additional factor \(q^{k\left( n-k\right) }\) that has no set-theoretic counterpart.
Lawvere, F. W., & Rosebrugh, R. (2003). Sets for Mathematics. Cambridge University Press.
Ellerman, D. (2023). The Logic of Partitions: With Two Major Applications, London: College Publications.
Ellerman, D. (2025). On Implication and Negation in Partition Logic. Open Journal of the Mathematical Sciences, 9, 149-157.
Birkhoff, G. (1936). The logic of quantum mechanics. Annals of Mathematics, 37, 823-834.
Ellerman, D. (2018). The quantum logic of direct-sumdecompositions: the dual to the quantum logic of subspaces. Logic Journal of the IGPL, 26(1), 1-13.
Goldman, J., & Rota, G. C. (1970). On the Foundations of Combinatorial Theory IV Finite Vector Spaces and Eulerian Generating Functions. Studies in Applied Mathematics, 49(3), 239-258.
Bender, E. A., Goldman, J. R., & Rota, G. C. (1971). Enumerative uses of generating functions. Indiana University Mathematics Journal, 20(8), 753-765.
Stanley, R. P. (1978). Exponential structures. Studies in Applied Mathematics, 59(1), 73-82.
Andrews, G. E. (1998). The Theory of Partitions (No. 2). Cambridge university press.
Knuth, D. E. (2011). The Art of Computer Programming: Vol. 4A Combinatorial Algorithms Part 1. Pearson Education.
Stanley, R. P. (1999). Enumerative Combinatorics. Volume 2. Cambridge University Press.
Lidl, R., & Niederreiter, H. (1994). Introduction to Finite Fields and Their Applications. Cambridge University Press.
Crapo, H. H. (1966). The Möbius function of a lattice. Journal of Combinatorial Theory, 1(1), 126-131.
Ellerman, D. (2017). Quantum mechanics over sets: a pedagogical model with non-commutative finite probability theory as its quantum probability calculus. Synthese, 194(12), 4863-4896.
