全排列和对换
奇排列与偶排列
重要程度：7 分
<h2>1. 全排列与对换</h2>
<p>全排列是指将一组元素按照不同的顺序进行排列。对于 <strong>n</strong> 个不同元素，共有 <strong>n!</strong> 种不同的排列方式。</p>
<h3>1.1 奇排列与偶排列</h3>
<p>在全排列中，可以通过对换（即交换两个元素的位置）来改变排列的顺序。每次对换会改变排列的奇偶性。</p>
<ul>
<li><strong>偶排列：</strong> 如果一个排列可以通过偶数次对换从自然排列（1, 2, 3, ..., n）得到，则该排列称为偶排列。</li>
<li><strong>奇排列：</strong> 如果一个排列可以通过奇数次对换从自然排列（1, 2, 3, ..., n）得到，则该排列称为奇排列。</li>
</ul>
<h4>例题 1：判断排列的奇偶性</h4>
<p>给定排列 (3, 1, 2)，判断它是奇排列还是偶排列。</p>
<ol>
<li>从自然排列 (1, 2, 3) 开始，我们需要通过对换来得到 (3, 1, 2)。</li>
<li>第一次对换：(1, 2, 3) → (3, 2, 1)</li>
<li>第二次对换：(3, 2, 1) → (3, 1, 2)</li>
</ol>
<p>总共进行了两次对换，因此 (3, 1, 2) 是一个偶排列。</p>
<h4>例题 2：计算排列的逆序数</h4>
<p>逆序数是指在一个排列中，前面的元素大于后面的元素的对数。奇偶排列也可以通过逆序数来判断：</p>
<ul>
<li>如果逆序数为偶数，则该排列是偶排列。</li>
<li>如果逆序数为奇数，则该排列是奇排列。</li>
</ul>
<p>给定排列 (4, 3, 2, 1)，计算其逆序数并判断奇偶性。</p>
<ol>
<li>(4, 3, 2, 1) 中的逆序对有：<br>
(4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1)<br>
总共有 6 个逆序对。</li>
<li>因为逆序数为 6，是偶数，所以 (4, 3, 2, 1) 是一个偶排列。</li>
</ol>
<h4>例题 3：证明对换改变排列的奇偶性</h4>
<p>设排列 <strong>P</strong> 是一个偶排列，证明通过一次对换后，新的排列 <strong>P'</strong> 一定是奇排列。</p>
<ol>
<li>假设排列 <strong>P</strong> 的逆序数为 <strong>k</strong>，且 <strong>k</strong> 是偶数。</li>
<li>对换任意两个元素 <strong>a</strong> 和 <strong>b</strong>，假设 <strong>a > b</strong> 且它们之间的相对位置发生了变化。</li>
<li>对换后，<strong>a</strong> 和 <strong>b</strong> 之间的逆序对数会减少 1 或增加 1，具体取决于它们原来的相对位置。</li>
<li>因此，新的排列 <strong>P'</strong> 的逆序数为 <strong>k ± 1</strong>，即变成了奇数。</li>
<li>结论：对换一次后，排列的奇偶性发生了改变。</li>
</ol>