Tag

Sort by:

Ball Picking

Consider an infinite repository containing balls of different types. Then the following table summarizes the number of distinct ways in which balls can be picked for four common definitions of "distinct."type of pickingnamesymbol namesymbolordered samples with replacementstringpowerordered sample without replacementpermutationunordered samples with replacementmultisetmultichooseunordered samples without replacementcombinationbinomial coefficient, choose

Permutation Pattern

Let denote the number of permutations on the symmetric group which avoid as a subpattern, where " contains as a subpattern" is interpreted to mean that there exist such that for ,iff .For example, a permutation contains the pattern (123) iff it has an ascending subsequence of length three. Here, note that members need not actually be consecutive, merely ascending (Wilf 1997). Therefore, of the partitions of , all but (i.e., , , , , and ) contain the pattern (12) (i.e., an increasing subsequence of length two).The following table gives the numbers of pattern-matching permutations of , , ..., numbers for various patterns of length .patternOEISnumber of pattern-matching permutations1A0001421, 2, 6, 24, 120, 720, 5040, ...12A0333121, 5, 23, 119, 719, 5039, 40319, ...A0569861, 10, 78, 588, 4611, 38890, ...1234A1580051, 17, 207, 2279, 24553, ...1324A1580091, 17, 207, 2278, 24527, ...1342A1580061, 17, 208, 2300, 24835, ...The following..

Permutation Involution

An involution of a set is a permutation of which does not contain any permutation cycles of length (i.e., it consists exclusively of fixed points and transpositions). Involutions are in one-to-one correspondence with self-conjugate permutations (i.e., permutations that are their own inverse permutation). For example, the unique permutation involution on 1 element is , the two involution permutations on 2 elements are and , and the four involution permutations on 3 elements are , , , and . A permutation can be tested to determine if it is an involution using InvolutionQ[p] in the Wolfram Language package Combinatorica` .The permutation matrices of an involution are symmetric. The number of involutions on elements is the same as the number of distinct Young tableaux on elements (Skiena 1990, p. 32).In general, the number of involution permutations on letters is given by the formula(1)where is a binomial coefficient (Muir 1960, p. 5),..

Permutation Inversion

A pair of elements is called an inversion in a permutation if and (Skiena 1990, p. 27; Pemmaraju and Skiena 2003, p. 69). For example, in the permutation contains the four inversions , , , and . Inversions are pairs which are out of order, and are important in sorting algorithms (Skiena 1990, p. 27).The total number of inversions can be obtained by summing the elements of the inversion vector. The number of inversions in any permutation is the same as the number of interchanges of consecutive elements necessary to arrange them in their natural order (Muir 1960, p. 1). The value can be found in the Wolfram Language using Signature[p].The number of inversions in a permutation is equal to that of its inverse permutation (Skiena 1990, p. 29; Knuth 1998). If, from any permutation, another is formed by interchanging two elements, then the difference between the number of inversions in the two is always an odd number...

Even Permutation

An even permutation is a permutation obtainable from an even number of two-element swaps, i.e., a permutation with permutation symbol equal to . For initial set 1,2,3,4, the twelve even permutations are those with zero swaps: (1,2,3,4); and those with two swaps: (1,3,4,2, 1,4,2,3, 2,1,4,3, 2,3,1,4, 2,4,3,1, 3,1,2,4, 3,2,4,1, 3,4,1,2, 4,1,3,2, 4,2,1,3, 4,3,2,1).For a set of elements and , there are even permutations, which is the same as the number of odd permutations. For , 2, ..., the numbers are given by 0, 1, 3, 12, 60, 360, 2520, 20160, 181440, ... (OEIS A001710).

Wilf Class

Two patterns and belong to the same Wilf class if for all , where denotes the set of permutations on that avoid the pattern . Two sets having the same Wilf class are said to be Wilf equivalent.

Permutation Index

The index of a permutation is defined as the sum of all subscripts such that , for . MacMahon (1960) proved that the number of permutations of size having index is the same as the number having exactly inversions (Skiena 1990, p. 29). The permutation index can be computed as Index[p] in the Wolfram Language package Combinatorica` .

Eulerian Number

The Eulerian number gives the number of permutations of having permutation ascents (Graham et al. 1994, p. 267). Note that a slightly different definition of Eulerian number is used by Comtet (1974), who defines the Eulerian number (sometimes also denoted ) as the number of permutation runs of length , and hence .The Eulerian numbers are given explicitly by the sum(1)(Comtet 1974, p.  243). The Eulerian numbers satisfy the sum identity(2)as well as Worpitzky's identity(3)Eulerian numbers also arise in the surprising context of integrating the sincfunction, and also in sums of the form(4)(5)where is the polylogarithm function. is therefore given by the coefficient of in(6) has the exponential generating function(7)The Eulerian numbers satisfy the recurrence relation(8)Special cases are given by(9)(10)(11)and summarized in the following table.OEIS, , , ...1A0002950, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...2A0004600,..

Euler Zigzag Number

The number of alternating permutations for elements is sometimes called an Euler zigzag number. Denote the number of alternating permutations on elements for which the first element is by . Then and(1)where is an Entringer number.

Permutation Graph

For a permutation in the symmetric group , the -permutation graph of a labeled graph is the graph union of two disjoint copies of (say, and ), together with the lines joining point of with of (Harary 1994, p. 175).Skiena (1990, p. 28) defines a permutation graph as a graph whose edges correspond exactly to being a permutation inversion is some permutation , i.e., but occurs before in . The above graph corresponds to the permutation , which has permutation inversion . Permutation graphs are implemented as PermutationGraph[p] in the Wolfram Language package Combinatorica` .

Transposition Graph

A transposition graph is a graph whose nodes correspond to permutations and edges to permutations that differ by exactly one transposition (Skiena 1990, p. 9, Clark 2005).The transposition graph has vertex count , edge count (for ), and is regular of degree (Clark 2005). All cycles in transposition graphs are of even length, making them bipartite.The transposition graph of a multiset is always Hamiltonian(Chase 1973).Special cases are summarized in the table below.1singleton graph 22-path graph 3utility graph 4Reye graph

Permutation Cycle

A permutation cycle is a subset of a permutation whose elements trade places with one another. Permutations cycles are called "orbits" by Comtet (1974, p. 256). For example, in the permutation group , (143) is a 3-cycle and (2) is a 1-cycle. Here, the notation (143) means that starting from the original ordering , the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., .There is a great deal of freedom in picking the representation of a cyclic decomposition since (1) the cycles are disjoint and can therefore be specified in any order, and (2) any rotation of a given cycle specifies the same cycle (Skiena 1990, p. 20). Therefore, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), and (2)(143) all describe the same permutation. The following table gives the set of representations for each element of the symmetric group on three elements, , sorted in lowest canonical order (first..

Transposition

An exchange of two elements of an ordered list with all others staying the same. A transposition is therefore a permutation of two elements. For example, the swapping of 2 and 5 to take the list 123456 to 153426 is a transposition. The permutation symbol is defined as , where is the number of transpositions of pairs of elements that must be composed to build up the permutation.

Permutation Ascent

Let be a permutation. Then is a permutation ascent if . For example, the permutation is composed of three ascents, namely , , and .The number of permutations of length having ascents is given by the Eulerian number .The total number of ascents in all permutations of order isgiving the first few terms for , 2, ... as 0, 1, 6, 36, 240, 1800, 15120, ... (OEIS A001286).There is an intimate connection between permutation ascents and permutation runs, with the number of ascents of length in the permutations being equal to the number of permutation runs of length (Skiena 1990, p. 31), or

Derangement

A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place. For example, the only derangements of are and , so . Similarly, the derangements of are , , , , , , , , and . Derangements are permutations without fixed points (i.e., having no cycles of length one). The derangements of a list of elements can be computed in the Wolfram Language usingDerangements[l_List] := With[ {perms = Permutations[l]}, {supp = PermutationSupport /@ perms}, Pick[perms, Length /@ supp, Length[l]]]The derangement problem was formulated by P. R. de Montmort in 1708, and solved by him in 1713 (de Montmort 1713-1714). Nicholas Bernoulli also solved the problem using the inclusion-exclusion principle (de Montmort 1713-1714, p. 301; Bhatnagar 1995, p. 8).Derangements are also called rencontres numbers (named after rencontres solitaire) or complete permutations, and the..

Permutation

A permutation, also called an "arrangement number" or "order," is a rearrangement of the elements of an ordered list into a one-to-one correspondence with itself. The number of permutations on a set of elements is given by ( factorial; Uspensky 1937, p. 18). For example, there are permutations of , namely and , and permutations of , namely , , , , , and . The permutations of a list can be found in the Wolfram Language using the command Permutations[list]. A list of length can be tested to see if it is a permutation of 1, ..., in the Wolfram Language using the command PermutationListQ[list].Sedgewick (1977) summarizes a number of algorithms for generating permutations, and identifies the minimum change permutation algorithm of Heap (1963) to be generally the fastest (Skiena 1990, p. 10). Another method of enumerating permutations was given by Johnson (1963; Séroul 2000, pp. 213-218).The number..

Cyclic Permutation

A permutation which shifts all elements of a set by a fixed offset, with the elements shifted off the end inserted back at the beginning. For a set with elements , , ..., , a cyclic permutation of one place to the left would yield , ..., , , and a cyclic permutation of one place to the right would yield , , , ....The mapping can be written as for a shift of places. A shift of places to the left is implemented in the Wolfram Language as RotateLeft[list, k], while a shift of places to the right is implemented as RotateRight[list, k].

Partial Derangement

A permutation of distinct, ordered items in which none of the items is in its original ordered position is known as a derangement. If some, but not necessarily all, of the items are not in their original ordered positions, the configuration can be referred to as a partial derangement (Evans et al. 2002, p. 385).Among the possible permutations of distinct items, examine the number of these permutations in which exactly items are in their original ordered positions. Then(1)(2)(3)where is a binomial coefficient and is the subfactorialHere is a table of the number of partial derangements for , 1, ..., 8:(4)(OEIS A098825).

Contained Pattern

A subset of a permutation is said to contain if there exist such that is order isomorphic to . Here, is the symmetric group on elements.In other words, contains iff any k-subset of is order isomorphic to .

Odd Permutation

An odd permutation is a permutation obtainable from an odd number of two-element swaps, i.e., a permutation with permutation symbol equal to . For initial set 1,2,3,4, the twelve odd permutations are those with one swap (1,2,4,3, 1,3,2,4, 1,4,3,2, 2,1,3,4, 3,2,1,4, 4,2,3,1) and those with three swaps (2,3,4,1, 2,4,1,3, 3,1,4,2, 3,4,2,1, 4,1,2,3, 4,3,1,2).For a set of elements and , there are odd permutations (D'Angelo and West 2000, p. 111), which is the same as the number of even permutations. For , 2, ..., the numbers are given by 0, 1, 3, 12, 60, 360, 2520, 20160, 181440, ... (OEIS A001710).

Combination Lock

Consider a combination lock consisting of buttons that can be pressed in any combination (including multiple buttons at once), but in such a way that each number is pressed exactly once. Then the number of possible combination locks with buttons is given by the number of lists (i.e., ordered sets) of disjoint nonempty subsets of the set that contain each number exactly once. For example, there are three possible combination locks with two buttons: , , and . Similarly there are 13 possible three-button combination locks: , , , , , , , , , , , , . satisfies the linear recurrence equation(1)with . This can also be written(2)(3)where the definition has been used. Furthermore,(4)(5)where are Eulerian numbers. In terms of the Stirling numbers of the second kind ,(6) can also be given in closed form as(7)where is the polylogarithm. The first few values of for , 2, ... are 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (OEIS A000670).The quantity(8)satisfies..

Stirling Number of the First Kind

The signed Stirling numbers of the first kind are variously denoted (Riordan 1980, Roman 1984), (Fort 1948, Abramowitz and Stegun 1972), (Jordan 1950). Abramowitz and Stegun (1972, p. 822) summarize the various notational conventions, which can be a bit confusing (especially since an unsigned version is also in common use). The signed Stirling number of the first kind is are returned by StirlingS1[n, m] in the Wolfram Language, where they are denoted .The signed Stirling numbers of the first kind are defined such that the number of permutations of elements which contain exactly permutation cycles is the nonnegative number(1)This means that for and . A related set of numbers is known as the associated Stirling numbers of the first kind. Both these and the usual Stirling numbers of the first kind are special cases of a general function which is related to the number of cycles in a permutation.The triangle of signed Stirling numbers of the..

Necklace

In the technical combinatorial sense, an -ary necklace of length is a string of characters, each of possible types. Rotation is ignored, in the sense that is equivalent to for any .In fixed necklaces, reversal of strings is respected, so they represent circular collections of beads in which the necklace may not be picked up out of the plane (i.e., opposite orientations are not considered equivalent). The number of fixed necklaces of length composed of types of beads is given by(1)where are the divisors of with , , ..., , is the number of divisors of , and is the totient function.For free necklaces, opposite orientations (mirror images) are regarded as equivalent, so the necklace can be picked up out of the plane and flipped over. The number of such necklaces composed of beads, each of possible colors, is given by(2)For and an odd prime, this simplifies to(3)A table of the first few numbers of necklaces for and follows. Note that is larger than for . For..

Combination

The number of ways of picking unordered outcomes from possibilities. Also known as the binomial coefficient or choice number and read " choose ,"where is a factorial (Uspensky 1937, p. 18). For example, there are combinations of two elements out of the set , namely , , , , , and . These combinations are known as k-subsets.The number of combinations can be computed in the Wolfram Language using Binomial[n, k], and the combinations themselves can be enumerated in the Wolfram Language using Subsets[Range[n],k].Muir (1960, p. 7) uses the nonstandard notations and .

Mousetrap

A permutation problem invented by Cayley. Let the numbers 1, 2, ..., be written on a set of cards, and shuffle this deck of cards. Now, start counting using the top card. If the card chosen does not equal the count, move it to the bottom of the deck and continue counting forward. If the card chosen does equal the count, discard the chosen card and begin counting again at 1. The game is won if all cards are discarded, and lost if the count reaches .The number of ways the cards can be arranged such that at least one card is in the proper place for , 2, ... are 1, 1, 4, 15, 76, 455, ... (OEIS A002467).

Circular Permutation

The number of ways to arrange distinct objects along a fixed (i.e., cannot be picked up out of the plane and turned over) circle isThe number is instead of the usual factorial since all cyclic permutations of objects are equivalent because the circle can be rotated.For example, of the permutations of three objects, the distinct circular permutations are and . Similarly, of the permutations of four objects, the distinct circular permutations are , , , , , and . Of these, there are only three free permutations (i.e., inequivalent when flipping the circle is allowed): , , and . The number of free circular permutations of order is for , 2, andfor , giving the sequence 1, 1, 1, 3, 12, 60, 360, 2520, ... (OEIS A001710).

Married Couples Problem

Also called the ménage problem. In how many ways can married couples be seated around a circular table in such a manner than there is always one man between two women and none of the men is next to his own wife? The solution (Ball and Coxeter 1987, p. 50) uses discordant permutations and was solved by Laisant, Moreau, and Taylor. The solution for can be given in terms of Laisant's recurrence formulawith and (Dörrie 1965, p. 33).A closed form expression for in terms of a sum due to Touchard (1953) iswhere is a binomial coefficient (Comtet 1974, p. 185; Vardi 1991, p. 123).The first few values of for , 3, ... obtained from the recurrence and sum above are 0, 1, 2, 13, 80, 579, ... (OEIS A000179), which are sometimes called ménage numbers. The desired solution is then . The numbers can be considered a special case of a restricted rooks problem...

Siteswap

A siteswap is a sequence encountered in juggling in which each term is a positive integer, encoded in binary. The transition rule from one term to the next consists of changing some 0 to 1, subtracting 1, and then dividing by 2, with the constraint that the division by two must be exact. Therefore, if a term is even, the bit to be changed must be the units bit. In siteswaps, the number of 1-bits is a constant.Each transition is characterized by the bit position of the toggled bit (denoted here by the numeral on top of the arrow). For example,The second term is given from the first as follows: 000111 with bit 5 flipped becomes 100111, or 39. Subtract 1 to obtain 38 and divide by two to obtain 19, which is 10011.

Lexicographic Order

An ordering for the Cartesian product of any two sets and with order relations and , respectively, such that if and both belong to , then iff either 1. , or 2. and . The lexicographic order can be readily extended to cartesian products of arbitrary length by recursively applying this definition, i.e., by observing that .When applied to permutations, lexicographic order is increasing numerical order (or equivalently, alphabetic order for lists of symbols; Skiena 1990, p. 4). For example, the permutations of in lexicographic order are 123, 132, 213, 231, 312, and 321.When applied to subsets, two subsets are ordered by their smallest elements (Skiena 1990, p. 44). For example, the subsets of in lexicographic order are , , , , , , , .Lexicographic order is sometimes called dictionary order...

Bumping Algorithm

Given a permutation of , the bumping algorithm constructs a standard Young tableau by inserting the one by one into an already constructed Young tableau. To apply the bumping algorithm, start with , which is a Young tableau. If through have already been inserted, then in order to insert , start with the first line of the already constructed Young tableau and search for the first element of this line which is greater than . If there is no such element, append to the first line and stop. If there is such an element (say, ), exchange for , search the second line using , and so on.

Langford's Problem

Arrange copies of the digits 1, ..., such that there is one digit between the 1s, two digits between the 2s, etc. For example, the unique (modulo reversal) solution is 231213, and the unique (again modulo reversal) solution is 23421314. Solutions to Langford's problem exist only if , so the next solutions occur for . There are 26 of these, as exhibited by Lloyd (1971). In lexicographically smallest order (i.e., small digits come first), the first few Langford sequences are 231213, 23421314, 14156742352637, 14167345236275, 15146735423627, ... (OEIS A050998).The number of solutions for , 4, 5, ... (modulo reversal of the digits) are 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, ... (OEIS A014552). No formula is known for the number of solutions of a given order .

Secant Number

The secant numbers , also called the zig numbers or the Euler numbers numbers than can be defined either in terms of a generating function given as the Maclaurin series of or as the numbers of alternating permutations on , 4, 6, ... symbols (where permutations that are the reverses of one another counted as equivalent). The first few for , 2, ... are 1, 5, 61, 1385, ... (OEIS A000364).For example, the reversal-nonequivalent alternating permutations on and 4 numbers are , and , , , , , respectively.The secant numbers have the generating function(1)(2)

Avoided Pattern

A pattern is said to avoid if is not contained in . In other words, avoids iff no k-subset of is order isomorphic to .

Prime Circle

A prime circle of order is a free circular permutation of the numbers from 1 to with adjacent pairs summing to a prime. The number of prime circles for , 2, ..., are 1, 1, 1, 2, 48, 512, ... (OEIS A051252). The prime circles for the first few even orders are given in the table below.prime circles2468,

Associated Stirling Number of the First Kind

The associated Stirling numbers of the first kind are defined as the number of permutations of a given number having exactly permutation cycles, all of which are of length or greater (Comtet 1974, p. 256; Riordan 1980, p. 75). They are a special case of the more general numbers , and have the recurrence relation(1)with initial conditions for , and (Appell 1880; Tricomi 1951; Carlitz 1958; Comtet 1974, pp. 256, 293, and 295). The generating function for is given by(2)(Comtet 1974, p. 256). The associated Stirling numbers of the first kind satisfy the sum identity(3)For and a prime,(4)For all integers ,(5)and similarly,(6)(Comtet 1974, p. 256).Special cases of the associated Stirling numbers of the first kind are given by(7)(8)(9)(10)(Comtet 1974, p. 256). The triangle of these numbers is given by(11)(OEIS A008306)...

Inverse Permutation

An inverse permutation is a permutation in which each number and the number of the place which it occupies are exchanged. For example,(1)(2)are inverse permutations, since the positions of 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10 in are , and the positions of 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10 in are likewise (Muir 1960, p. 5).The inverse permutation of a given permutation can be computed in the Wolfram Language using InversePermutation[p].Inverse permutations are sometimes also called conjugate or reciprocal permutations (Muir 1960, p. 4).

Permutation Symbol

The permutation symbol (Evett 1966; Goldstein 1980, p. 172; Aris 1989, p. 16) is a three-index object sometimes called the Levi-Civita symbol (Weinberg 1972, p. 38; Misner et al. 1973, p. 87; Arfken 1985, p. 132; Chandrasekhar 1998, p. 68), Levi-Civita density (Goldstein 1980, p. 172), alternating tensor (Goldstein 1980, p. 172; Landau and Lifshitz 1986, p. 110; Chou and Pagano 1992, p. 182), or signature. It is defined by(1)The permutation symbol is implemented in the WolframLanguage as Signature[list].There are several common notations for the symbol, the first of which uses the usual Greek epsilon character (Goldstein 1980, p. 172; Griffiths 1987, p. 139; Jeffreys and Jeffreys 1988, p. 69; Aris 1989, p. 16; Chou and Pagano 1992, p. 182), the second of which uses the curly variant (Weinberg 1972, p. 38; Misner et al. 1973, p. 87;..

Immanant

For an matrix, let denote any permutation , , ..., of the set of numbers 1, 2, ..., , and let be the character of the symmetric group corresponding to the partition . Then the immanant is defined aswhere the summation is over the permutations of the symmetric group and

Graceful Permutation

A graceful permutation on letters is a permutation such thatFor example, there are four graceful permutations on : , , , and . The number of graceful permutations on letters for , 2, ... are 1, 2, 4, 4, 8, 24, 32, 40, ... (OEIS A006967).

Permutation Run

A set of ascending sequences in a permutation is called a run (Graham et al. 1994) or sometimes a rise (Comtet 1974, p. 241). A sorted permutation consists of a single run, whereas a reverse permutation consists of runs, each of length 1. The permutation runs in a permutation can be computed using Runs[p] in the Wolfram Language package Combinatorica` . The number of permutation runs of the partition of with runs is sometimes denoted (Comtet 1974, p. 241).For example, the permutation contains the single run , while contains the two runs and . The following table lists the permutation runs for each permutation of .permutation runs, , , , , , The number of permutations of length with exactly runs is directly related to the number of permutation ascents, with runs implying ascents (Comtet 1974, p. 241; Skiena 1990, p. 31), sowhere is an Eulerian number.Surprisingly, the expected length of the first run is shorter than the expected..

Alternating Permutation

An alternating permutation is an arrangement of the elements , ..., such that no element has a magnitude between and is called an alternating (or zigzag) permutation. The determination of the number of alternating permutations for the set of the first integers is known as André's problem.The numbers of alternating permutations on the integers from 1 to for , 2, ... are 1, 2, 4, 10, 32, 122, 544, ... (OEIS A001250). For example, the alternating permutations on integers for small are summarized in the following table.alternating permutations1122, 34, , , 410, , , , ,, , , , For , every alternating permutation can be written either forward or reversed, and so must be an even number . The quantity can be simply computed from the recurrence equation(1)where and pass through all integral numbers such that(2), and(3)The numbers are sometimes called the Euler zigzag numbers, and the first few are given by 1, 1, 1, 2, 5, 16, 61, 272, ... (OEIS A000111).The..

Euler Number

The Euler numbers, also called the secant numbers or zig numbers, are defined for by(1)(2)where is the hyperbolic secant and sec is the secant. Euler numbers give the number of odd alternating permutations and are related to Genocchi numbers. The base e of the natural logarithm is sometimes known as Euler's number.A different sort of Euler number, the Euler number of a finite complex , is defined by(3)This Euler number is a topological invariant.To confuse matters further, the Euler characteristic is sometimes also called the "Euler number" and numbers produced by the prime-generating polynomial are sometimes called "Euler numbers" (Flannery and Flannery 2000, p. 47). In this work, primes generated by that polynomial are termed Euler primes.Some values of the (secant) Euler numbers are(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(OEIS A000364).The slightly different convention defined by(16)(17)is..

Random Permutation

A random permutation is a permutation containing a fixed number of a random selection from a given set of elements. There are two main algorithms for constructing random permutations. The first constructs a vector of random real numbers and uses them as keys to records containing the integers 1 to . The second starts with an arbitrary permutation and then exchanges the th element with a randomly selected one from the first elements for , ..., (Skiena 1990).A random permutation on the integers can be implemented in the Wolfram Language as RandomSample[Range[n]]. A random permutation in the permutation graph pg can be computed using RandomPermutation[pg], and such random permutations by RandomPermutation[pg, n]. random permutations in the symmetric group of order can be computed using RandomPermutation[d, n].There are an average of permutation inversions in a permutation on elements (Skiena 1990, p. 29). The expected number of permutation..

Tangent Number

The tangent numbers, also called a zag number, andgiven by(1)where is a Bernoulli number, are numbers that can be defined either in terms of a generating function given as the Maclaurin series of or as the numbers of alternating permutations on , 3, 5, 7, ... symbols (where permutations that are the reverses of one another counted as equivalent). The first few for , 2, ... are 1, 2, 16, 272, 7936, ... (OEIS A000182).For example, the reversal-nonequivalent alternating permutations on and 3 numbers are , and , , respectively.The tangent numbers have the generating function(2)(3)(4)Shanks (1967) defines a generalization of the tangent numbers by(5)where is a Dirichlet L-series, giving the special case(6)The following table gives the first few values of for , 2, ....OEIS1A0001821, 2, 16, 272, 7936, ...2A0004641, 11, 361, 24611, ...3A0001912, 46, 3362, 515086, ...4A0003184, 128, 16384, 4456448, ...5A0003204, 272, 55744, 23750912, ...6A0004116,..

Symmetric Group

The symmetric group of degree is the group of all permutations on symbols. is therefore a permutation group of order and contains as subgroups every group of order .The th symmetric group is represented in the Wolfram Language as SymmetricGroup[n]. Its cycle index can be generated in the Wolfram Language using CycleIndexPolynomial[SymmetricGroup[n], x1, ..., xn]. The number of conjugacy classes of is given , where is the partition function P of . The symmetric group is a transitive group (Holton and Sheehan 1993, p. 27).For any finite group , Cayley's group theorem proves is isomorphic to a subgroup of a symmetric group.The multiplication table for is illustrated above.Let be the usual permutation cycle notation for a given permutation. Then the following table gives the multiplication table for , which has elements.(1)(2)(3)(1)(23)(3)(12)(123)(132)(2)(13)(1)(2)(3)(1)(2)(3)(1)(23)(3)(12)(123)(132)(2)(13)(1)(23)(1)(23)(1)(2)(3)(132)(2)(13)(3)(12)(123)(3)(12)(3)(12)(123)(1)(2)(3)(1)(23)(2)(13)(132)(123)(123)(3)(12)(2)(13)(132)(1)(2)(3)(1)(23)(132)(132)(2)(13)(1)(23)(1)(2)(3)(123)(3)(12)(2)(13)(2)(13)(132)(123)(3)(12)(1)(23)(1)(2)(3)This..

Permutation Group

A permutation group is a finite group whose elements are permutations of a given set and whose group operation is composition of permutations in . Permutation groups have orders dividing .Two permutations form a group only if one is the identity element and the other is a permutation involution, i.e., a permutation which is its own inverse (Skiena 1990, p. 20). Every permutation group with more than two elements can be written as a product of transpositions.Permutation groups are represented in the Wolfram Language as a set of permutation cycles with PermutationGroup. A set of permutations may be tested to see if it forms a permutation group using PermutationGroupQ[l] in the Wolfram Language package Combinatorica` .Conjugacy classes of elements which are interchangedin a permutation group are called permutation cycles.Examples of permutation groups include the symmetric group (of order ), the alternating group (of order for ),..

Factorial

The factorial is defined for a positive integer as(1)So, for example, . An older notation for the factorial was written (Mellin 1909; Lewin 1958, p. 19; Dudeney 1970; Gardner 1978; Conway and Guy 1996).The special case is defined to have value , consistent with the combinatorial interpretation of there being exactly one way to arrange zero objects (i.e., there is a single permutation of zero elements, namely the empty set ).The factorial is implemented in the Wolfram Language as Factorial[n] or n!.The triangular number can be regarded as the additive analog of the factorial . Another relationship between factorials and triangular numbers is given by the identity(2)(K. MacMillan, pers. comm., Jan. 21, 2008).The factorial gives the number of ways in which objects can be permuted. For example, , since the six possible permutations of are , , , , , . The first few factorials for , 1, 2, ... are 1, 1, 2, 6, 24, 120, ... (OEIS A000142).The..

Birthday Problem

Consider the probability that no two people out of a group of will have matching birthdays out of equally possible birthdays. Start with an arbitrary person's birthday, then note that the probability that the second person's birthday is different is , that the third person's birthday is different from the first two is , and so on, up through the th person. Explicitly,(1)(2)But this can be written in terms of factorials as(3)so the probability that two or more people out of a group of do have the same birthday is therefore(4)(5)In general, let denote the probability that a birthday is shared by exactly (and no more) people out of a group of people. Then the probability that a birthday is shared by or more people is given by(6)In general, can be computed using the recurrence relation(7)(Finch 1997). However, the time to compute this recursive function grows exponentially with and so rapidly becomes unwieldy.If 365-day years have been assumed, i.e.,..

Subfactorial

The th subfactorial (also called the derangement number; Goulden and Jackson 1983, p. 48; Graham et al. 2003, p. 1050) is the number of permutations of objects in which no object appears in its natural place (i.e., "derangements").The term "subfactorial "was introduced by Whitworth (1867 or 1878; Cajori 1993, p. 77). Euler (1809) calculated the first ten terms.The first few values of for , 2, ... are 0, 1, 2, 9, 44, 265, 1854, 14833, ... (OEIS A000166). For example, the only derangements of are and , so . Similarly, the derangements of are , , , , , , , , and , so .Sums and formulas for include(1)(2)(3)(4)where is a factorial, is a binomial coefficient, and is the incomplete gamma function.Subfactorials are implemented in the WolframLanguage as Subfactorial[n].A plot the real and imaginary parts of the subfactorial generalized to any real argument is illustrated above, with the usual integer-valued subfactorial..

Check the price
for your project
we accept
Money back
guarantee
100% quality