questions regarding the re-orderings of some finite set of objects.
1
vote
1answer
89 views
Minimum number of moves to create a new permutation
Edit: Before you begin, please note that a move refers to swapping a pair of letters (thanks to ferfer93)
Ok, so I understand the title is a bit ambiguous, so I'll clarify it further below:
Let us ...
1
vote
2answers
48 views
combinations, how many ways are there?
how many ways are there to put 36 non-distinguishable balls in 15 distinguishable buckets? This is what I thought: suppose the balls are distinguishable. every time you want to put a ball in a bucket, ...
3
votes
2answers
219 views
Is every permutation group isomorphic to a 'familiar' group?
This may be a very simple question, but I do not know how to approach it.
Cayley's theorem states that every group G is isomorphic to a subgroup of the symmetric group acting on G (in other words, ...
5
votes
1answer
68 views
Is it possible to reverse this sequence of permutations?
Let
$ S = (a_1, a_2, ..., a_N) $ be a finite (arbitrarily long) sequence of elements, and let $p_1, p_2, ..., p_n $ be the first $n$ prime numbers, with $n \ge 3$.
We apply a sequence of ...
7
votes
1answer
147 views
Is n! mod p doable in sub O(n) time?
I ask because I can use Lucas Theorem to find n choose k mod p but don't know of an equivalent for permutations (n permute k mod p).
0
votes
1answer
45 views
Dividing all permutations
Suppose you're trying to solve the Traveling Sales Person problem by going over all possible paths. To do so, you have a number of computers. Each gets $(n-1)!/p$ paths to scan, where $p$ is the ...
2
votes
1answer
75 views
Wreath Products of Symmetric Groups
I am currently in the process of reading an article by D.Bundy The connectivity of commuting graphs. In section 3 (in the Preliminary Results) Bundy gives the following result:
$\mathbf{(3.1)}$ Let ...
1
vote
1answer
131 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
147 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 ...
22
votes
1answer
433 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
78 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
149 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
63 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
54 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 ...
8
votes
2answers
253 views
how to find the root of permutation
$$\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 & 4 ...
2
votes
1answer
128 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
93 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
50 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
89 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 ...
5
votes
3answers
108 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 ...
6
votes
1answer
299 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
58 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
61 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 ...
0
votes
1answer
63 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
59 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?
3
votes
1answer
113 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
38 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 ...
1
vote
2answers
293 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
175 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
137 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
59 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
91 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
106 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
172 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 ...
0
votes
1answer
63 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
270 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
78 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
116 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
156 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
89 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
86 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!$ ?
4
votes
1answer
87 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
36 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
101 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
1answer
175 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
85 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
58 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 ...
7
votes
2answers
140 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
97 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
111 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$ ...
