Counting problem (number of permutations)

**SlipEternal** · September 29th 2012, 09:57 AM

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.

**SlipEternal** · September 29th 2012, 01:34 PM

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...

Thread: Counting problem (number of permutations)

LinkBack

Thread Tools

Display

Counting problem (number of permutations)

Re: Counting problem (number of permutations)

Similar Math Help Forum Discussions

Counting-Permutations

Counting (Permutations/Combinations)

[SOLVED] Help with combinations, permutations and counting please?

Permutations & Organized Counting

Counting (Permutations and Combinations)

Search Tags