# Combinatorial problem

Discussion in 'Physics & Math' started by arfa brane, Apr 28, 2021.

1. ### arfa branecall me arfValued Senior Member

Messages:
7,184
The problem is described thus:

Given a string of n different characters, choose a substring of length k and define a cyclic permutation on it. Take the k-cycle to another substring of length k by shifting it along the string.

So if you have a string of length n and a pair of k-cycles, k < n, is there a way to predict how compositions of the pair acting on the string will behave? Can you predict the order of some composition, given you have only a pair of cyclic permutations and their inverses to play with?

An example: if n is 5, five different characters might be: abcde.
The pair of cycles in cycle notation might be (123) and (345). they intersect with the third character in the string.

Already there are some obvious details. Given the above pair of cycles have inverses, there are four possible combinations, but I can multiply that by 2 to get the number of possible compositions.

Is there a general formula that can tell me the order of each composition?

Last edited: Apr 28, 2021

3. ### Write4UValued Senior Member

Messages:
17,377
question: Does this have something to do with probability ? Might the following be applicable ?

Formula to Calculate Probability

The formula of the probability of an event is
:

Probability Formula

Or,

P(A) = n(A)/n(S)

Where,
• P(A) is the probability of an event “A”
• n(A) is the number of favourable outcomes
• n(S) is the total number of events in the sample space
Note: Here, the favourable outcome means the outcome of interest.

https://byjus.com/probability-formulas/

5. ### arfa branecall me arfValued Senior Member

Messages:
7,184
I don't think it does. Everything is determined: the length of the string, the size of the cycles, the number of compositions of a pair of equal but 'displaced' cycles along with inverses, all of which implies there is a formula you can write that says at least something about how many permutations there are over n characters.

Write4U likes this.

7. ### Write4UValued Senior Member

Messages:
17,377
Next question: how about "differential equations?

Not trying to be difficult, but asking from some intuitive association, perhaps.

8. ### arfa branecall me arfValued Senior Member

Messages:
7,184
I can't recall ever seeing differential equations for strings of characters. But maybe there's an actual mathematician somewhere who has . . .
Differential equations are sometimes equations of motion; a cyclic permutation can sometimes be a rotation (or rather there's a map between the two).

This problem is a counting problem; it's actually about integral, not continuous spaces like gradient maps etc.

p.s. I think my level of sarcasm can sometimes be almost endearing.

Write4U likes this.
9. ### QuarkHeadRemedial Math StudentValued Senior Member

Messages:
1,728
Try $\frac{n!}{(n-k)!k!}$ where by convention $0!=1$

10. ### arfa branecall me arfValued Senior Member

Messages:
7,184
There's a theorem (Ruffini) that says the order of a permutation of a finite set, in cycle notation, is the lcm of the lengths of the cycles.

So writing (123)(345) = (12453), the order is 5.
Also (123)(543) = (12543).

So having one inverse (in the composition) doesn't change the order, and in fact all 8 compositions have the same order.

Last edited: Apr 30, 2021
11. ### arfa branecall me arfValued Senior Member

Messages:
7,184
Stay with n = 5; define a pair of 4-cycles: (1234)(5432) = (154). An order 3 element of the subgroup of cyclic permutations in $S_5$.

Likewise on a string of length 6, define a pair of 4-cycles: (1234)(3456) = (124)(356).
But (1234)(6543) = (12654).

The order doesn't seem to be related to the string length.

12. ### arfa branecall me arfValued Senior Member

Messages:
7,184
That should actually say the lcm of disjoint cycles; you have to do a bit of calculating (apply an algorithm) to rewrite say, (1234)(3456) a composition of two 4-cycles, as = (124)(356).