Inversions - Revision history

Admin: /* Related */

2019-03-27T01:20:27Z

← Older revision		Revision as of 01:20, 27 March 2019
Line 114:		Line 114:
	==Related==		==Related==

	* [[~~Inversions~~]]		* [[Cycles]]
	* [[Permutations]]		* [[Permutations]]
	* [[Rubiks Cube/Permutations]]		* [[Rubiks Cube/Permutations]]
	* [[Combinatorics]]		* [[Combinatorics]]

			==Flags==

			{{CombinatoricsFlag}}

			{{AOCPFlag}}

Admin: /* Cards */

2019-03-27T01:19:58Z

Cards

← Older revision		Revision as of 01:19, 27 March 2019
Line 110:		Line 110:
	==Cards==		==Cards==

	We can apply this idea to a pack of [[Cards]], although in the case of a pack of cards we have to account for duplicates (or assign an arbitrary ranking for suits to break ties).		We can apply this idea to a pack of 52 [[Cards]], although in the case of a pack of cards we have to account for duplicates (or assign an arbitrary ranking for suits to break ties).

	==Related==		==Related==

Admin: /* Expected Number of Inversions */

2019-03-27T01:19:47Z

Expected Number of Inversions

← Older revision		Revision as of 01:19, 27 March 2019
Line 107:		Line 107:
	\dfrac{ 0 + \frac{n(n-1)}{2} }{2} = \dfrac{n(n-1)}{4}		\dfrac{ 0 + \frac{n(n-1)}{2} }{2} = \dfrac{n(n-1)}{4}
	</math>		</math>

			==Cards==

			We can apply this idea to a pack of [[Cards]], although in the case of a pack of cards we have to account for duplicates (or assign an arbitrary ranking for suits to break ties).

	==Related==		==Related==

Admin: /* Expected Number of Inversions */

2019-03-27T01:18:32Z

Expected Number of Inversions

← Older revision		Revision as of 01:18, 27 March 2019
Line 99:		Line 99:

	==Expected Number of Inversions==		==Expected Number of Inversions==

			Take the minimum and maximum number of inversions, which are 0 and <math>\dfrac{n(n-1)}{2}</math>.

			If we assume that all inversions are uniformly distributed, the number of inversions on average will be the mean of the min and max, which is

			<math>
			\dfrac{ 0 + \frac{n(n-1)}{2} }{2} = \dfrac{n(n-1)}{4}
			</math>

	==Related==		==Related==

Admin: /* Number of Inversions */

2019-03-27T01:16:45Z

Number of Inversions

← Older revision		Revision as of 01:16, 27 March 2019
Line 83:		Line 83:

	<math>		<math>
	\dfrac{(n)(n-1)}{2}		\dfrac{n(n-1)}{2}
	</math>		</math>

Line 95:		Line 95:

	<math>		<math>
	\dfrac{(n)(n-1)}{2} + n = \dfrac{n^2 - n + 2n}{2} = \dfrac{n(n+1)}{2}		\dfrac{n(n-1)}{2} + n = \dfrac{n^2 - n + 2n}{2} = \dfrac{n(n+1)}{2}
	</math>		</math>

Admin: /* Maximum Number of Inversions */

2019-03-27T01:16:24Z

Maximum Number of Inversions

@@ Line 74: / Line 74: @@
 <math>
 \sum_{i=0}^{n} \sum_{j+1}^{n} = \dfrac{ (n)(n-1) }{2}
 </math>

Admin: /* Maximum Number of Inversions */

2019-03-27T00:30:53Z

Maximum Number of Inversions

← Older revision		Revision as of 00:30, 27 March 2019
Line 67:		Line 67:

	<math>		<math>
	\sum_{i=0}^{n} \sum_{j=i+1}^{n} 1 = \sum_{i=0}^{n} \sum_{j=0}^{i} 1 =		\sum_{i=0}^{n} \sum_{j=i+1}^{n} 1 = \sum_{i=0}^{n} \sum_{j=0}^{i-1} 1 = \sum_{i=0}^{n} i-1
			</math>

			Now we use the famous formula for the sum of the first n integers, where n = i - 1, to get:

			<math>
			\sum_{i=0}^{n} \sum_{j+1}^{n} = \dfrac{ (n)(n-1) }{2}
	</math>		</math>

Admin: Created page with "==Notes== Inversions are an important concept when discussing Permutations and Combinatorics. An '''inversion''' is a pair of items (not necessarily neighbors) that..."

2019-03-27T00:29:14Z

Created page with "==Notes== Inversions are an important concept when discussing Permutations and Combinatorics. An '''inversion''' is a pair of items (not necessarily neighbors) that..."

New page

==Notes==

Inversions are an important concept when discussing [[Permutations]] and [[Combinatorics]].

An '''inversion''' is a pair of items (not necessarily neighbors) that are out of order in a permutation.

If we have a set of items, for example the integers 1, 2, 3, 4, 5, a permutation is an arrangement of those items in a particular order. This is typically written with two line notation - the first line indicating the natural order of the items, the second indicating their arrangement in the permutation.

<math>
a = \bigl(\begin{smallmatrix}
1 & 2 & 3 & 4 & 5 \\
1 & 5 & 3 & 2 & 4
\end{smallmatrix}\bigr)
</math>

But writing the second row only is more convenient, so we will write the second row by itself going forward.

==Definition==

An inversion is defined as a pair of items that are out of order in a permutation. These items do not need to be neighbors, which means we must consider every pairwise combination of elements. Consider the example:

<math>
1 \, 5 \, 3 \, 2 \, 4
</math>

We can build a table of all inversions:

<pre>
i j inversion? (1=yes, 0=no)
------------------------------
1 5 0
1 3 0
1 2 0
1 4 0
5 3 1
5 2 1
5 4 1
3 2 1
3 4 0
2 4 0

total: 4
</pre>

==Maximum Number of Inversions==

From consideration of the definition of an inversion, we can see that the maximum number of inversions occurs when the entire array is reversed, so that every pairwise combination is an inversion.

This is usually accompanied by an iteration structure like this (note that j starts at i):

<pre>
for (i = 0; i < n; i++ ){
for (j = i; j < n; j++ ){
...
}
}
</pre>

Mathematically, this is equivalent to the sum:

<math>
\sum_{i=0}^{n} \sum_{j=i}^{n} ...
</math>

If we use 1 as the expression in the sum and shift the index we can combine the sums like so:

<math>
\sum_{i=0}^{n} \sum_{j=i+1}^{n} 1 = \sum_{i=0}^{n} \sum_{j=0}^{i} 1 =
</math>

==Expected Number of Inversions==

==Related==

* [[Inversions]]
* [[Permutations]]
* [[Rubiks Cube/Permutations]]
* [[Combinatorics]]