COST (GBP)

1.40

3.96

Maths › Combinatorics › Sequences ›

fixed permutation

Calculates the number of permutations of \e n objects with \e m fixed.

Controller: CodeCogs

Contents

Interface
Fixed Permutation
Page Comments

Dependents

Interface

C++

Excel

Fixed Permutation

intfixed_permutation(	int	`n`
	int	`m`	)

A permutation of n objects with m fixed is a permutation in which exactly m of the objects retain their original positions. In more formal terms, consider the following permutation

$\sigma = \left( \begin{array}{cccc} 1 & 2 & \ldots & n \cr \sigma(1) & \sigma(2) & \ldots & \sigma(n) \end{array} \right)$

(2)

then $\inline \sigma$ has exactly m fixed objects if

$\mathrm{card} \{ i \,|\,\sigma(i) = i, \quad i = \overline{1, n} \} = m$

(3)

If $\inline m = 0$ , the permutation is a derangement, while if $\inline m = n$ , the permutation is the identity.

The number of permutations of n objects with m fixed is given by

$F(n, m) = (n! / m!) \cdot (1 - 1/1! + 1/2! + \cdots + (-1)^{n-m}/(n-m)!)$

(4)

$F(n, m) = \left( \begin{array}{c} n \cr m \end{array} \right) \cdot D_{n - m}$

(5)

where $\inline D_{n - m}$ is the number of derangements of $\inline n - m$ objects.

This function calculates the value of $\inline F(n, m)$ based on the above formula.

References:

SUBSET, a C++ library of combinatorial routines, http://www.csit.fsu.edu/~burkardt/cpp_src/subset/subset.html

Example 1

#include <codecogs/maths/combinatorics/sequences/fixed_permutation.h>
#include <iostream>
int main()
{
  std::cout << "The number of permutations of 10 elements with 5 fixed is: ";
  std::cout << Maths::Combinatorics::Sequences::fixed_permutation(10, 5) << std::endl;
  return 0;
}

Output

The number of permutations of 10 elements with 5 fixed is: 11088

Parameters

n	the size of the permutation
m	the number of fixed objects

Returns

the number of permutations of n items with m fixed

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.