A problem on constrained combinatorics

Not sure if this is a proper place, but I really don't know where else to ask. I'm craving for an algorithm generating certain sequences of numbers (the problem comes from physics).

I'm looking for all such sequences of $a_n$ an $b_n$ that:
$$
\begin{cases}
\sum \limits_{n=1}^{K} (n a_n) + \sum \limits_{m=1}^{K} (m b_m) = K\\
\sum \limits_{n=1}^{K} a_n - \sum \limits_{m=1}^{K} b_m = Q\\
\end{cases}
\quad,\quad
\text{where}\qquad
\begin{cases}
K\in\mathbb{Z}^+\\
Q\in\mathbb{Z}\\
a_n,b_m= \{0,1\}
\end{cases}
$$

For my application, I am interested in finding all such sequences starting from $K=Q(\operatorname{mod}2)$ and up to some large value of $K$, so, I guess, it would make sense to solve the problem iteratively. I would really appreciate if someone could up with an efficient solution.

EXAMPLE

For $Q=0$, $K=2$ the only option is $a_1=b_2=1$. We shall write it as $\{\{1\},\{1\}\}$. The first sublist corresponds to $a$'s, the second $-$ to $b$'s. The $j$th position in the sublist denotes the value of $a_j$ or $b_j$.

For $Q=0$, $K=4$, the possible sets are: $\{a_3=1;b_1=1\}$, $\{a_1=1;b_3=1\}$, $\{a_2=1;b_2=1\}$, with all other coefficients vanishing.

Here's an example of the output:
\begin{alignat}{9}
&Q=0,K=2:\quad &&\{\{\{1\},\{1\}\}\}\\
&Q=0,K=4:\quad &&\{\{\{0,0,1\},\{1\}\},\{\{1\},\{0,0,1\}\},\{\{0,1\},\{0,1\}\}\}
\\&...&&
\end{alignat}

Where I omitted the vanishing elements following the last non-zero element.

P.S.

The particular form of the output is not important for me. I would be equally happy to get it, say, in the form of lists of numbers of non-vanishing elements:
\begin{alignat}{9}
&Q=0,K=2:\quad &&\{\{\{1\},\{1\}\}\}\\
&Q=0,K=4:\quad &&\{\{\{3\},\{1\}\},\{\{1\},\{3\}\},\{\{2\},\{2\}\}\}
\\&...&&
\end{alignat}

UPDATE

-
By efficient algorithm I mean the one which does not make any useless steps (like "going though all possible sequences and throwing away the ones which do not work"). Yes, the algorithm will work in exponential time, and the

Rephrasing, $$A, B \subseteq \{1, 2, \ldots, K\} \\
\sum_{a \in A}a + \sum_{b \in B}b = K \\
|A| - |B| = Q$$

So as your friend suggests, this can be tackled by looking at partitions of an integer into a given number of distinct parts.

for K1 = 0 to K:
for N1 = 0 to K1:
for A in distinct_partitions(K1, N1):
for B in distinct_partitions(K - K1, N1 - Q):
process(A, B)


The easiest way to generate all partitions of an integer is a recursion with a second parameter: the largest part. Similarly, the easiest way to generate all partitions of an integer into a given number of distinct parts is a recursion with a third parameter: the largest part.

distinct_partitions(n, k):
# Special case
if n == 0 and k == 0:
yield []

for m = 1 to n:
yield from distinct_partitions_inner(n, k, m)

distinct_partitions_inner(n, k, m):
# Base case
if k == 1:
if n == m:
yield [n]
return

# Parts are distinct, positive, and no greater than m
if k > m:
return

# The smallest possible partition is 1+2+...+(k-1)+m
if n m k - (k-1) k / 2:
return

# m is the largest part, so we have n-m left to assign to smaller parts
for i = 1 to m-1:
for subpartition in distinct_partitions_inner(n-m, k-1, i):
yield [m] + subpartition


The early aborts can be adjusted according to aesthetics to try to abort one level up the call stack.

Note that the table of the number of Fock states given in the Pauli and Brodsky paper you link contains a few errors. I derived their generating function and generated some data using the following Python code:

`import math

def convolveP(a):
''' Convolves a generating function with the g.f. of the partition numbers '''
for n in range(0, len(a)):
for j in range(int((math.sqrt(1 + 24*n) + 1) / 6)):
t = 1 + j (3j + 5) // 2
a[n] += (-1)**j * a[n - t]
if t + j

This gave enough terms to find the sequences for the first four values of $Q$ in the Online Encyclopedia of Integer Sequences:

• $Q=0$: A006330

• $Q=1$: A001523 (correcting $a(0)$ to $0$: see comment by Michael Somos)

• $Q=2$: A288578, offset so that the first non-zero term is at $K=3$

• $Q=3$: A288579, offset so that the first non-zero term is at $K=6$

All four of those reference this paper, section 2.1, which gives some similar g.f.s (offset by a power of $q$) and a combinatorial explanation. I find that the explanation doesn't match up, but if I figure out the discrepancy and a suitable bijection to extract the partitions for fermions, antifermions, and bosons then I'll edit, because that might give a more economical generation procedure.

StackExchange Computer Science Q#99284, answer score: 2