3
votes
0answers
36 views

an elementary problem on wreath product groups with combinatorial flavor

Embarrassingly, I got stuck in solving the following elementary exercise. Let $G=H\wr \Gamma$ be a wreath product groups, $H,\Gamma$ are countable discrete groups, when $\xi\in\oplus_{\Gamma}H$, then ...
1
vote
0answers
30 views

Variations of M,n,k-games

I just read about M,n,k-games and wondered if the following variation (with fixed $k$) has been studied as well and if there exists a name for it: Two players consecutively mark elements of ${\bf Z}$ ...
7
votes
1answer
54 views

Is it possible to partition $\mathbb{N}_+$ into a *finite* family of sets completely not closed under $+$?

Let's say that $A \subseteq \mathbb{N}_+$ is completely not closed under $+$ if $$ \forall_{a,b \in A}[{a+b \notin A}] $$ Is it possible to partition $\mathbb{N}_+$ into a finite family of sets ...
0
votes
1answer
20 views

Conjugating a permutation

I am trying to see that two permutations are conjugate exactly when they have the same cycle decomposition. I fail to see that $$r(i_1,i_2,\dots,i_k)r^{−1}=(r(i_1),r(i_2),\dots,r(i_k))$$ Any thoughts ...
1
vote
0answers
34 views

Calculation related to the number of conjugacy classes of the symmetric group

The symmetric group on $n$ elements, $S_n$, can act on itself by conjugation. The orbits of this action are the conjugacy classes corresponding to integer partitions of $n$. If $S_n$ acts on some ...
2
votes
1answer
35 views

Relations counting in two sets

I have two sets $A=\{1,2,3, 4\}, \ B=\{5,6,7,8,9\}$. I wanted to count the relations from $A$ to $B$ that didn't include $1$ in their domain. First i did it like this: $2^{20} - 2^5 + 1 = ...
0
votes
1answer
26 views

Count relations in a specific domain

I have two groups $A=\{6,7,8,9\}, \ B=\{1,2,3,4,5\}$. I want to count how many relations there are from $A$ to $B$ which obey to the rule: $\{6,7,8\}\subseteq \text{domain}(k)$ * k is the ...
2
votes
0answers
48 views

Puzzle with character order

Suppose I have 3 letters a, b, c and I want to find the minimum length of a string that uses all the double combinations of the aforementioned letters. How should I do it or how are such problems ...
0
votes
2answers
70 views

Asymmetry of random graphs

By a well known result of Pólya we know that the number $g_n$ of isomorphism classes of simple graphs on $n$ vertices is asymptotically equivalent to $\frac{2^{\binom{n}{2}}}{n!}$. In this paper the ...
1
vote
2answers
97 views

Number of essentially different ways of colouring the edges of a regular tetrahedron with n colours ensuring there are monochromatic triangles?

I've shown that the number of colourings of the edges of a regular tetrahedron with n different colours when we want to ensure that there is at least one monochromatic triangle is $4n^4 - 6n^2 + 3n$. ...
1
vote
1answer
43 views

Counting sum of lattice points

Assume a set $S$ with $|S|$ entries. Indeed, $S$ is the set of lattice points inside a $k$-sphere. Assume $V=S\oplus S$ where $\oplus$ is the Minkowski sum of two sets. Do you know any lower bound on ...
3
votes
3answers
49 views

Conjugate to the Permutation

How many elements in $S_{12}$ are conjugate to the permutation $$\sigma=(6,2,4,8)(3,5,1)(10,11,7)(9,12)?$$ How many elements commute with $\sigma$ in $S_{12}$? I believe I use the equation ...
1
vote
1answer
77 views

Application of group theory to combinatorics

Let k be a positive integer. In how many ways one can color the edges of an equilateral triangle using k colors (two coloring schemes are considered the same if one can be obtained from the other via ...
0
votes
1answer
38 views

Find order of the given permutation

Let $\sigma$ be the permutation: $$1 \quad2 \quad3 \quad4 \quad5 \quad6\quad 7\quad 8\quad 9$$ $$3\quad 5 \quad6\quad 2\quad 4\quad 9\quad 8\quad 7\quad 1$$and $I$ be the identity permutation. Also, ...
4
votes
0answers
190 views

Special Products of Transpositions

[Edit. Significantly expanded to add examples and (I hope) clarification. Feel free to skim by reading the gray boxes.] A colleague asked me for insights on a collection of special permutations, ...
2
votes
1answer
58 views

Is my application of Burnside's Lemma correct in this combinatorial problem?

For a course in Combinatorics (I know very little group theory unfortunately), we've been tasked to use Burnside's Lemma on the following problem: Suppose you write a 5-digit number on a piece of ...
0
votes
0answers
41 views

Burnside's Lemma and Stirling Numbers of the First Kind

I've seen that $n!=\displaystyle\sum_{p=0}^n s(n, p)n^p$, where $s(n, p)$ are the signed Stirling Numbers of the First Kind, whose absolute values count the number of permutations in $S_n$ which have ...
0
votes
2answers
59 views

permutation problem: cycle representation

Let $n$ be an odd number. Let $C_n$ be the set of permutations $\pi$ of $[n]$ whose cycle representation has only one cycle. Let $\pi,\sigma\in C_n$. Prove that their composition $\pi\sigma$ has an ...
2
votes
0answers
30 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
1
vote
0answers
32 views

Coxeter length of a cycle in $S_n$

Is there a formula for the Coxeter length of a cycle in $S_n$? For example, if the cycle is $(ij)$ then the length is $2(j-i)-1$.
8
votes
1answer
119 views

2D Rubik's cube?

There is a $3\times3$ matrix filled by numbers 1~9 that might look like this $$\begin{bmatrix}3 & 8 & 2 \\ 4 & 1 & 6 \\ 7 & 5 & 9\end{bmatrix}$$ All its rows and columns can ...
3
votes
0answers
72 views

Given a number of items, how many sets of three are there where no two sets are two thirds similar?

Sorry if the title isn't proper math-talk. Hopefully I can explain it better here. So let's say we have a set. 1, 2, 3, 4, 5, 6, 7, 8, 9. I want to know how many groups of three can be made where no ...
2
votes
1answer
59 views

How did the Symmetric group and Alternating group come to be named as such?

The Dihedral group makes sense, "Di" means two, and "hedral" means.. shape I think (I've just realised how much of what I think words mean are guesses based on experience) like a "polygon" is a 2d ...
0
votes
1answer
37 views

A bijective transform that cycles. Help with definitions requested

In many ways I am a novice with mathematics. My background is college algebra. I am attempting to write my first maths paper and am faced with sifting through mathematics I am not familiar with. It ...
0
votes
0answers
67 views

Describing the sequence A224239.

I've been trying to describe mathematically the $n$th term $a_n$ of the sequence A224239. We get $a_n$ by counting the distinct ways to fill an $n\times n$ grid with squares of smaller integer size, ...
1
vote
0answers
66 views

Square root of permutation

I have been thinking about square roots of permutations. I realized that the square of cycle of odd length is a cycle with the same length and the square of cycle with even length is multiplication of ...
7
votes
3answers
180 views

What is the probability of product of two elements is desired element?

Let $G$ be a group with $n$ element. Fix $x\in G$. If you choose randomly two elements from $G$, what is the probability of $x$ being product of these two elements? At first, I thought answer was ...
10
votes
2answers
276 views

Is it possible to shuffle a 3x3 Rubik's cube so that there's no more than 2 pieces of the same color in every face?

I'm not sure if this question belongs here but I see lots of Rubik Cube's questions around so here it goes: Can I take a standard 3x3 Rubik's Cube and shuffle it so that, for every face, there are no ...
1
vote
1answer
136 views

If $|A| > \frac{|G|}{2} $ then $AA = G $

I'v found this proposition. If $G$ is a finite group , $ A \subset G $ a subset and $|A| > \frac{|G|}{2} $ then $AA = G $. Why this is true ?
1
vote
0answers
29 views

Polya enumeration theorem, general form

In classic Polya enumeration theorem we have group $G$ acting on $X$ in $Y^X.$ Is there some similar statement, where we have also group $H$ acting on $Y?$ My opinion is that's true, but I can't ...
5
votes
2answers
117 views

What can we say about the kernel of $\phi: F_n \rightarrow S_k$

Let $F_n$ denote the free group on $n$ generators and let $S_k$ denote the symmetric group on the integers $\{1,\dots, k\}$, and the action of homomorphism $\phi$ (as given in the title) on the ...
4
votes
0answers
281 views

Counting simple quadrilaterals in a rectangular lattice.

I've been trying to make an algorithm to find the number of all possible simple quadrilaterals in a N*M lattice. I already have a brute force solution but since this is a Project Euler problem I ...
2
votes
0answers
23 views

How to calculate when a specific semigroup is closed under conjugation by this group.

Let $\mathcal{T}_n$ be the set of $n \times n$ matrices such that $X\in \mathcal{T}_n$ can be written as: $$X = \bigl( \begin{array}{cc} 1 & \overline{0} \\ T & \underline{0} \end{array} ...
4
votes
2answers
109 views

How to prove $\frac{1}{q} \binom{p^k q}{p^k} \equiv 1 \mod p\;\;$?

An argument that I just came across asserts that if $p$ is prime, and $k, q\in \mathbb{Z}_{>0}$, then $$\frac{1}{q} \binom{p^k q}{p^k} \equiv 1 \mod p \;.$$ This assertion was made in a way (i.e. ...
0
votes
1answer
68 views

Painting a cube using N different colors?

In how many different ways can a cube be painted by using N different colors of paint? Note that this question is not same to Painting the faces of a cube with distinct colours as the colours ...
10
votes
1answer
100 views

Some questions concerning the symmetric group $S_n$

Let $a_n$ be the number of permutations in $S_n$ having an square root. Is it true that $a_{2n+1} = (2n+1)a_{2n}$ ? (experimental data's shows that this is true for small values of $n$). Is there ...
1
vote
2answers
100 views

Find all the elements in $S_4$ that commutes with $(12)(34)$.

Find all the elements in $S_4$ that commutes with $(12)(34)$. And show the algorithm of the process.
5
votes
3answers
97 views

How many Homomorphisms can be between $Z_6$ to $Z_{18}$?

How many Homomorphisms can be between $Z_6$ to $Z_{18}$? and the most important: What is the algorithm for calculating, step by step?
1
vote
1answer
96 views

Number of 2n-1 equal size partitions up to symmetry

Consider the $K_{2n}$ (or just the set $\{1,\dots,2n\}$) with $S_{2n}$ acting on the vertices. Moreover consider a collection of 2n-1 partitions of the vertices into two equal sized sets (repeated ...
0
votes
0answers
29 views

What is a quotient of a building by a lattice?

For an algebraic group $G$, we may defined a building associated to $G$. Let $B = B(G)$ be the corresponding building. I don't understand much about the concept quotient $B/\Gamma$ of a building $B$ ...
1
vote
0answers
45 views

Proof of dimension formula for sl(3,C) reps

this is my first question on the forums, so forgive me if I did something wrong. I have tried to find an answer in here as well as on the usual places on the internet and was unsuccessful. So here ...
3
votes
1answer
63 views

Trying to understanding the proof of the fact that Kazhdan property (T) implies expanders.

I am trying to trying to understanding the proof of the fact that Kazhdan property (T) implies expanders. This is a result of Grigory Margulis. It is stated in Proposition 3.3.1 on Page 30 of the book ...
1
vote
1answer
65 views

Counting number of group homomorphism

Let $G$ be a group. Show that $$\# \text{hom}(\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}, G)=\# \{f:\mathbb{Z}\times\mathbb{Z}\to G\mid f\; \text{is a homomorphism},2\mathbb{Z}\times ...
2
votes
1answer
101 views

Burnside's lemma: 30 possible different dice

I have been working with Burnside's counting lemma and I came across the problem to show that there are 30 possible different dice. I have tried working with the 24 rotational symmetries of the cube ...
1
vote
1answer
72 views

Number of non-equivalent necklaces

A necklace is made up of 12 beads in a circular loop. 3 are green and 9 are yellow. How many non-equivalent necklaces can be made? I have to use Burnside's Counting Lemma in this question.
0
votes
2answers
72 views

Compute number of permutations composed only of transpositions for a given set

Given a set of $n$ elements, how can I find the number of all possible permutations composed only by a product of cycles? For example, for the set $\{1,2,3\}$ there are 4 such permutations: $(123)$, ...
4
votes
1answer
37 views

Graph with sharply 1-transitive automorphism group

What finite Graphs $G$ have the property that for all $v,w\in G$, there is exactly one automorphism $\phi$ of $G$ with $\phi(v)=w$? Of course, each of the three graphs with one or two vertices have ...
9
votes
0answers
113 views

How many arrays with crossed cells, order of rows/columns irrelevant

I've been struggling with this simple problem for months though as I am a newbie to… well, maths, there's high chance someone more educated than myself may get it right! Let's consider an array or a ...
5
votes
0answers
128 views

How many elements of order $2$ are there in the symmetric group $S_{n}$? [closed]

How many elements of order $2$ are there in the symmetric group $S_{n}$?
1
vote
1answer
45 views

The automprphism group of the complete binary rooted tree height 3

Can someone give me some help with this problem: How do I find the automorphism gruop of the complete binary rooted tree height 3 (15 vertices)? when an automorphism F on a graph G=(V,E) is defined ...