What is Permutation: Definition and 275 Discussions

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory.
Permutations are used in almost every branch of mathematics, and in many other fields of science. In computer science, they are used for analyzing sorting algorithms; in quantum physics, for describing states of particles; and in biology, for describing RNA sequences.
The number of permutations of n distinct objects is n factorial, usually written as n!, which means the product of all positive integers less than or equal to n.
Technically, a permutation of a set S is defined as a bijection from S to itself. That is, it is a function from S to S for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of S in which each element s is replaced by the corresponding f(s). For example, the permutation (3,1,2) mentioned above is described by the function


{\displaystyle \alpha }
defined as:




{\displaystyle \alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2}
.The collection of all permutations of a set form a group called the symmetric group of the set. The group operation is the composition (performing two given rearrangements in succession), which results in another rearrangement. As properties of permutations do not depend on the nature of the set elements, it is often the permutations of the set



{\displaystyle \{1,2,\ldots ,n\}}
that are considered for studying permutations.
In elementary combinatorics, the k-permutations, or partial permutations, are the ordered arrangements of k distinct elements selected from a set. When k is equal to the size of the set, these are the permutations of the set.

View More On Wikipedia.org
  1. RChristenk

    In how many ways can 5 prizes be given away to 4 boys?

    I first thought obviously the solution would be ##5^4##. This made intuitive sense to me because this solution means the first boy can choose one out of five prizes, the second boy can choose one out of five (even if it's the same prize as the first boy's since each boy is eligible for all...
  2. Memo

    Combination, partial permutation

    a) p=(4C1*6C2)/(10C3)=0.5 b) p=(4C1*6C2)/(10C3) + (4C2*6C1)/(10C3) + (4C3*6C0)/(10C3)=0.83 Please check if my answer is correct. Thank you very much.
  3. S

    Question about permutation formula -- How to use the formula when r = 0 ?

    ##P^5_0=\frac{5!}{(5-0)!}=1## But when I use ##P^n_r=n(n-1)...(n-r+1)##, I get ##P^5_0=5(4)...(6)## Where is the mistake? Thanks
  4. DaveC426913

    B Simple Combo/Permute calculation

    I'm playing a Steam game called Shapez wherein the goal is to produce and deliver given shapes to the Hub by conveyor belt. In the screencap you can see resources of discs and squares and well as green and red, which are to be extracted, chopped up and recombined to form the "product"...
  5. nomadreid

    I Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction

    There is a proof that shows by induction (and by contradiction) that the identity permutation decomposes into an even number of transpositions. The proof is presented in the first comment here...
  6. nomadreid

    I Cycles from patterns in a permutation matrix

    In a permutation matrix (the identity matrix with rows possibly rearranged), it is easy to spot those rows which will indicate a fixed point -- the one on the diagonal -- and to spot the pairs of rows that will indicate a transposition: a pair of ones on a backward diagonal, i.e., where the...
  7. chwala

    Solve the given permutation problem

    My First approach on this; The last digit should be a ##0## or a ##5##. Therefore the first ##4## slots can be filled in ##_9P_4×1## ways = ##3024##. Secondly, we also note that ##0## cannot be on the first slot as this would imply ##4## digits instead of ##5##...further the last slot has to...
  8. DaveC426913

    B Tournament Permutation Problem

    I've got ten teams, five boards, and only three nights to figure out who's the best team. We've had our regular season, so we have the teams ranked. (i.e. 1st place in regular season gets to play against last place, etc.) Can we get a fair score out of 10 teams in three nights? (Is that...
  9. C

    Comp Sci Validating Braces Placement for Expression Evaluation

    Here's what I've done: Mentor note: replaced icode tags with code=python and \code pair. def valid_braces_placement(s, L): if len(L)==0: return False string = '' for element in L: string = string + str(element) D = ['+','-','*'] return...
  10. DaalChawal

    MHB Vowel-Consonant Arrangements and Non-Adjacent Vowels

    Question itself and options 1 and 3.
  11. DaalChawal

    MHB How Does the Number of Metro Stations Affect the Color of Connecting Lines?

    Let n > 2 be an integer. Suppose that there are n Metro stations in a city located along a circular path. Each pair of stations is connected by a straight track only. Further, each pair of nearest stations is connected by blue line, whereas all remaining pairs of stations are connected by red...
  12. M

    MHB QR decomposition with permutation matrix

    Hey! :giggle: At the QR-decomposition with permutation matrix is the matrix $R$ equal to $R=G_3^{-1}P_1G_2^{-1}P_0G_1^{-1}A$ or $G_3P_1G_2P_0G_1A=R$? Which is the correct one? Or are these two equivalent? In general, it holds that $QR=PA$, right? :unsure:
  13. Kaguro

    Identity permutation as product of even number of 2-cycles

    The book I'm following (Gallian) basically says: r can't be 1 since then it won't map all elements to themselves. If r=2, then it's already even, nothing else to do. If r>2, Then consider the last two factors: ##\beta_{r-1} \beta_r##. Let the last one be (ab). Since the order of elements...
  14. V

    I Combination or Permutation Calculation

    Hello Forum: I have numbers 1 through 6 from which i must select 4 items. The twist is that i need to count only those subsets that include the number 2 all of the subsets are 'distinct' --> 2145 is the same as 2415. My quick calculation yields 15 distinct subsets however some of those do...
  15. sahilmm15

    B A problem of circular permutation

    I have understood everything till 2nd paragraph. But after that everything was above my head. Can you explain me the concept
  16. S

    I Is there a theorem that a set of binary swaps can affect any permutation?

    Is there a theorem that states that a set of binary swaps can result in any permutation? For example, the original set (1,2,3,4,5) can have the swap (24) and result in (1,4,3,2,5). is there a set of specific swaps for each net result permutation?
  17. M

    MHB Permutation Problem SWITZERLAND

    Given the word "SWITZERLAND", in how many ways can we rearrange its letters so: a) There is at least one consonant between every vowel b) There is at least least two consonants between every vowel Thanks for your help!
  18. M

    MHB Subsets of permutation group: Properties

    Hey! 😊 Let $G$ be a permutation group of a set $X\neq \emptyset$ and let $x,y\in X$. We define: \begin{align*}&G_x:=\{g\in G\mid g(x)=x\} \\ &G_{x\rightarrow y}:=\{g\in G\mid g(x)=y\} \\ &B:=\{y\in X\mid \exists g\in G: g(x)=y\}\end{align*} Show the following: $G_x$ is a subgroup of $G$. The...
  19. M

    MHB The permutation induces on the set

    Hey! :o I am looking at the following exercise: Make a sketch of a regular tetrahedron and label the corners with the numbers $1, 2, 3, 4$. For $1\leq i\leq 5$ the permutations $\pi_i \in \text{Sym} (4)$ are defined as follows: \begin{align*}&\pi_1:=\text{id} \\ &\pi_2:=(1 \ \ 2) \\...
  20. Z

    MHB Help proving prime and permutation

    https://imgur.com/a/9tDdMqt Hey So I am trying to prove this. I tried using linear combinations and not sure how that would help. I am just not familiar with combinatorics and wondering if anyone would enlighten me.
  21. D

    Permutation Counting Algorithm for Large Integers

    Remark: This is not homework Given a vector a of permuted numbers from 1 to n, I want to construct the vector b which contains in the ith position the number of elemets of a_j with j <i which are larger than a_i. E.g. a=(5,2,3,1,4), b=(0,1,1,3,1). Is there an algorithm which scales faster...
  22. Biochemgirl2002

    How do i answer this permutation question?

    Question: A home security device with 10 buttons is disarmed when three different buttons are pushed in the proper sequence. (No button can be pushed twice.) If the correct code is forgotten, what is the probability of disarming this device? My attempt: 10!/(10-3)! =(...
  23. karush

    MHB How about this? What is the inverse of a permutation cycle?

    $\tiny{412.5.9}$ this is under the section on Permutation Groups What cycle is $(a_1a_2\dots a_n)^{-1}$ ok thot there would be and east theorem on this but can't find
  24. Mr Davis 97

    I Order of a permutation is the lcm of the orders of cycles

    Let ##\sigma \in S_n##, and ##|\sigma| = r##. Then, we'll assume that ##\sigma## can be decomposed into a product of disjoint cycles, which commute with each other. So ##\sigma = c_1c_2 \dots c_k##. Then ##\sigma^r = (c_1c_2 \dots c_k)^r## = 1. Since the cycles commute, we have ##c_1^rc_2^r...
  25. R

    I Permutation of identical elements

    If we have n object and n1,n2,..nk are identical element. And we take r at a time i.e r < n. Is there a general formulae for the permutation of the above. Or how it is solved? Thanks.
  26. S

    Probability (Permutation Combination)

    Homework Statement There are 22 students in a class. The professor will divide the class into 4 groups. Group 1 and 2 have 5 members each whilst Group 3 and 4 have 6. Given that the teacher forms the group at random, find the probabilities of : A = event where Paula, Trina, Gia all belong in...
  27. F

    Multiplying permutation cycles

    Homework Statement Compute each of the following products in ##S_9## (Write your answer as a single permutation). a) (145)(37)(682) Homework Equations Theorem: Every permutation is either the identity, a single cycle, or the product of disjoint cycles. The Attempt at a Solution I start with...
  28. B

    Is Every Element of a Transitive Abelian Permutation Group Not the Identity?

    Homework Statement Assume that ##G## is an abelian transitive subgroup of ##S_A## that acts on the set ##A##. Show that ##\sigma(a) \neq a## for all ##\sigma \in G - \{1\}## and all ##a \in A##. Deduce that ##|G| = |A|##. Homework Equations A group is said to act transitively on a set if...
  29. tze liu

    I Why combination and permutation is useless in physics

    discuss whether combination and permutation in math are useless in physics the undergraduate math courses related to physics always contain algebra,complex number and calculus. however we don't need to study discrete math /combination and permutation in those courses that means those stuffs...
  30. H

    MHB Optimal Seating Arrangement Algorithm for Friendship Graphs

    Hi all, I am struggling the question, please see attachments. Thanks a lot Devise an algorithm which, given a (directed) friendship graph (in the xkcd format), finds the optimal seating arrangement. Your algorithm should include the following:  a description of the required input format...
  31. Konte

    I Permutation group and character table

    Hi everybody, I work currently with permutation group, and with the good advice of this forum I discover GAP software (https://www.gap-system.org/) which is an excellent tools for working with group. My question is about something that is too strange for me: I have a permutation group G...
  32. SSequence

    Row Shuffling and Permutation Question

    The question below could also be re-phrased in terms of functions of one variable (using indexes). However, it seems it is easier to explain it with two variables. Here is the question: Suppose we have some total recursive function f: N x N→N. Define the n-th row of f as the function Fn : N→N...
  33. Telemachus

    Fortran Permutation of indices in fortran

    Hi there. I am working with a numerical quadrature in some scheme to solve a set of equations. At this point I am working in two dimensions. The thing is that I have some function ##\psi_m(x,y,\Omega_m)## with ##\Omega_m=(\Omega_{x,i},\Omega_{y,j})## with ##\displaystyle...
  34. Chadi B Ghaith

    I How to find the nth binary permutation?

    I need to complete this. Let's say I have 4 bits with 2 bits set as 1, 0011. The total number of permutations for this number is 0011, 0101, 0110, 1001, 1010, 1100, 6 cases. This can be computed using the calculation. 4! / ((2!)(4-2)!) = 6 Now I want to be able to find the nth sequence, for...
  35. C

    MHB Permutation question concerning cycle shapes

    Consider the subset of $S_4$ defined by $$K_4=\{(1)(2)(3)(4),(12)(34),(13)(24),(14)(23)\}$$ Show that for all $f \in K_4$ and all $h \in S_4$, we have $h^{-1}fh \in K_4$ I showed all the possible cycle shapes of h and am trying to show that $h^{-1}fh$ must always have cycle shape $(2,2)$...
  36. T

    I Permutation operator and Hamiltonian

    The permutation operator commutes with the Hamiltonian when considering identical particles, which implies: $$ [\hat{P}_{21}, \hat{H}] = 0 \tag{1}$$ Now given a general eigenvector ##{\lvert} {\psi} {\rangle}##, where $$ \hat{P}_{21} (\hat{H}{\lvert}{\psi}){\rangle} = (\hat{P}_{21} \hat{H})...
  37. S

    Largest permutation of elements in the range 1,....,N

    with at most k swaps. (In other words, like the largest number formed by swapping k digits.) Example. A=[4,2,3,5,1], k = 1 ---> [5,2,3,4,1] I'm wondering why my algorithm is failing the test cases which I'm unable to see. using System; using System.Collections.Generic; using System.IO...
  38. N

    MHB Solving equation involving permutation and combination

    Find n if P(n, 3) = 6 C(n, 5). My attempt $\frac{n!}{(n-3)!}=6\frac{n!}{(n-5)5!}$ I don't know how to proceed
  39. K

    How many ways can 12 balls be arranged into 4 different rows

    Homework Statement In how many ways can 12 balls be arranged into 4 different rows with each row having at least one ball (a) if the balls are identical? (b) if there are 6 identical red balls and 6 identical blue balls? Homework EquationsThe Attempt at a Solution a) Put 4 balls in each row...
  40. Y

    Linear Algebra - Elimination Matrix when Permutation Needed

    Homework Statement I feel like I should know the answer to this, so I believe this to be an easy question. Say have matrix A, and I store the elimination matrices E_1,1 E_2,1 etc. and somewhere in the elimination process I have to use a permutation matrix to swap rows. My question is when I...
  41. V

    A permutation and combination problem

    .The number of points, having both co-ordinates as integers, that lie in the interior of the triangle with vertices (0, 0), (0, 41) and (41, 0), is (1) 901 (2) 861 (3) 820 (4) 780 my attempt: for this to be true i know that sum of x and y coordinate should be 41 but i don't know how to proceed.
  42. E

    MHB Choosing a Dissertation Committee: Combination Permutation Dilemma

    I am in a group we cannot agree on how to answer the following word problem... "Let me tell you a little dirty secret about the mutual dislike between mathematicians and physicists. It can escalate into a full blown war if diplomacy is not attempted properly. It happens that a graduate...
  43. M

    How Can I Master Complex Counting Problems Involving Multiple Principles?

    Homework Statement Counting problems are a very tough subject to me, so if someone could give me tips, examples explaining what's really happening, that would be great. Homework Equations I know what permutations, variations, combinations, ... are. The problems involving only one of those...
  44. Q

    I How many combinations of unique arrangements are there?

    If there was a 1 billion x 1 billion x 1 billion cube made of 3D pixel cubes, and half of them are black and half of them are clear/colorless, then how many combinations of unique pixel arrangements are there? Would the amount of shapes/objects in this cube be infinite? (Assuming the black...
  45. Nader AbdlGhani

    How to Factorize a Large Number for Permutations?

    Hey guys , Could anyone here tell me the easiest way to solve for n , nP7 = 604800 , the traditional way (I'm currently using) is to divide 604800 by 10 and then 9 and so on until I get 1 as a result of that division , The problem is this way isn't helpful with all permutations I have in my...
  46. T

    Pascal Permutation Matrix: Find Number of Columns

    Homework Statement I should write a program that determines how many columns of a given matrix are a permutation. The user will input some number N <=20 which will be the size of our matrix NxN. Then he will input the individual elements of the matrix by rows. I need to find out how many...
  47. Crazorin

    Permutation with exception/repetition

    I need a formula to calculate permutation. For example I have a 5 numbers and I creating a 3 digit number from it. The numbers are: 1, 1, 1, 2, 3; I could write up 13 variations, but I couldn't work out the formula. If the numbers are: 1, 1, 2, 2, 3 the number of variations are 18 (if I wrote...
  48. P

    Permutation Proof: Proving (n+1)nPr=(n+1)P(r+1)

    Homework Statement Hello I have to proof this ##(n+1)nPr=(n+1)P(r+1)## The attempt at a solution if i substitute this in ##nPr=\frac{n!}{(n-r)!}## I get this ##(n+1)nPr=\frac{[(n+1)n]!}{[(n+1)n-r]!}## This will give ##(n+1)nPr=\frac{(n^2+n)!}{(n^2+n-r)!}## Now i don't know how to continue.
  49. Matejxx1

    How Can Students Be Arranged into Groups with Set Sizes?

    Homework Statement There are 30 students in a class. In how many ways can we arrange them if : a)we must have three group, group one must have 5 students , group two 10 students and group three 15 students. answer=\frac{30!}{5!*10!*15!} b)we must have three group and all must have 10 students...