2
votes
1answer
73 views

An estimate involving gaps in a subsemigroup of $(\mathbb N,+)$

I think this question can be solved by a high school student, maybe there is some trick on it or I'm forgetting something. Before my question, some background is required: Definition: A ...
4
votes
1answer
54 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
123 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
36 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
50 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 ...
1
vote
1answer
38 views

Maps preserving roots of a polynomial function over finite fields

Let $P(x_{1},\ldots,x_{n}):\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}$ be a polynomial function with degree $d$ and with variables $x_{1},\ldots,x_{n} \in \mathbb{F}_{2}$. Let $S(P)=\{ ...
2
votes
1answer
57 views

How many elements of order 4 does $S_6$ have?

I am trying to count the number of elements of order 4 in $S_6,$ but my answer is not matching the one in the back of the book. Here's my attempt: Such elements are either of the form $(6543)(21)$ ...
2
votes
0answers
44 views

solving recurrence relations for functions with more than one variable

Is there a way to find formula for a function on more than one variable which is given by recurrence relation with some initial conditions? e.g.if one knows the value of f(n,p,l) for all p,l where ...
1
vote
1answer
28 views

What sets of transpositions generate full $S_n$? Connected graphs?

I'm looking for an easy characterization of transpositions $\pi_1, \ldots, \pi_d \in S_d$ that generate $S_d$ or a transitive subgroup thereof (this should be equivalent). Examples include $(1 2), ...
1
vote
1answer
24 views

$PGL_d(F)$ is 2-transitive but not 3-transitive if $d > 2$

An exercise asks to prove that: If $d > 2$, then the projective general linear group $PGL_d(F)$ of dimension $d$ over a field $F$ is 2-transitive but not 3-transitive on the set of points of the ...
5
votes
1answer
66 views

Using Plancherel's Theorem to Prove the Gauss Sum

I'm interested in proving the following: Where $p$ is an odd prime and $z$ is a primitive $p$th root of unity, we let $Q(p)=\sum^{p−1}_{k=0}z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$. Specifically, I want ...
1
vote
1answer
70 views

Math competitions resource at university level

I want some problems especially in Algebra field for math competitions at undergraduate math students level. Does anybody here know book, website,... that I can use?!
0
votes
1answer
44 views

Does the Cayley digraph $C$= [(12)(34),(123):$A_4$] have a Hamiltonian Circuit?

This is a problem I'm working on for a friend of mine. I haven't been able to solve it, or make much progress. I have drawn the digraph, and it consists of four directed cycles of three vertices all ...
2
votes
1answer
62 views

Find the number of irreducible polynomials in any given degree

For any prime $p$ find the number of monic irreducible polynomials of degree $2$ over $\mathbb Z_p$. Do the same problem for degree $3$. Generalize the above statement to higher degree ...
1
vote
1answer
79 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 ...
3
votes
1answer
71 views

Recurrence for the number of $\sigma \in S_n$ with cycle length at most $r$

I have just learned that the formula is right, but the definition of $c_n^{(r)}$ was wrong. The correct problem is: Prove $$c_{n+1}^{(r)} = \sum_{k=n-r+1}^n n^{\underline{n-k}} c_k^{(r)}$$ where ...
4
votes
1answer
89 views

How many monoids of order three are there?

http://oeis.org/A058129 In the above link we can see the answer is 7. I have tried counting these and don't get 7. I am not sure what I am doing wrong so could someone go through counting these step ...
0
votes
0answers
58 views

Two generating functions are combined, how are the coefficients for the combined generating function determined?

I have a function or operation $f(x)$ that takes integer inputs $0\leq x_\mathrm{in}<2^N$ to a limited set of integer outputs $x_\mathrm{out}\in[-N,N]$. I know that if all inputs are computed then ...
2
votes
3answers
152 views

Fibonacci polynomials and factorization redux

I recently asked a question about factorizing a certain expression involving Fibonacci and Lucas polynomials. That question had a very simple and nice answer, but now I've come across another similar ...
1
vote
1answer
56 views

A factorization problem involving Fibonacci and Lucas Polynomials

Consider a sequence of polynomial $\{w_n(x)|\, n\geq 0\}$ which are defined recursively by $w_n(x)=xw_{n-1}(x)+w_{n-2}(x)$. With $w_0(x)=0$ and $w_1(x)=1$, one gets the so-called Fibonacci polynomials ...
2
votes
1answer
57 views

Proving that if $n\times n$ Hadamard matrix exists, then 4 divides $n$

Im looking for an explanation of the following: a standard way to prove that, if there exists Hadamard matrix of dimension $n > 2$, then $4|n$, is to suppose that without loss of generality every ...
3
votes
0answers
25 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
2
votes
2answers
79 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ (1) \quad x_1 y_2 \equiv x_2 y_1 \pmod{N}\\ (2) \quad x_1 y_3 ...
8
votes
1answer
132 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 ...
0
votes
0answers
32 views

Intuition of Newton's identities, is it worth persuing these thoughts? Should be able to show it from special case.

I've "accidentally" stumbled on a special case of it (i=n) and it is very intuitive. Then there's some sort of "transpose" going on with the terms. So I'm thinking there might be something there. I ...
0
votes
2answers
38 views

Understanding “avoiding sequence”

Each subsequence (91674, 91675, 91672) is called a copy, instance, or occurrence of σ. Since the permutation π = 391867452 contains no increasing subsequence of length four, π avoids 1234. ...
0
votes
0answers
24 views

I suspect that a polynomial that is symmetric is a polynomial in “the sums of powers” - using a loose def of polynomial.

This is something I suspect, by this I mean I can't see it being wrong and I have evidence to suggest it is true. It may be a named theorem but given I've been exploring this with a notebook at a ...
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
39 views

Counting problem about sub-matrices

EDIT (along the lines suggested by @sea turtles): Given a prime power $q$ and a positive integer $x\gt q$, how many subsets $A\subseteq{\bf F}_2^q$ have size $x$ and contain a subset $B\subseteq A$ ...
0
votes
1answer
77 views

An algebraic proof that a set has $2^n$ subsets. (I'm looking for an inductive argument.)

There will be duplicates of this, so let me explain why I am asking: I have become blind to what it may be, so I want hints. I am blind because I can do it "combinatorially". The question wishes me ...
3
votes
2answers
125 views

How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

For instance is $\binom{n}{n+1}=0$ always or something else?
0
votes
1answer
41 views

Finding the coefficient of a specific term in a polynomial without expanding/simplifying?

I'm learning about Polya's Theorem which deals a lot with the coefficients of terms in a polynomial. In one problem I had the following polynomial, $(b+w)^{16}$, and the problem basically reduces to ...
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 ?
0
votes
0answers
14 views

Is there a general formula for counting number of canonical forms given the minimal polynomial?

Suppose you have an operator $T$ on a vector space $F^n$, and you're given the minimal polynomial $m_T(x)=p_1(x)^{a_1}\cdots p_k(x)^{a_k}$, where $\sum a_i=\deg(m_T(x))=d\leq n$. Is there a general ...
0
votes
0answers
110 views

Two very difficult induction proofs; having trouble with the inductive step

$$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+1}\frac{n-2k-1}{k+1} = n-2 + \frac{1}{n+1}\binom{2n}{n}$$ $$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+2}\frac{n-2k-1}{k+1} = -n + ...
10
votes
1answer
159 views

Direct combinatorial proof of a sum identity on formal Lagrange polynomials

Let $k$ be a field and $K=k(x_0,x_1,\ldots, x_n)[x]$. Define $$\mathcal{L}_k(x)\triangleq \prod_{\substack{j=0\\ j\ne k}}^n\frac{x-x_j}{x_k-x_j}.$$ Is there a purely combinatorial way to show ...
1
vote
1answer
45 views

Permutation (without repeating)- (basic)

I have problems solving and understanding the following task from the combinatorics: We have two sets: $\mathcal A=${$x; (x\in Z)$ $\land$ $(-6 \le x \lt 0)$} and $\mathcal B=${$n; (n\in N) \land ...
2
votes
2answers
47 views

The curriculum's permutation

Consider the word CURRICULUM.How can i find number of ways in which 5 letter words can be formed using the letyers from the word CURRICULUM if each 5 letter word has exactly 3 different letters?My ...
0
votes
1answer
29 views

how fast does the proportion of associative operations on $S$ decrease with |$S$|?

as doubtless many have done before me, i recently fell into wondering how many of the binary operations on a finite set are associative. the stackexchange software fortunately pointed me to this ...
2
votes
2answers
76 views

Number of functions with some property

A function $f$ is defined on the set $\{0,1,2,3,…,n-1\}$ to itself. This is a function such that if you take any $k$ from the set $\{0,1,2,3,…,n-1\}$ then $f^m (k)=0$ for some natural number $m$. ...
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?
4
votes
2answers
130 views

How many elements of order $k$ are in $S_n$?

I need to find how many elements of order $k$ are in $S_n$ (where $k \leq n$). So if $k$ is prime, it's easy: $k$ can't be the $\mathrm{lcm}$ of any integers besides itself and one's (which we're ...
3
votes
0answers
52 views

Deducing that polynomials span

Let us say that we are dealing with a countable family of polynomials with real coefficients in $n$ indeterminates that commute. Are there any known/common nice systematic ways to tell if their span ...
3
votes
1answer
220 views

How many of all cube's edges 3-colorings have exactly 4 edges for each color?

I've found the number of different cube's edges colorings with three colors available. (We say that the two colorings are the same if one can obtain a second by turning cube and permuting colors) My ...
1
vote
0answers
52 views

Computing binomial coefficients mod 2

Computing binomial coefficients $n\choose k$ mod $2$ is relatively easy. It is $1$ if and only if the $1$'s in the binary expansion of $k$ are a subset of the $1$'s in the binary expansion of $n$. I ...
0
votes
1answer
59 views

Convergence of formal power series substitution

Prove that the substitution of formal power series $F(G(x))=\sum_{k\geq0}f_k \frac{G(x)^k}{n!}$ converges for every $F$ if and only if $G(0)=0$
3
votes
2answers
355 views

Formal power series, the Chain Rule and the Product Rule.

Definitons Let $$\mathbb{C}[[x]] := \left\{ \sum_{n\geq 0} a_n x^n : a_n \in \mathbb{C} \right\}$$ be the set of formal power series of $x$. Exercise i) If $F_1(x)$ and $F_2(x)$ are power series ...
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}$?
3
votes
1answer
195 views

Decomposition formulas for rotational symmetries of a cube

I have a problem that I would like to check my work on. I am also stuck on the verifications for $E$ and $F$. Any help would be greatly appreciated. Thanks in advance. Problem statement: Let $G$ be ...
1
vote
5answers
133 views

When is round-robin scheduling possible and with in minimal time?

Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five ...