All Questions
29
questions
4
votes
0
answers
109
views
How many connected nonisomorphic graphs of N vertices given certain edge constraints?
Background:
I’m helping a colleague with a theoretical problem in ecology, and I haven’t quite the background to solve this myself. However, I can state the problem clearly, I think:
Problem statement:...
0
votes
1
answer
81
views
Question about element in $\{1,\cdots,n\}$ and its product with its permutation: $\sum_{j=1}^nj\sigma(j)$ for $\sigma \in S_n$ [closed]
Let $\sigma\in S_n$ for some $n\in \mathbb{N}$. I am interested in $\displaystyle \sum_{j=1}^nj\sigma(j)$. Can anyone help point me in a decent direction? If $\sigma = (1)$ in cycle notation, we ...
-2
votes
1
answer
91
views
Existence of a "square-sum"-free word
Let $A$ be a finite subset of an additive group $G$, with no pair of its elements being inverses. I would like to prove/disprove the existence of an infinite word over $A$ (treated now as an alphabet) ...
1
vote
0
answers
28
views
how to cover the unit interval by using shift operators
Consider the following partition of $[0,1)$:
$$P:=\left\{
[0,\frac{1}{2^n}), [\frac{1}{2^n},\frac{2}{2^n}),[\frac{2}{2^n},\frac{3}{2^n}), [\frac3{2^n},\frac{4}{2^n}), \cdots, [\frac{2^n-1}{2^n},1)\...
3
votes
1
answer
283
views
Symmetry in the set of integers that cannot be written as $ap+bq$ where $a,b$ are non-negative integers for relatively prime $p,q$
I was studying symmetries (as an introduction to Group Theory) and found this question-
Let $p,q$ be relatively prime positive integers and let $X$ be the set of integers that cannot be written as $...
6
votes
1
answer
178
views
Choosing elements from an abelian group $\mathbb{Z}_n$ that make the enumeration of partitions incomplete.
Take an abelian group $(\mathbb{Z}_n,+)$ and enumerate all partitions of two elements (i.e. $x=x_1+x_2$) of each element $\{0,1,...,n-1\}=\mathbb{Z}_n$. Take, for example, abelian groups $\mathbb{Z}_9$...
4
votes
2
answers
1k
views
How many rings are there for a given order?
Often I have encountered questions like :
How many rings of order 4 are there upto isomorphism?
Often the solution involved brute-force treatments as checking the multiplication tables.
But it is ...
0
votes
1
answer
47
views
Find $a,b,c,d$ such that $p \not\mid ad - bd$ and each element is in $\mathbb{Z}/p\mathbb{Z}$
Find the number of quadruples $(a,b,c,d)$ such that $ad - bc \not\equiv 0 \pmod p$ where $a,b,c,d \in \{\mathbb{\overline{0},\overline{1},\cdots, \overline{p-1}} \}$.
From this, we have $\...
1
vote
0
answers
15
views
Finding the relationship between generating elements represented by a Hamiltonian cycle of a Cayley graph
Consider an undirected Cayley graph of a finite group $\mathbb{Z}_p \times \mathbb{Z}_q$, where $p$ and $q$ are distinct primes. Let the generating set for the Cayley graph be $S=\{g_p, g_q\}$, where $...
0
votes
1
answer
71
views
Number of solutions for this diophantine equation using character theory?
Let $G$ an abelian group with $\vert G\vert<+\infty$ and $N_1, ..., N_k$ , $k$ subsets of $G$. Let $a \in G$.
We want to find $\vert \{(n_1,...,n_k)\in N_1\times...\times N_k \ / \ n_1+...+n_k=a \}\...
3
votes
0
answers
86
views
A question on a possible cyclic sieving phenomenon
Let $G$ be a finite group. Consider the set $X_G:=\cup_{H\le G} G/H$, where the disjoint union is taken over all left cosets of the subgroups $H \le G$. Let $S \subset G$ be a generating set for $G$ ...
0
votes
0
answers
145
views
Given a finite group, does this equation involving group's order, a partition of it and centralizers' orders hold?_Attempt#2
After failing this attempt, I've revised my proof sketch and I've come to the following version of the equation in the title.
So, let $G$ be a finite group, say $G=\lbrace e,a_1,\dots,a_{n-1} \rbrace$...
1
vote
2
answers
78
views
Сonditions for the equality of Greatest Common Divisor of two specified sequences of numbers
I consider two sequences of numbers $A=\{a_1,...,a_n\}$ and $B=\{k-a_1,...,k-a_n\}$, where $a_1 \le a_2 \le ... \le a_n \le k$.
I am looking for such conditions under which: $gcd(a_1,...,a_n)=gcd(k-...
0
votes
0
answers
34
views
Asymptotics of the number distinct of subgroups of $S_n$ as $n$ goes to infinity [duplicate]
I would like to have a sense of the number of distinct subgroups (that is, isomorphic subgroups are counted multiple times) the symmetric group $S_n$ has as $n$ goes to infinity. I suspect nailing ...
1
vote
0
answers
45
views
Asymptotic formula for the integral sequence s(n)
Prove that there exists a sequence $A_{0}, A_{1}$, . . . of rational polynomials $A_{i}(x)\in \mathrm{Q}[x]$ with $A_{i}$ of degree $i$ such that
$$
s(n)=\frac{n^{n-1}}{(1-\log 2)^{n-1/2}e^{n}}(\sum_{...
5
votes
2
answers
4k
views
Maximum possible order of an element in $S_7 \text{ and } S_{10}$
Exercise :
Find the maximum possible order of an element of the group of permutations $S_7$. Do the same thing for $S_{10}$.
Discussion :
Recalling that any permutation can be written as a ...
0
votes
1
answer
430
views
Find the count of unique subset sums in a powerset
Given a list of integers, I want to find the count of unique sums for all possible subsets of length $N$.
I don't want to know the sum, or the subsets, just the count of possible unique sums for ...
2
votes
0
answers
276
views
When the 24 Game is solvable given the four cards?
Consider the 24 Game with a deck of cards that forms a set $ \Omega = \{1, 2, ..., 13\}$, and we try to compute 24 using addition, subtraction, division and multiplication in Rational numbers $\mathbb{...
0
votes
1
answer
81
views
Condition that for a given set of numbers and given divisor all finite sums from this set contain all possible remainders
Given $q \in \mathbb{N}$ and ${a_1, a_2, ...}$ where each $a_j \in \mathbb{N} \cup{\{0\}}$ define $A_p=$ {set of all finite sums of $\{a_1 ... a_p\}$ such that each $a_j$ will appear either $1$ or $0$ ...
0
votes
3
answers
63
views
Proof about elementary group theory
Let $X = \{1, 2, 3, 4, 5\}$ and $σ : X → X$ be a bijective function. 1) Prove
that $σ^n$ is invertible for all $n ∈ N$. 2) Prove that there is an natural number
$n$ such that $σ^n = I_x$. Hint: Use ...
9
votes
1
answer
2k
views
What is the largest abelian subgroup in $S_n$?
I am almost to complete my first course in group theory. I have read Dummit and Foote into chapter 5.
I know that I can always find an abelian subgroup isomorphic to $C_{k_1} \times C_{k_2} \times .....
18
votes
1
answer
6k
views
What is the number of Sylow p subgroups in $S_p$?
I am reading the Wikipedia article entitiled Sylow theorems. This short segment of the article reads:
Part of Wilson's theorem states that
$(p-1)!$ is congruent to $-1$ (mod $p$) for every prime $p$....
3
votes
2
answers
953
views
Permutations minus Transpositions
I want a formula that allows me to find all the permutations in $S_n$ (which is the set of all the integers from 1 to $n$) which don't contain a transposition.
Attempt:
Lets call $g(n)$ the ...
0
votes
0
answers
134
views
Zero-Sum Partitions of Nonzero Elements of a Ring
In this question, rings are not necessarily finite nor do they need to be unital (i.e., the multiplicative identity may not exist). Although I shall almost exclusively discuss finite commutative ...
3
votes
0
answers
82
views
'Randomness' of inverses of $(\mathbb{Z}/p \mathbb{Z})^\times$
Suppose you are given the group $(\mathbb{Z} / p \mathbb{Z})^{\times}$, where $p$ is prime. Let $A_p$ denote the sequence whose $j$th element is the inverse of $[j]$. For instance, if $p = 7$, the ...
2
votes
0
answers
99
views
Generalization of Cauchy-Davenport inequality to $\mathbb Z_p^d$
Is there some generalization of Cauchy-Davenport inequality to the group $\mathbb Z_p^d$? ($p$ prime number, $d \ge 3$)
For example, Kneser Theorem says that if $G$ is any abelian group and $\...
2
votes
1
answer
211
views
Select k no.s from 1 to N with replacement to have a set with at least one co-prime pair
Given $1$ to $N$ numbers. You have to make array of $k$ no.s using those no.s, where repetition of same no. is also allowed, such that at least one pair in that chosen array is co-prime. Find no. of ...
5
votes
2
answers
166
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. ...
5
votes
4
answers
618
views
${{p-1}\choose{j}}\equiv(-1)^j \pmod p$ for prime $p$
Can anyone share a link to proof of this?
$${{p-1}\choose{j}}\equiv(-1)^j(\text{mod}\ p)$$ for prime $p$.