Combinatorial problem

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

  1. arfa brane call me arf Valued 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
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Write4U Valued 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
    :

    Please Register or Log in to view the hidden image!


    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/

    Please Register or Log in to view the hidden image!

     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. arfa brane call me arf Valued 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.
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Write4U Valued 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 brane call me arf Valued 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. QuarkHead Remedial Math Student Valued Senior Member

    Messages:
    1,728
    Try \(\frac{n!}{(n-k)!k!}\) where by convention \(0!=1\)
     
  10. arfa brane call me arf Valued 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 brane call me arf Valued 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 brane call me arf Valued 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).
     

Share This Page