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

learn more… | top users | synonyms

3
votes
2answers
213 views

Derangements property

It is not difficult to evaluate a formula for the number of derangements, with a simple combinatorical argument we get $D(n)=(n-1)(D(n-1)+D(n-2)), n\ge 3$ where $D(n)$ is the number of derangements. ...
9
votes
2answers
154 views

Cocktail bar problem

Recently I went out with friends and we asked ourselves the following question: Consider $n$ people sitting at a cocktail bar next to each other. How many rearrangements have to be made to ensure that ...
7
votes
0answers
191 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
1
vote
2answers
280 views

Permutations in Two Rows

I have been looking at linear and circular permutations. I have now come across a question that entails permutations in two rows. This is the question: Six natives and two foreigners are seated in a ...
0
votes
1answer
157 views

Anti-Symmetric Complex Polynomial

Let $f(x_1,...,x_n)$ be a complex polynomial. Show the following two conditions on $f$ are equivalent: i) for any transpositions $\tau$ we have $\tau.f=-f$ and ii) for any $\sigma \in S_n$ we have ...
6
votes
4answers
85 views

Permutations under Complex Numbers

The question stands: Let $S=\mathbb{C}-\{1,0\}$. Describe the subgroup of $\operatorname{Perm}(S)$ generated by the functions: $f:S\rightarrow S, z\mapsto 1-z$ and $g:S\rightarrow S, z\mapsto ...
1
vote
2answers
50 views

Why cannot the permutation $f^{-1}(1,2,3,5)f$ be even

Please help me to prove that if $f\in S_6$ be arbiotrary permutation so the permutation $f^{-1}(1,2,3,5)f$ cannot be an even permutation. I am sure there is a small thing I am missing it. Thank you.
4
votes
1answer
41 views

from product of swaps to product of disjoint cycles

I have permutation represented in this form: $X=(8,9)(14,15)(12,14)(13,15)$ Can I do the following steps? $$X=(8,9)(14,15)(12,14)(13,15)\\ =(8,9)(14,12,15)(13,15)\\ =(8,9)(15,13,14,12)$$ I think ...
3
votes
2answers
592 views

Calculating the power of permutations

I have this permutation $A$: $$ \left(\begin{array}{rrrrrrrrrr} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 8 & 5 & 2 & 3 & 1 & 6 & ...
0
votes
3answers
203 views

Odd permutations example

How to prove that this permutation: p=(1,10,9,7,6)(2,8,4)(3,5) is odd. Thanks much!
4
votes
2answers
272 views

“Randomize” output of a Linear Feedback Shift Register for the same taps?

I'm using a (Galois) LFSR to sample a large array, ensuring that each entry is only visited once. I simply skip past the entries that exceed the array length. With the same taps then the array entry ...
3
votes
0answers
62 views

Consider $P(n)$ as a number of $n$-permutations, which each cycle have even length, and … [duplicate]

Consider $P(n)$ as a number of $n$-permutations, which each cycle have even length, and $N(n)$ as a number of $n$-permutations, which each cycle have odd length. Calculate $P(2n)-N(2n)$
3
votes
1answer
87 views

computing a limit of a ratio of derangements

Fix $m$. Consider $\lbrace 1,\ldots ,n\rbrace$. Let $a_1\dots a_n$ be a permutation of this set. How many permutations are there such that $a_i\not=i$ for all $i$ and each $i$ travels at most $m$ ...
1
vote
1answer
113 views

Minimum number of moves to convert a list of any integers into a permutation

Given a list of integers of size n, how to find the minimum number of moves to convert it to a Permutation? In one move, we are allowed to decrease or increase any element of the list by one. For ...
0
votes
2answers
417 views

Combinatorics: How to find the number of sets of numbers in increasing order?

The problem is the following one: Let $n$ and $m$ be natural numbers and $m < n$. Find $m$-permutations of the set $\{1, 2,\dots, n\}$ such that permutations are in non-decreasing order (for both ...
6
votes
2answers
4k views

How many possible iPhone passwords?

A standard iPhone has $10$ digits (ranging from $0$ to $9$) Consider a user who has oily fingers (which is normal for an average user) and he unlocks the iPhone by pressing the numbers on the number ...
3
votes
1answer
388 views

Find the number of permutations in these words

Finding the number of permutations in these three words, am I doing this correctly? a) CORRECT: $\;\dfrac{7!}{2!\cdot2!} = 1260$ b) COEFFICIENT: $\;\dfrac{11!}{2!\cdot2!\cdot2!\cdot2!} = 2494800$ ...
0
votes
1answer
51 views

Permutations - bug in Wolfram Alpha?

I've got question whether Wolfram Alpha has bug in showing permutations. Check permutation rules, list, and two-line notation in this permutation. I'd expect same result as was on Wolfram Alpha blog ...
2
votes
2answers
40 views

number of ways poker card question

I am having difficulties to calculate the number of ways 11 poker card can be chosen such that two cards of one suit, two cards of another suit, four cards of another suit, three cards of another ...
1
vote
2answers
143 views

Notation of permutation

I have a question about the notation of the permutation. I am looking at a proof that shows composition of two permutations is a permutation. There it says, let us assume the contrary, let ...
8
votes
1answer
469 views

Literature on group theory of Rubik's Cube

While searching for literature on the group theory of Rubik's Cube, I mostly find introductions to group theory motivated by applications to Rubik's cube. I.e. the focus lies on elementary group ...
3
votes
2answers
1k views

Efficient method to determine the order of a permutation in $S_n$

Instead of trying multiplication again and again until I get $(1)(2)(3)(4)(5)(6)(7),$ is there an efficient, logical method to compute order of $(157)(134)(12)$ of $S_{10}$? Is there some relation to ...
4
votes
3answers
1k views

Is there a quick trick to write permutations of $S_n$ as products of transpositions?

If I want to write $(123)$ as product of transpositions, I get $(13)(12)$. For $(132)$ I get $(12)(13)$. For $(1234)$, I get $(14)(13)(12)$. Seems like I can write $(abcd)$ as $(ad)(ac)(ab)$. Is this ...
0
votes
1answer
59 views

Is there a known distribution for this permutation with replacement problem? [duplicate]

Choose $t$ numbers from $n$ $(n>t)$ distinct numbers with replacement and the order of the $t$ numbers matters. Say, $P(X=1) = \dfrac{{numbers\ of\ unique\ t-set \ which\ has\ 1\ distinct\ ...
2
votes
2answers
2k views

Solve for numbers to appear on two six-sided dice

I have a small wooden calendar that uses two six-sided dice to display day of month. One die carries numbers 0, 1, 2, 6, 7, 8 and the other carries 0, 1, 2, 3, 4, 5. The six of course doubles as the ...
0
votes
2answers
35 views

Relation between binomials

how can I prove that the following relation is true: $$\binom{x-2}y+2\binom{x-2}{y-1}+\binom{x-2}{y-2}=\binom{x}y$$ Thank you for hints or references! Marted
3
votes
1answer
237 views

Number of Permutations Fixed by the Fundamental Transformation is Fibonacci

Writing a permutation in $S_n$ as a product of disjoint cycles, we define a standard representation by writing each cycle with its largest element first, and ordering the cycles by the increasing ...
4
votes
1answer
367 views

Finding a permutation, and number of, from powers of the permutation

Sorry for the vagueness of the title, I couldn't think of a better way to put it. I just wanted to run a couple of simple questions past SE to check my reasoning is correct etc. Find a permutation ...
2
votes
1answer
96 views

Algebra, groups and permutations

The question asks for me to write down the permutations on the set $\{1,2,3,4\}$ which are symmetries of the square with vertices as shown. Hence show that $D_4$ is a subgroup of $S_4$. 1 2 4 ...
1
vote
4answers
311 views

Combinations of consecutive digits

Find the number of passwords that use 3, 4, 5, 6, 7, 8, 9 exactly once. I think I solved this part: it's 7! Next question is: in how many of those 7! are the three even digits consecutive? I been ...
1
vote
2answers
56 views

Assigning values to permutations

N objects can be arranged in N! different orders. For example, 10 playing cards can be stacked 10! = 3,628,800 different ways. Is there a way to assign a numerical value to each permutation so that ...
0
votes
1answer
118 views

Number of $k$-cycles in permutations of $[2k]$?

What is the expectation of the number of $k$-cycles in a randomly selected permutation of $[2k] = {1,2, . . . ,2k}$?
0
votes
2answers
218 views

A step in finding the determinant of transpose of a matrix

The following question involves the permutation group, which I am horrible at handling. Any help will be greatly appreciated. Let $A$ be an $n \times n$ matrix with entries $(a_{ij})_{i = 1,2 \cdots, ...
1
vote
0answers
82 views

Permutation and combination with males/females

There are $6$ males and $6$ females in the finals of a talent competition. A contest is held to pick the top $3$ winners in both the male and female categories in order of merit. How many different ...
2
votes
2answers
196 views

Combinatorics And Music [closed]

What's the likelihood that we'll run out of different songs to be able to make? I know this seems like a difficult question to answer, possibly. But I was just wondering, and I thought of a scale of ...
3
votes
3answers
176 views

Counting ways to arrange envelopes by inclusion (from Stanley's Enumerative Combinatorics)

This is a question from supplement( Bijective proof problems ) to the Stanley's Enumerative Combinatorics. The question statement goes like this. "In how many ways can $n$ square envelopes of ...
1
vote
2answers
212 views

Combinatorics: counting sums with conditions

Hi guys, Here's a combinatorial nut to crack. I've been struggling with this one: Count the number of ways summing a set of $n$ non negative integers $i_1, \cdots, i_n \in \{ 0, \cdots , n-1\} $ so ...
3
votes
1answer
164 views

What is the number of even and odd permutations that satisfies the following condition?

Let $\phi$ be a permutation of $n$ numbers with $\phi(1)=1$ and $\phi(2)=2$. It is asked to prove that the number of odd permutations of $n$ numbers that commute with $\phi$ is equal to the number of ...
1
vote
1answer
245 views

Equation to find possible combinations of combining lists while retaining order

Lets say I have two ordered lists of size n, [A1, A2, ..., An] and [B1, B2, ...,Bn]. I want to find all the possible ...
6
votes
1answer
101 views

On the precise asymptotic scaling of $n!/(n-k)!$ as $n,k \to \infty$

On page 23 of [Erdős+Rényi 1960, "On the evolution of random graphs"], the following asymptotic formula is stated without proof: $$ \binom{n}{k} \sim \frac{n^k \mathrm e^{-\frac{k^2}{2n} - ...
1
vote
0answers
207 views

Possible paths in 3×8 GRID (from Brilliant.org)

Let G be a rectangular grid of unit squares with 3 rows and 8 columns. How many self-avoiding walks are there from the bottom left square of G to the top left square of G? A self-avoiding walk on a ...
3
votes
3answers
514 views

Showing that a transitive abelian permutation group is necessarily regular

I am trying to show that a transitive, abelian permutation group acting on a set $X$ is necessarily regular, given this hint: 'Given $g \in G$, consider the set $X^g:=\{x \in X\,|\,gx=x\}$. Show that ...
1
vote
1answer
97 views

The set that a group can act on it as a permutation group

What can we say about the set that a group can act on it as a permutation group? My question is about the structure of elements of a group G when acts on an arbitrary set Ω as a permutation group. For ...
8
votes
2answers
376 views

Probability of opening all piggy banks

Interesting problem I found, and can't solve it since the morning: We have $n$ keys and $n$ piggy banks. Each key fits only one piggy bank. We randomly put exactly one key in each piggy bank. Then ...
0
votes
3answers
158 views

combination with repetition or permutation $n$=5

I have 5 types of symptoms, I want to know all kind of combinations a patient could have: The set is $(vomit, excrement, urine, dizzyness, convulsion)$ As patient can show only one, or even 5 of ...
4
votes
1answer
10k views

How to write permutations as product of disjoint cycles and transpositions

$$\sigma=\begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 4&2&9&10&6&5&11&7&8&1&3 \end{pmatrix}$$ (1) I am ...
7
votes
3answers
156 views

Problem involving permutation matrices from Michael Artin's book.

Let $p$ be the permutation $(3 4 2 1)$ of the four indices. The permutation matrix associated with it is $$ P = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 ...
3
votes
0answers
40 views

Bound on Permutations [duplicate]

I am trying to prove the following inequality, $$n^{(l)} = n(n-1)\cdots(n-l+1) \geq \frac{n^l}{e}\quad\text{ for }\quad 2 \leq l \leq \sqrt{n}\;.$$ So my approach is to observe that $n^{(l)} = ...
5
votes
2answers
311 views

Generators of Symmetric and Alternating Group

Consider the symmetric and alternating groups $S_n$ and $A_n$ ($n>2$). 1. Does arbitrary $2$-cycle and an arbitrary $n$-cycle in $S_n$ generates $S_n$? 2. If $n$ is odd, does an arbitrary ...
0
votes
2answers
182 views

Finding all permutations containing B elements from a set of size A elements

Given a set A containing {x, y, z}, how many permutations can we obtain that contain B elements, all drawn from the set A(with repetition)? eg. given A = {x, y, z} and a target number of elements B=5 ...