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.
38
questions
36
votes
1
answer
15k
views
Undergrad-level combinatorics texts easier than Stanley's Enumerative Combinatorics?
I am an undergrad, math major, and I had basic combinatorics class using Combinatorics and Graph Theory by Harris et al before (undergrad level). Currently reading Stanley's Enumerative Combinatorics ...
- 517
15
votes
2
answers
4k
views
Identity involving partitions of even and odd parts.
First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions ...
- 153
14
votes
6
answers
1k
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 ...
- 547
3
votes
3
answers
2k
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.
...
- 718
20
votes
3
answers
5k
views
Hartshorne Problem 1.2.14 on Segre Embedding
This is a problem in Hartshorne concerning showing that the image of $\Bbb{P}^n \times \Bbb{P}^m$ under the Segre embedding $\psi$ is actually irreducible. Now I have shown with some effort that $\psi(...
user38268
8
votes
5
answers
268
views
Algebraic proof of $\sum_{k}\binom{n}{2k}\binom{2k}{k}2^{n-2k}=\binom{2n}n$ (Combinatoric proof is given)
I had a IMO training about double counting. Then, there is a problem which I hope there is a combinatoric proof. Here comes the problem:
For every positive integer $n$, let $f\left(n\right)$ be ...
- 4,043
16
votes
4
answers
2k
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 following ...
- 378
8
votes
2
answers
381
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 ...
- 26.7k
4
votes
1
answer
8k
views
Use of rook polynomials
Use rook polynomials to count the number of permutations of $(1,2,3,4)$ in which $1$ is not in the second position, $2$ is not in the fourth position, and $3$ is not in the first or fourth position. ...
- 61
2
votes
0
answers
130
views
Proving Crapo's Lemma
Let $L$ be a finite lattice with least and greatest elements $0, 1$, respectively, and let $X\subseteq L$. Let $n_k$ be the number of $k$-element subsets of $X$ with join $1$ and meet $0$. I want to ...
- 9,205
14
votes
3
answers
324
views
Family of sets with $|F_i| \equiv 2\pmod 3$ and $|F_i \cap F_j| \equiv 0 \pmod 3$
Let $p$ be a prime. By considering the incidence vectors of subsets $F_1,\ldots,F_m$ of $\{1,2,\ldots,n\}$, such that $|F_i| = a \not\equiv 0 \pmod p$ and $|F_i \cap F_j| \equiv 0 \pmod p$ for all $1\...
- 2,853
11
votes
0
answers
297
views
Clubs whose intersections are multiples of six (Oddtown variant)
This is a question about generalizing the famous "Clubs in Oddtown" problem. The original setup is that a town has $n$ people, and $m$ clubs each consisting of a subset of the population. ...
- 78.4k
11
votes
1
answer
635
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) ...
- 1,872
10
votes
1
answer
205
views
why $\frac{f_n}{f_kf_{n-k}}$ is an integer for this sequence
New Zealand 2013 TST problem:
Let $r$ and $s$ be positive integers. Define $a_0 = 0$, $a_1 = 1$, and $a_n = ra_{n-1} + sa_{n-2}$ for $n \geq 2$. Let $f_n = a_1a_2\cdots a_n$.
Prove that $\dfrac{f_n}{...
- 626
9
votes
1
answer
513
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 ...
- 26.7k