StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I can answer 1 for you. Consider these two cases:</p> <p><strong>Case 1: <code>D13 = D23</code></strong></p> <p>Here you can just multiply by <code>D12</code> on both sides to get <code>D12 * D13 = D12 * D23</code>.</p> <p><strong>Case 2: <code>D13 != D23</code></strong></p> <p>This means that either <code>d1 = d3</code> XOR <code>d2 = d3</code> but <strong>not both</strong>. Therefore we know that <code>d1 != d2</code>. This implies that <code>D12 = 0</code>. Therefore </p> <pre><code>D12 * D13 = 0 * D13 = 0 = 0 * D23 = D12 * D23 </code></pre> <p>The problem with your logic when you think this implies <code>D13 = D23</code> is that you cannot divide by <code>0</code>, and <code>D12</code> might be <code>0</code> (as always happens in the second case). </p> <hr> <p>Your second question is interesting, and I do not know the answer off the top of my head, but here are some observations that may be helpful.</p> <p>Draw the numbers <code>1, 2, ..., n</code> in a row:</p> <pre><code>1 2 3 ... n </code></pre> <p>Given an expression <code>D_(i1,j1) * D_(i2,j2) * ... * D_(ik,jk)</code>, make an arc from <code>i1 to j1</code> and <code>i2 to j2</code> and so on. This turns that row into a graph (vertices are numbers, edges are these arcs).</p> <p>Each connected component of that graph represents a subset of the number <code>1, 2, ..., n</code>, and taken as a whole this gives us a <a href="http://en.wikipedia.org/wiki/Partition_of_a_set" rel="nofollow">set partition</a> of <code>{1, 2, ..., n}</code>. </p> <p><strong>Fact:</strong> Any two terms that have the same corresponding set partition are equal.</p> <p>Example:</p> <pre><code>D12 * D23 = D12 * D13 --------- | | 1 -- 2 -- 3 = 1 -- 2 3 </code></pre> <p>Sometimes this fact will mean the degree is the same, as in the case above, and sometimes the degree will decrease as in</p> <pre><code>D12 * D13 * D23 --------- | | 1 -- 2 -- 3 </code></pre> <p>The upshot is that now you can express the product (1 - Dij) as a sum over set partitions:</p> <pre><code>\prod_{i<j} ( 1 - Dij ) = \sum_{P set partition of \{1,2,...,n\}} c_P * m_P </code></pre> <p>where the monomial term is given by</p> <pre><code>mP = mP1 * mP2 * ... * mPk </code></pre> <p>when <code>P = P1 union P2 union ... union Pk</code> and if <code>Pi = { a < b < c < ... < z }</code> then</p> <pre><code>m_Pi = Dab * Dac * ... * Daz </code></pre> <p>Finally, the coefficient term is just</p> <pre><code>c_P = \prod (#P1)! (#P2)! ... (#Pn)! </code></pre> <p>Having worked this out, I'm now certain this belongs on <a href="http://math.stackexchange.com">http://math.stackexchange.com</a> rather than here.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload