Results 1 to 2 of 2

Math Help - Counting problem (number of permutations)

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,791
    Thanks
    693

    Counting problem (number of permutations)

    Let's say I have n objects, each with a number from 1 to 5 printed on them. There are r_i objects with the number i printed on them for i=1,2,3,4,5. These objects are otherwise indistinguishable. Let M be the set of all permutations of these n objects ( M is essentially a set of multiset permutations). Given any permutation \sigma \in M, let a_{i,k}(\sigma) be the number of times the number i appears on any of the first k objects in the permutation, and let a^\prime_{i,k}(\sigma) be the number of times the number i appears on any of the last k objects in the permutation. Fix an integer 0\le k \le n. Let b_i(\sigma) = a_{i,k}(\sigma)+a^\prime_{6-i,n-k}(\sigma).

    Evaluate the following sum:

    \displaymode \sum_{\sigma\in M}\left( \prod_{i=1}^5 i^{b_i(\sigma)} \right)

    I already solved this problem, but it involved summing over all integral solutions to a Diophantine equation in 5 variables. I am looking for an alternate solution. Here is my attempt to solve it (any advice would be greatly appreciated). Since each number i must appear r_i times in any permutation, r_i=a_{i,k}(\sigma)+a^\prime_{i,n-k}(\sigma). Hence, b_3(\sigma)=a_{3,k}(\sigma)+a^\prime_{3,n-k}(\sigma)=r_3 for all \sigma \in M. I will first count the number of permutations with b_1(\sigma)=p for some 0 \le p \le r_1+r_5. For any one of those permutations, we have
    \displaymode b_5(\sigma)=a_{5,k}(\sigma)+a^\prime_{1,n-k}(\sigma)=(r_5-a^\prime_{5,n-k}(\sigma))+(r_1-a_{1,k}(\sigma))=r_1+r_5-b_1(\sigma)=r_1+r_5-p

    I believe the count for the number of permutations with b_1(\sigma)=p is:

    \displaymode \sum_{a=0}^{p}\left(\binom{k}{a}\binom{n-k}{r_1-a}\binom{k-a}{p-a}\binom{n-k-r_1+a}{r_5-p+a}\right)

    Is this correct? I want to make sure I am counting correctly before I continue.
    Last edited by SlipEternal; September 29th 2012 at 10:09 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,791
    Thanks
    693

    Re: Counting problem (number of permutations)

    Oddly enough, according to Wolfram Alpha, a possible solution has something to do with the hypergeometric function 2F1... I don't quite see what this problem has to do with the hypergeometric function, but that might help me approximate solutions if it works out...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting-Permutations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 26th 2011, 09:40 AM
  2. Counting (Permutations/Combinations)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 12th 2010, 09:49 PM
  3. [SOLVED] Help with combinations, permutations and counting please?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 23rd 2010, 11:43 AM
  4. Permutations & Organized Counting
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 16th 2010, 02:56 PM
  5. Counting (Permutations and Combinations)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 25th 2009, 04:34 PM

Search Tags


/mathhelpforum @mathhelpforum