+ Reply to Thread
Results 1 to 1 of 1

Thread: Permutations w/ constraints question

  1. #1
    Points: 4, Level: 1
    Level completed: 7%, Points required for next Level: 46

    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Permutations w/ constraints question




    Hello Everyone!

    I apologize, in advance, if I'm posting this query in the wrong thread...

    My query:

    Given a transpose 5-d vector, {d_1, d_2, d_3, d_4, d_5}, I allow d_i, where i=1,...5, to be an integer element between [1,n]. The possible permutations are

    (1) n=1, 1^5=1; {1,1,1,1,1}
    (2) n=2, 2^5=32; {1,1,1,1,1},{1,1,1,1,2},...,{2,2,2,2,2}
    (3) n=3, 3^5=243; {1,1,1,1,1},{1,1,1,1,2},...,{3,3,3,3,3}
    ...
    (m) n=m, m^5; {1,1,1,1,1},...{m,m,m,m,m}

    (C1) My first constraint is to exclude any permutation where any d_i is repeated 3 or more times, e.g. {1,2,1,1,2}, {2,1,2,2,2}, {m,m,5,9,m}, etc.

    d_i repeated twice, or d_i and d_j repeated twice is fine, e.g. {1,1,3,4,5}, {2,3,4,3,2}, etc.

    (1) n=1, {1,1,1,1,1}, does not satisfy this constraint.
    (2) n=2, {1,1,1,1,1},{1,1,1,1,2},...,{2,2,2,2,2}, does not satisfy this constraint either.
    (3) n=3, {1,1,1,1,1},{1,1,1,1,2},...,{3,3,3,3,3}, has 90 permutations, of 243, that satisfy this constraint, specifically {1,1,2,2,3},...{3,3,2,2,1}.

    Is there a mathematical formula, as a function of n, and i, i.e. n^i -(something) that gives the permutations for this constraint?

    There's one more constraint after this one, specifically sum_i (d_i) leq p, but I need to get through the first constraint...first.

    I very much appreciate nay help that is given. Again, if this is too elementary, and I've posted this on the wrong thread, I apologize. I'll move it to where it belongs.

    Thanks in advance,
    G_M

    P.S. I can write brute-force algorithms to crank out the answers, using both constraints, but I'm weak on the statistical math theory.
    If someone could point me in the general direction of some research that resembles this problem, I can start reading. Thanks again.
    Last edited by G_M_Vald; 02-05-2014 at 12:56 PM.

+ Reply to Thread

           




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats