List all pairs of permutations with repetition with the given conditions

[Robin04]

Homework Statement

List all pair of permutations with repetition with given condition, conditions are elaborated below

Relevant Equations

-

Let us consider two sequences:
$$n_k \in \Omega,\,k=1,2,...K,$$
$$m_k \in \Omega,\,k=1,2,...K,$$
where $$\Omega:=\{n\in\mathbb{N}|\,n\leq K\}.$$
Let us define
$$\sigma_n:=\sum_{k=1}^K k\, n_k,\,\sigma_m:=\sum_{k=1}^K k\,m_k$$
The task is to find all possible $(n_k,\,m_k)$ pairs such that
$$\sigma_n=\sigma_m$$
and
$$\sigma_n+\sigma_m=2S,$$
where $S\in \mathbb{N}^+$

For example for $K=2,S=1$, only one pair is possible:
$$n_k=1,0$$
$$m_k=1,0$$
For $K=2,S=2$:
First pair:
$$n_k=2, 0$$
$$m_k=2,0$$
Second pair:
$$n_k=2, 0$$
$$m_k=0,1$$
Third pair:
$$n_k=0,1$$
$$m_k=2,0$$
Fourth pair:
$$n_k=0,1$$
$$m_k=0,1$$

So far, I have only written a program that lists all possible sequences from $\Omega$, and than checks each one against the other if they match the given conditions. It is really slow, and I wonder whether it is possible to list them more efficiently.

 

[FactChecker]

Shouldn't the problem statement specify values for K and S? Otherwise, how do you know what list to make?

 

[Robin04]

Shouldn't the problem statement specify values for K and S? Otherwise, how do you know what list to make?

Yes, $K$ is a constant and $S$ runs from 1 to K.

 

[FactChecker]

Yes, $K$ is a constant and $S$ runs from 1 to K.

So are you being asked for lists from S= 1 to 5 or lists from S= 1 to $10^{100}$? It seems to make a difference.
Or are you being asked for a formula for generating any lists required?

 

[Robin04]

So are you being asked for lists from S= 1 to 5 or lists from S= 1 to $10^{100}$? It seems to make a difference.
Or are you being asked for a formula for generating any lists required?

Seeking for a general formula might sound too optimistic to me. I only need to generate lists for small values of S, let's say up to 10-20. If no explicit formula could be given, I would already be satisfied with a more efficient algorithm to generate the lists. My current code, for S = 5, has to check around 8000 possible lists against each other, which takes around a minute, but for S = 6, this increases to around 100000 lists, haven't waited til its termination yet.

 

[haruspex]

I find your notation confusing. Sometimes you use n_k for an element of a sequence and sometimes for a whole sequence. In the latter usage, the subscript k is meaningless. Maybe write (n_k) to denote a sequence.

The thread title mentions permutations, but I see nothing related to those in the description.

I don't get what is so interesting about pairs of such sequences. If A_S,K is the set of all sequences conforming to the given S, K, isn't it then just a matter of listing all unordered pairs of elements of A?