# Questions tagged [algebraic-combinatorics]

For problems involving algebraic methods in combinatorics (especially group theory and representation theory) as well as combinatorial methods in abstract algebra.

124 questions
451 views

### A conference uses $4$ main languages. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know.

A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know. Source: ...
753 views

### Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
918 views

### Property of a polynomial with no positive real roots

The following is an exercise (Exercise #3 (a), Chapter 3, page 28) from Richard Stanley's Algebraic Combinatorics. Let $P(x)$ be a nonzero polynomial with real coefficients. Show that the ...
2k views

348 views

### Motivation/intuition behind using linear algebra behind these combinatorics problem

What is the motivation behind using linear algebra in these three problems ? A pair $(m,n)$ is called nice if there is a directed graph with (self edge are allowed, but multiple edge are not allowed)...
63 views

### Given a matrix $A$ such that $A^{\ell}$ is a constant matrix, must $A$ be a constant matrix?

This problem originates from an exercise in Richard Stanley's Algebraic Combinatorics. The exercise in the text (Chapter 3, Exercise 2(a)) asks Let $G$ be a finite graph (allowing loops and ...
377 views

### Powers of a simple matrix and Catalan numbers

Consider $m \times m$ anti-bidiagonal matrix $M$ defined as: $$M_{ij} = \begin{cases} -1, & i+j=m\\ \,\,\ 1, & i+j=m+1\\ \,\,\, 0, & \text{otherwise} \end{cases}$$ Let $S_n$ stand ...
221 views

### Proving an identity for complete homogenous symmetric polynomials

Probably everybody knows the expression: $$\sum_{k_1,k_2\ge0}^{k_1+k_2=k}a_1^{k_1}a_2^{k_2}=\frac{a_1^{k+1}-a_2^{k+1}}{a_1-a_2},$$ where $a_1\ne a_2$ is assumed. It seems that it can be further ...
554 views

### A question on Derangement Combinatorics

Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the ...
139 views

309 views

### Uses of Chevalley-Warning

In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows: We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the ...
152 views

### We have $n$ real numbers around the circle and among any consecutive 3 one is AM of the other two. Then all the numbers are the same or $3\mid n$.

There are $n$ real numbers around the circle and among any consecutive 3 one is arithmetic mean of the other two. Prove that all the numbers are the same or $3\mid n$. Hint was to use a linear ...
269 views

### “Binomial coefficients” generalized via polynomial iteration

This is a question I will answer myself immediately by repeating one of my old AoPS posts, since the latter post no longer renders on AoPS. Convention. In the following, whenever $A$ is a ...
201 views

### $\eta$-value of a partition and its meaning

The $\eta$-value of an integer partition $\lambda = \big( \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k \geq 0 \big)$ is defined as \eta \big( \lambda \big) \ := \ \sum_{i=1}^k ...
399 views

### Properties of the 'forgotten' symmetric polynomials

In I.G. Macdonald "Symmetric Functions and Hall Polynomials" pg.22, the forgotten symmetric functions $f$ are introduced very briefly as the result of applying an involution $\omega$ to the monomial ...
148 views

63 views

### Prove the bijections between the following $(p,q,r)$-shuffles

I am reading the book "From Calculus to Cohomology: De Rham cohomology and characteristic classes" Let $p, q, r$ be nonnegative integers. It says, (for those who own the book, on pg 10) without ...
88 views

68 views

39 views

### Calculating determinants

Let $n\geq 2$ be an integer and let $\Sigma$ be the collection of all $2$-subsets (a 2-set is a set that contains $2$ elements) of $[n]=\{1,2,\dots,n\}$, thus $\Sigma$ contains $\binom{n}{2}$ elements....
60 views

### Example of shellable and non-shellable simplicial complexes with the same $f$-vector

I need to construct two pure simplicial complexes with the same $f$-vector such that one is shellable and one isn't. I think we can try two-dimensional simplicial complexes, I can find two simplicial ...
60 views

### What do you get when you pull the Bruhat Decomposition back to the Lie algebra via the exponential map?

If $G$ is a connected, reductive, complex group with Borel subgroup $B < G$ and Weyl group $W$, we can write $$G = \bigsqcup_{w \in W} B w B$$ If $\mathfrak{g}$ is the Lie algebra of $G$, we have ...
76 views

### To show two formal power series equal

I am wondering whether the following two formal power series are equal: $A(x)=\Pi_{k=1}^{\infty}\frac{1}{1-x^{2k-1}}$, $B(x)=\Pi_{k=1}^{\infty}(1+x^k)$.
279 views

### Reference request: Representation theory over fields of characteristic zero

Many representation theory textbooks and online resources work with the field of complex numbers or more generally algebraically closed fields of characteristic zero. I am looking for a good textbook ...
760 views

### A Variation of the even-town odd-town problem

Let assume facebook has $n$ users. Mark Zuckerberg decided that people are allowed to open groups under the following restrictions: 1) No two different groups can exactly the same participants. ...
454 views

### Number of permutations of $[n]$ with a multiple of $n$ inversions

We have a permutation $\left(a_1,a_2,...,a_n\right)$ of the set $\{1,2,...,n\}$. A pair $(a_i,a_j)$ is said to be an inversion of this permutation if $i<j$ and $a_i>a_j$. Find the number of ...
111 views

### Proof that the Lascoux-Schützenberger involutions satisfies the braid-relations

I am interested in the Lascoux-Schützenbereger involutions $\theta_i$, defined on semistandard Young tableaux. See this paper for definitions, page 4. These involutions satisfy the braid relations: (...
I know that every irreducible polynomial over $\mathbb F_p[x]$ of degree equal to the degree $m$ of a finite field $\mathbb F_{p^{m}}$ has a root in the field. Using this result we can count the ...