Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [permutations]

For questions related to permutations, which can be viewed as re-ordering a collection of objects.

The word permutation has several possible meanings, based on context. In combinatorics, a permutation is generally taken to be a sequence containing every element from a finite set exactly once. Permutations of a finite set can be thought of as exactly the ways in which the elements of the set can be ordered.

In group theory, a permutation of a (not necessarily finite) set $S$ is a bijection $\sigma : S \to S$. The set of all permutations of $S$ forms a group under composition, called the symmetric group on $S$.

Reference: Permutation.

12854 questions
1
vote
1 answer

Determining the sign of the following permutation

In my homework, I was asked to determine the sign of the following permutation, $\sigma =\begin{pmatrix} 1 &2 &3 &\cdots &n &n+1 &n+2 &\cdots &2n \\ 1 &3 &5 &\cdots &2n-1 &2 &4 &\cdots &2n \end{pmatrix}$ My plan: Firstly, I try…
Nguyễn Hữu Nam
  • 151
  • 7
1
vote
4 answers

Detailed, Understandable Explanation as to why 0!=1?

I have referred to many websites online regarding the proof, but I haven't understood it at all.. Please do help. As far as I know, $n! = 1 \times 2 \times 3 \times 4 \times \dots \times n$ Then using the same logic, $0!=0$ Then why is it that…
Niharika
  • 1,051
1
vote
0 answers

Backtracking algorithm for permutations

I am looking at the backtracking algorithm for computing permutations, and although I can understand what is happening, I cannot understand how it solves the problem for any value of h elements. How are proofs that algorithm is correct made. Can…
Veak
  • 177
  • 6
1
vote
0 answers

How many ways can $\sum\limits_{i=1}^{n} x_ii = c$ be arranged?

I'm working on a curious math problem I'm trying to figure out how many permutations for a set of n integers (1..n), With the constraint: $\sum\limits_{i=1}^{n} x_ii = c$ Such that c is a known constant, and $x_i$ is one of the whole numbers 1..n…
Blaze
  • 125
1
vote
1 answer

How do I calculate permutations?

Ok in a normal set of N numbers, I might take the length of the number set, like 4 numbers long, raise that to the power of the base numbering scheme 0-9 so 10^4th=10000 and subtract 1. I get that. Suppose I cannot reuse any number in the set. 1-9 I…
j0h
  • 145
1
vote
0 answers

Factorization of permutations on a triple Cartesian product of a set

Let $X$ be a finite set, let's say the numbers from 1 to $N$. We consider permutations on $X^3$, which we can also regard as a bijective map $U: X^3\to X^3$. We say that $U$ is factorizable if there exist bijective maps $A,B,C$, all of them $X^2\to…
Balázs Pozsgay
  • 493
  • 3
  • 9
1
vote
1 answer

Permutation in Enigma machine.

The enigma machine permuted the words by using a plugboard, three rotors, and a reverting drum. View the image by clicking as I don't have permission to upload image The plugboard, the three rotors, and the reverting drum performed permutations on…
Sumit Gupta
  • 207
1
vote
2 answers

Doubt in composition of transpositions.

Read article here to show importance of expressing permutation as product of disjoint transpositions. Have a doubt regarding the notation used. Have found that need an easy way, which is much less confusing It states: Proposition Every permutation…
jiten
  • 4,524
1
vote
0 answers

is the decomposition of a permutation into adjacent transpositions unique?

Is there such an immediate proof to the statement or is it simply not true? Recall that an adjacent transposition is just any transposition $(k\ k+1)$, every permutation $\sigma$ can be written as composition of at least $inv(\sigma)$ adjacent…
NotaChoice
  • 931
  • 3
  • 15
1
vote
0 answers

How do I find a decomposition of a permutation into cycles?

I have the follwing question: Find the decomposition into cycles with disjoint supports, then determine the order and the signature. I have the following cycle: $$\sigma=\left(\begin{array}{rrr}…
user123234
  • 2,885
1
vote
1 answer

How many permutations are there if you have n+1 items, where the extra item can be repeated?

This is a little different than the normal case of permutations with repetition. Basically, let's say we have $n$ numbered balls, and there are $n$ spots. However, we can leave a spot empty if we want. The solution I got was…
A Question Asker
  • 459
1
vote
1 answer

Permutations of the numbers with only two differences

The question is from Pui Ching Invitational Mathematics Competition (2019) My attempt: obvious solution (symmetric form is omitted) $(0,1,2,3,...,n,0)$ [difference: $1 \& n$] $(0,1,3,5,...,2m-1,2m,2m-2,...,0)$ [difference: $1 \&…
Ichungchen
  • 190
1
vote
0 answers

Iterating through the non-commutative powerset.

Everyone knows the powerset. It's extremely useful and I seem to see it everywhere now days. It always seems to be hidden in some problem where if you think about it hard enough you'll see in some way that the powerset is involved. 2^n is an obvious…
Gupta
  • 456
  • 2
  • 4
1
vote
1 answer

Permutations of the first $n$ positive integers with no fixed points among the first $k$ integers

Is there a formula, direct or recursive, for the number of permutations $\sigma$ of $\{1,2,\cdots,n\}$ for which $\sigma(j) \neq j$ for $1 \le j \le k$ ? [For $j>k$ the permutation may or may not fix $j.$] I would also be interested in any kind of…
coffeemath
  • 7,403
1
vote
1 answer

In how many ways $3$ rings can be worn in $2$ fingers if a finger can have any number of rings or no rings at all?

It has been calculated to be $8$, but I don't see how. If the rings are $A, B$ and $C$ then: $\{(A,B), (A,C), (B,A), (B,C), (C,A), (C,B)\}$, that's $6$ ways, then if one finger has all the rings that's $2$ ways $\{ABC,0\}$ and $\{0,ABC\}$, so total…
rdev
  • 59
  • 2
1 2 3
…
69 70