Computing Permutations with Partial Duplicates - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T05:53:27Z http://mathoverflow.net/feeds/question/75447 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates Computing Permutations with Partial Duplicates dustin 2011-09-14T20:59:21Z 2011-10-01T08:22:12Z <p>I am looking for a way to compute the number of $K$ permutations of a multiset with $N*D$ elements where each group has exactly $D$ equal elements (and typically $D &lt; N$ ).</p> <p>I've got an application that actually generates these unique permutations and works on them, but I'd like to understand how I can compute the number of sets I'll have across various inputs without computing the entire result.</p> <p>Example (in R):</p> <pre><code>N &lt;- 19 K &lt;- 4 # Implied D = 3 by just duplicating it in-place three times. a &lt;- append(1:N, append(1:N, 1:N)) b &lt;- unique(gtools::permutations(length(a), K, a, set=FALSE)) </code></pre> <p><code>nrow(b)</code> in this case will be <code>130,302</code>.</p> <p>This is slow and inelegant. Can someone help me do this with actual math?</p> <p><strong>Expanding a bit</strong></p> <p>If <code>N</code> is 9 and <code>D</code> is 3, my input might look like this:</p> <pre><code>1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 </code></pre> <p>A standard permutation would look like this:</p> <pre><code>1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 3 1 1 1 3 1 1 1 3 </code></pre> <p>But at this point, I want to treat the things that look the same as the same, so I deduplicate to get the following:</p> <pre><code>1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 1 6 1 1 1 7 </code></pre> <p>The first (full permutation) provides 421,200 rows: $(9*3)! \over (9 * 3 - 4)!$</p> <p>My final, deduplicated answer is <code>6,552</code> rows. I'd like to know how I can get that without generating them all.</p> <p><strong>New Discovery</strong></p> <p>For my initial case where $D = K - 1$, I get the correct answer with $N^K - N$.</p> http://mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates/75458#75458 Answer by psd for Computing Permutations with Partial Duplicates psd 2011-09-14T22:55:24Z 2011-09-14T22:55:24Z <p>oeis...........</p> http://mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates/75460#75460 Answer by nullghost for Computing Permutations with Partial Duplicates nullghost 2011-09-14T23:04:38Z 2011-09-15T00:14:51Z <p>I'm thinking the result should be:<br> n ^ k for d >= k<br> n ^ k - n ^ (k - d) for d &lt; k </p> http://mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates/75498#75498 Answer by Max Alekseyev for Computing Permutations with Partial Duplicates Max Alekseyev 2011-09-15T09:12:48Z 2011-09-17T07:51:54Z <p>The number of $K$-permutations of the numtiset ${ 1^D, 2^D, \ldots, N^D }$ is $$\sum_{j_1+j+2+\dots+j_N=K\atop 0 \leq j_i \leq D} \binom{K}{j_1,j_2,\dots,j_N}.$$ (summands here are multinomial coefficients)</p> <p>Alternatively, denoting by $m_i$ the number of $j$'s equal $i$, we get a formula as the sum over restricted partitions: $$\sum_{0m_0+1m_1 + \dots + Dm_D = K\atop m_0 + m_1 + \dots + m_D = N,\quad m_i\geq 0} \binom{N}{m_0,\dots,m_D} \frac{K!}{1!^{m_1} 2!^{m_2} \cdots D!^{m_D}}$$</p> <p>For the example with $N=9$, $D=3$, $K=4$, the latter formula consists of four summands and gives: $$\binom{9}{5,4} \frac{4!}{1!^4} + \binom{9}{6,2,1}\frac{4!}{1!^2 2!^1} + \binom{9}{7,1,1}\frac{4!}{1!^1 3!^1} + \binom{9}{7,2}\frac{4!}{2!^2}$$ $$= 3024 + 3024 + 288 + 216 = 6552$$ as expected.</p> http://mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates/75503#75503 Answer by nomatter for Computing Permutations with Partial Duplicates nomatter 2011-09-15T11:09:00Z 2011-09-15T11:09:00Z <p>You could try to use exponential generating functions.</p> <p>For each of the N letters you could use the exponential generating function</p> <p>$$\sum_{i=0}^D \frac{x^i}{i!}$$</p> <p>Cause each letter can be used at most D times this is the same for each letter.</p> <p>Then for using all different letters the egf's have to be multipled (you have N different letters so N times):</p> <p>$$\left(\sum_{i=0}^D \frac{x^i}{i!}\right)^N$$</p> <p>Then you are looking for the amount of different words of length K which is if you expand the expression above (which is possible if you put into it values for $D, N$. Then the coefficient of $x^K$ multiplied by $k!$ is your solution.</p> <p>What I wasn't able to do right now is trying to expand the generating function into a series without using concrete values for $D$ and $N$.</p>