4
votes
1answer
51 views

Order of group $GL_{2}\left( \mathbb{F}_{p}\right) $

I'm having a hard time counting. I need to count the number of elements for the multiplicative group of invertible $2\times 2$ matrices $GL_{2}\left( \mathbb{F}_{p}\right) $ with elements from the ...
9
votes
3answers
118 views

Number of elements of order $2$ in $S_n$

How many elements of order $2$ are there in $S_n$? Using combinatorics I arrived at this: For $n$ even ($n=2k$) there are ${n\choose2}+{n\choose 2}{n-2\choose 2}\dfrac{1}{2!}+{n\choose 2} ...
4
votes
1answer
35 views

Is the number of associative $n$-ary algebraic operations on a finite set with 2 cardinality always 8?

We know that if $n = 2$ then the operation is called a binary operation. $ \circ $ on set $X$ is a function $\circ : X \times X \rightarrow X$. And the number of all associative binary operation on a ...
2
votes
1answer
48 views

Minimum number of out-shuffles required to get back to the start in a pack of $2n$ cards?

So I'm stuck on this problem. If you perform a faro out-shuffle (i.e. a perfect "riffle shuffle" where the top and bottom cards stays in place) on a pack of 52 cards ($n=26$), you can get back the ...
3
votes
0answers
44 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
36 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
57 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
21 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
38 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
27 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
55 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
72 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
99 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
51 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
78 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
39 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
193 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
61 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
44 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
33 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
129 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
81 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
61 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
38 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
69 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
68 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
181 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
315 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
142 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
30 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
119 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
289 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
26 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
112 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
73 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
97 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
30 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
66 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
104 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
78 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)$, ...