Thread: Counting problem (number of permutations)

1. Counting problem (number of permutations)

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

Evaluate the following sum:

$\displaystyle \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 $\displaystyle i$ must appear $\displaystyle r_i$ times in any permutation, $\displaystyle r_i=a_{i,k}(\sigma)+a^\prime_{i,n-k}(\sigma)$. Hence, $\displaystyle b_3(\sigma)=a_{3,k}(\sigma)+a^\prime_{3,n-k}(\sigma)=r_3$ for all $\displaystyle \sigma \in M$. I will first count the number of permutations with $\displaystyle b_1(\sigma)=p$ for some $\displaystyle 0 \le p \le r_1+r_5$. For any one of those permutations, we have
$\displaystyle \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 $\displaystyle b_1(\sigma)=p$ is:

$\displaystyle \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.

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