1
vote
1answer
35 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
43 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
21 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
58 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
67 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
43 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
57 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
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 ...
3
votes
1answer
67 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 ...
3
votes
1answer
82 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
53 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
150 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
50 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
53 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
24 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
78 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
121 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
31 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
36 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
23 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
38 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
75 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
39 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
139 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
44 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
46 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
75 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
107 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
215 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
51 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
58 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
340 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
191 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
131 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 ...
0
votes
1answer
130 views

Monomial ideals: isomorphism problem for commutative algebras?

Let $I,J\unlhd K[x_1,\ldots,x_n]=K[x]$ be monomial ideals and $f\!: K[x]\to K[x]$ a graded isomorphism (given by a matrix $A=[\alpha_{i,j}]\in K^{n\times n}$, i.e. $x_i\mapsto\sum_j\alpha_{i,j}x_j$ is ...
2
votes
1answer
52 views

How can one know how many possible abelian and non abelian group be formed from a given number of elements

Suppose that $G=\{a_1,a_2,...,a_n\}$ and how many abelian and non abelian group can be formed from this $n$ element? Attempts : I have tried consider the simple case. when n=2, there is only 1 ...
2
votes
2answers
52 views

What does ${N\choose\mu}$ mean where $\mu = (\mu_1, … , \mu_n)$ be the vector of nonnegative integers for which $\sum_{i=1}^n \mu_i = N$?

When I've read Cohn et al. paper 2005, I've met a strange object in lemma 1.1 that looks like number of combinations: ${N\choose\mu}$ where $\mu = (\mu_1, ... , \mu_n)$ be the vector of nonnegative ...
1
vote
0answers
44 views

Maximal size of an almost-disjoint linearly independent family in $K^{\mathbb{N}}$

Let $K$ be a field, say infinite, and denote by $L$ the $K$-vector space $K^{\mathbb{N}}$. What is the maximal cardinality of a $K$-linearly independent subset $X$ of $L$ such that any two distinct ...
0
votes
0answers
48 views

An extremal combinatorial problem over Finite rings

Let $q$ be an odd number and $g_i = (g_{i1} g_{i2} \dots g_{ir}) \in \Bbb Z_q^r$ a list of vectors with $i\in\{1,\ldots,L\}$. Let each $g_i$ have $0 < k < r$ zero entries. What is the maximum ...