List all pairs of permutations with repetition with the given conditions

In summary, the conversation discusses finding all possible pairs of sequences (n_k, m_k) that satisfy certain conditions and have a given value for S and K. The problem statement is unclear on the specific values for S and K, but the speaker mentions that they are looking for lists for small values of S. The current method of generating lists is slow and the speaker is seeking a more efficient algorithm. The notation used in the conversation is inconsistent and the purpose of finding these pairs is unclear.
  • #1
Robin04
260
16
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.
 
Physics news on Phys.org
  • #2
Shouldn't the problem statement specify values for K and S? Otherwise, how do you know what list to make?
 
  • #3
FactChecker said:
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.
 
  • #4
Robin04 said:
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?
 
  • #5
FactChecker said:
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.
 
  • #6
I find your notation confusing. Sometimes you use nk for an element of a sequence and sometimes for a whole sequence. In the latter usage, the subscript k is meaningless. Maybe write (nk) 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 AS,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?
 

Related to List all pairs of permutations with repetition with the given conditions

1. What are permutations with repetition?

Permutations with repetition are arrangements of a set of objects where repetition of elements is allowed. This means that the same element can appear multiple times in a permutation.

2. How do you list all pairs of permutations with repetition?

To list all pairs of permutations with repetition, you can use the formula n^r, where n is the number of elements and r is the number of positions in each permutation. You can also use a permutation calculator or manually write out all possible combinations.

3. What are the given conditions for listing all pairs of permutations with repetition?

The given conditions for listing all pairs of permutations with repetition include having a set of elements and a specific number of positions for each permutation. The elements can be repeated in each permutation and the order of the elements matters.

4. Can you provide an example of listing all pairs of permutations with repetition?

For a set of elements {A, B, C} and 2 positions, the pairs of permutations with repetition would be AA, AB, AC, BA, BB, BC, CA, CB, CC. This can also be written as 3^2 = 9 possible combinations.

5. How are permutations with repetition different from combinations?

Permutations with repetition differ from combinations in that permutations allow for repetition of elements and the order of the elements matters, while combinations do not allow for repetition and the order of the elements does not matter. For example, in the set {A, B, C}, the permutation AB would be different from the combination AB as the order matters in permutations but not in combinations.

Similar threads

Replies
18
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Topology and Analysis
Replies
3
Views
2K
  • Advanced Physics Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
605
  • Precalculus Mathematics Homework Help
Replies
16
Views
2K
  • Atomic and Condensed Matter
Replies
0
Views
613
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Back
Top