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

learn more… | top users | synonyms

1
vote
1answer
448 views

Puzzle of $N$ men around a table

This was asked to me by a friend. $N$ men sit around a circular table. Man 1 has a sword with him and he kills the Man 2, Man 3 picks up this sword and kills the next person i.e. Man 4. Thus the man ...
2
votes
3answers
233 views

Simplify these products of permutations

Can someone please explain how to get these answers? Everytime I think I understand the method, I end up getting a completely different answer to the one provided. How exactly do you go about ...
26
votes
1answer
1k views

Six Frogs - Puzzle

I had come across a puzzle: The six educated frogs in the illustration are trained to reverse their order, so that their numbers shall read 6, 5, 4, 3, 2, 1, with the blank square in its ...
2
votes
1answer
86 views

I want to find a natural faithful action with the wreath product.

Let $A$ and $B$ be any sets. Let $G\leq \operatorname{Sym}(A)$ and $H\leq\operatorname{Sym}(B)$. Can any one find a faithful action of the wreath product $G\wr H$ on $A\times B$? If there is no such ...
5
votes
1answer
195 views

Algorithm creating subsets with certain properties

I'm trying so solve following problem: Let's say, we have a set $A=\{1,2,3,...,49\}$. Now, I am defining sets $A_1, A_2, A_3,...,A_n$ as follow: $A_1=\{a_1,a_2,a_3,...,a_{30}\}$, $A_2= ...
3
votes
0answers
116 views

Is there a simple way to show that wreath product is associative?

Is there a simple way to show that wreath product is associative? If your proof is short, please write it explicitly. Thank you.
0
votes
1answer
64 views

Simple question about combinations

There is this problem I found in a book on combinations. It goes roughly like this: There are 4 type A machines and 5 type B machines. Three of the machines are removed from the piles. What is the ...
10
votes
2answers
1k views

how to find the root of permutation

Observe that $$\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{smallmatrix}\bigr)* \bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ ...
2
votes
1answer
2k views

In how many ways can 5 different toys be packed in 3 identical boxes such that no box is empty, if any of the boxes may hold all of the toys?

The toys are differnt here but the boxees are identical. since no box can be empty we can have two situations for this. ...
1
vote
1answer
206 views

Structure of the centralizer of an element in Sym(n)

Do we know the structure of the centralizer of any element in $S_n$? Or the centralizer of a permutation which has $q$ disjoint $r$-cycles where $r\leq n$. If we know, can anyone give proof or ...
4
votes
1answer
72 views

How many combination can we create from this structure?

I 'm stuck in to this problem and I really need your help. Sorry if the title is not very informative. It is really hard for me to explain it in one sentence. I do my best in explaining it: There ...
2
votes
3answers
2k views

Permutation and Combination with divisibility?

How many five digit positive integers that are divisible by 3 can be formed using the digits 0, 1, 2, 3, 4 and 5, without any of the digits getting repeating? my explanation: total number of ...
10
votes
4answers
212 views

Group Action - Permutation on the Polynomial

I'm trying to check the permutation on the polynomial is a Group Action, but I'm not getting the second axiom. I'm following my lecturer's work --- Examples 2.1 and 2.6 on page 5 on ...
7
votes
1answer
548 views

When does the adjacency or incidence matrix of a graph have consecutive ones property?

Given a graph, what are some sufficient (and necessary) conditions to tell if its adjacency matrix has the consecutive ones property? Similar question for its incidence matrix? Note that a ...
0
votes
1answer
62 views

Worst case probability of a point on 2 circles lining up.

Imagine 2 circles connected at 1 point. The smaller of the circles has n equally spaced points around its perimeter labelled $1...n$. The larger of the circles has $n^2$ equally spaced points around ...
4
votes
0answers
72 views

Expectation of Reciprocals Involving Permutations

Let $a_i$ be $n$ distinct real numbers. What is the expectation: $$\mathbb E_\sigma \left[ \sum_{i=1}^{n} \frac {1} {a_{\sigma(i)} - \sum_{j=1}^{i-1}a_{\sigma(j)}} \right] $$ where the expectation ...
1
vote
1answer
111 views

Possible orders of permutations of 11 symbols

Which of the following numbers can be orders of permutations \alpha of 11 symbols such that it does not fix any symbol? 1. 18, 2. 30, 3. 15, 4. 28
1
vote
1answer
63 views

A group that has a $\frac{3}{2}$-transitive subgroup

Do you know a group that has a $\frac{3}{2}$-transitive subgroup and it is not $\frac{3}{2}$-transitive itself?
4
votes
1answer
461 views

Labeled/unlabeled balls in unlabeled boxes

I was hoping I could receive some clarification into the the four cases: Placing labeled balls in unlabeled boxes with repetition. Placing labeled balls in unlabeled boxes without repetition. ...
1
vote
0answers
60 views

Matrix Representation of Integer Series

I would like some feedback regarding this process or the meaning of this process. Let say that I have a discrete time series: S = [1 2 3 4 5] And that I represent this serie by a stochastic matrix M ...
2
votes
2answers
4k views

How many ways are there to choose 10 objects from 6 distinct types when…

(a) the objects are ordered and repetition is not allowed? (b) the objects are ordered and repetition is allowed? (c) the objects are unordered and repetition is not allowed? (d) the objects are ...
2
votes
1answer
287 views

Permutations in Abstract Algebra

Can an odd permutation be conjugate to an even one? I want to say no, because odd/even permutations have defined cycle types, and conjugation always preserves the cycle type. Is this the correct ...
2
votes
3answers
206 views

Permutations with a cycle $>\frac{n}{2}$

I'm interested in the following question: Let $S_n$ be the set of all permutations over $\{1,...,n\}$. We know that $|S_n|=n!$. How many permutations of this set has a cycle larger than ...
2
votes
1answer
67 views

Expectation Involving Permutation Matrices

Let $L$ be $n\times n$ bidiagonal matrix such that its diagonal is all $1$ and its subdiagonal is all $-1$ (and zero elsewhere). Let $D$ be any diagonal matrix and $x,y$ be any $n$-dimensional column ...
1
vote
3answers
545 views

Three fair six-sided dice are tossed and the numbers showing on top are recorded.

I don't know if they are correct, these are my attempts Three fair six-sided dice are tossed and the numbers showing on top are recorded. How many different record sequences are possible? How many ...
1
vote
1answer
619 views

3-letter arrangement for “silly” - Permutations homework

We a homework question that asks us to find the 3 letter arrangement of the word "Silly". Here is the exact question. How many three-letter arrangements are there of the letters taken from the ...
1
vote
2answers
397 views

Rubik's Cube Combination

Could anyone explain why the number of legal or reachable combinations of a $3\times 3\times 3$ Rubik's Cube is $1/12\mbox{th}$ of the total. I understood the logic behind the total number of ...
-1
votes
1answer
222 views

permutation with cycles

Let $c(n,k)$ be the number of permutations of $[n]$ with $k$ cycles. I am looking for a proof of the following. $c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$ for $n,k \geq 1$ and $c(0,0)=1$ The number of ...
0
votes
1answer
868 views

Proof that computing composition of permutations is in P

Consider the following problem: A permutation on the set ${1,…,k}$ is a one-to-one, onto function on this set. When $p$ is a permutation, $p^t$ means the composition of $p$ with itself $t$ times. ...
1
vote
2answers
139 views

Howto organize a party where everyone meets everyone around a big table?

Ok hi all, my first question! I would like to organize a party where everyone meets everyone, the table is organized like this: ABCD J E IHGF So A can only meet ...
1
vote
3answers
255 views

How many permutations $\tau$ on 8 elements are there such that $\tau\circ\tau$ is the identity permutation?

How many permutations $\tau$ on 8 elements are there such that $\tau\circ\tau$ is the identity permutation? *Details and assumptions You may think of a permutation on 8 elements as a way to shuffle ...
4
votes
1answer
271 views

Combinatorics: $N$ balls of $R$ different colors into $R$ bins

Another balls and bins problem, but I couldn't find one like this after browsing a while. Say I have $N$ balls of $R$ different colors (N/R balls of each color) and I need to put them into $R$ ...
2
votes
1answer
92 views

Calculating $\binom{n}{r} \bmod\; p$ where $p$ is prime and as large as $1000000007$

I am trying to calculate $\binom{n}{r}$ modulo $1000000007$. I have read here about Lucas' Theorem but it seems to work for small values of $p$. Here $p = 1000000007$. Is there a way this can be ...
1
vote
1answer
563 views

Password Permutations

Could somebody answer me how many possibilities are there for a six-letter (only letters, but case-sensitive) computer password? Is it $^{52}C_6 \times 6!$ ?
5
votes
1answer
185 views

How can I apply a Inclusion–exclusion principle in this task?

Simple task from combinatorics: How much sequences does exist, that consist of letters A, B, C, D, ..., O, P; if no sequence could have any of these words: PONK, DOBA, COP. This task is about ...
1
vote
1answer
71 views

How many permutations when each position takes from different length alphabets?

Let's say there's a password scheme as follows: the password is of length 4 (four) the 1st position is taken by one character from the set: a, b, c the 2nd ...
1
vote
1answer
143 views

A puzzle in Permutation.

There are two stacks A and B. A : a,b,c,d ('a' is on top and 'd' is at the bottom of the stack) B : (empty) There are two rules. ...
0
votes
2answers
1k views

Ten people are seated at a rectangular table - Permutations homework

I got the following question for homework. Ten people are to be seated at a rectangular table for dinner. Tanya will sit at the head of the table. Henry must not sit beside either Wilson or ...
1
vote
1answer
181 views

Number of permutations given a sequence of 5 letters that are offset from 1-9

If I have a random sequence of letters "AOKNG", and I'd like to find how many permutations of this can be formed given a character offset from 1-9. So, offset the first character "A" 9 times would ...
1
vote
1answer
171 views

Determining if it is a permutation or a combination for this question

I am having some issues determining if it is a permutation or a combination for the following question. Some help would be really appreciated. A county park system rates its 20 golf courses in ...
6
votes
1answer
422 views

Find all permutations that commute with $\omega$=(1 9 7 10 12 2 5)(4 11)(3 6 8) in $S_{12}$

I'm asked in this exercise to find all permutations that commute with $\omega$=(1 9 7 10 12 2 5)(4 11)(3 6 8) in $S_{12}$. What I have so far: We could write $x$(1 9 7 10 12 2 5)(3 6 8)=(1 9 7 10 12 ...
7
votes
2answers
381 views

Bubble sorting question

Consider that we use the bubble-sorting algorithm to sort a string of size $n$. We know then that the maximum number of swaps results when the string is in reverse order- this gives $\frac{n(n-1)}{2}$ ...
1
vote
0answers
111 views

Card game-ordering a deck [duplicate]

Possible Duplicate: Game Theory Matching a Deck of Cards Suppose we take a blank deck of $52$ cards, write the number $1$ on the first card, $2$ on the second card, and so on until we write ...
3
votes
1answer
123 views

A faster way to show that a subgroup is normal

I'm working with $\mathbb S_4$, and I have a subgroup of $\mathbb S_4$ called $G$. $G$ is generated by $a=(12)(34)$ and $b=(123)$, which I've actually found to be $A_4$ by multiplying elements by $a$ ...
2
votes
3answers
158 views

$S_n$ acting transitively on $\{1, 2, \dots, n\}$

I am reading Dummit and Foote, and in Section 4.1: Group Actions and Permutation Representations they give the following example of a group action: The symmetric group $G = S_n$ acts transitively ...
1
vote
3answers
195 views

Prove that $S_n$ is doubly transitive on $\{1, 2,…, n\}$ for all $n \geqslant 2$.

Prove that $S_n$ is doubly transitive on $\{1, 2,\ldots, n\}$ for all $n \geqslant 2$. I understand that transitive implies only one orbit, but...
-1
votes
4answers
955 views

How many 4 digit numbers can be made with exactly 2 different digits

I need to find how many four digit numbers can be made using exactly 2 different digits. ALL DIGITS FROM 1 TO 9 CAN BE USED. NOT JUST 1 AND 0
0
votes
1answer
1k views

how many 2x2 matrices are invertible in mod p

I am trying to solve this problem for homework but unable to get anything. The question is to find the number of invertible 2x2 matrices in mod p? Each entery can bee from the set ...
0
votes
1answer
43 views

About definition of a sequences

The notion of sequence is basic notion in combinatorics and can be defined 1.Mapping from a finite set for example $$I_m=\{0,1,2,...,m-1\}$$ to an other set $X$ is finite sequence with terms in $X$ ...
6
votes
4answers
2k views

Exponential Generating Functions For Derangements

I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this ...