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.
265
questions
3
votes
1
answer
82
views
Given a transitive and faithful permutation group $G$, is each set of syntactically transitive permutations connected by another permutation in $G$?
$G$ is a permutation group of degree $n \geq 4$ which acts transitively and faithfully on a set $X$ with $|X| = n$.
Given indices $i < j < k \leq n$, elements $\alpha \neq \beta \neq \gamma \in ...
- 317
0
votes
0
answers
26
views
Proving Pascal's Identity for more than two terms [duplicate]
This involves a slightly different version of Pascal's Identity but is still based on it.
Prove that
$$
{a \choose k} + {a+1 \choose k} + \dots {a+n \choose k} = {a+n+1 \choose k+1}
$$
I have tried to ...
3
votes
0
answers
31
views
Decidability of Wilf Equivalence
I have seen a lot of papers discussing whether various permutation classes are Wilf equivalent to each other. I wonder if we could solve such problems in general with computers.
More rigorously, let $\...
- 9,080
1
vote
0
answers
49
views
Number of semi-standard Young tableaux of shape $\lambda$ with some entries fixed
Given a partition $\lambda$, the number of semi-standard Young tableaux (SSYT) of shape $\lambda$ with maximum entry $n$ is given by
\begin{equation}
\prod_{1\leq i<j\leq n} \frac{\lambda_i-\...
- 11
2
votes
0
answers
22
views
Derivation of the Macdonald operator $D_{n}(X;q,t)$
Since I first encountered Equation (3.2) on p.315 of Macdonald's Symmetric functions and Hall polynomials, I have wanted to know where it comes from. So how does one derive the operator
\begin{...
- 98
-3
votes
1
answer
127
views
Proving combinatoric identities with the inclusion and exclusion principle
Let V be a finite set and let the number $a(F) \in\Bbb R$ for $ F \subseteq V$.
We define the numbers
$$b(G, E) = \sum_{E\subseteq F\subseteq G} (-1)^{|G-F|} a(F)$$
where $E\subseteq G\subseteq V$...
user732679
0
votes
1
answer
62
views
Clique-coclique bound in association scheme
Let $A_0=I,A_1,\dots,A_k$ be the assocation matrices of a $k-$ class association scheme $R_0,\dots,R_k$ on a set $X$. Let $K \subset \{0,1,\dots,k\}$. We say a subset $Y \subset X$ is a $K-$coclique ...
- 608
2
votes
0
answers
151
views
Prove $\sum_{n \ge 0} (n+1)^{n-1}\frac{x^n}{n!} =(1- \sum_{n \ge 1} (n-1)^{n-1} \frac{x^n}{n!}) ^{-1}$
Is it possible to prove that
$$\sum_{n \ge 0} (n+1)^{n-1}\frac{x^n}{n!} =(1- \sum_{n \ge 1} (n-1)^{n-1} \frac{x^n}{n!}) ^{-1}$$
Where $(n-1)^{n-1} := 1$ for $n=1$
Idea:use the Lagrange inversion ...
user732679
-1
votes
1
answer
83
views
How many ways can someone choose a permutation $w $ and color each one of the integers [n] so that the minimum element of every cycle of w is white?
In how many ways can someone choose a permutation $w \in S_n$ and color each one of the integers $1,2,\ldots,n$ white, yellow or blue so that the minimum element of every cycle of $w$ is white?
...
user732679
1
vote
1
answer
192
views
the number of sequences is equal to the number of permutations
Consider the product
$A_n = \left\{1\right\} \times \left\{1,2\right\} \times \cdots \times \left\{1,2,\ldots,n\right\}$.
For $\sigma = (a_1, a_2, . . . , a_n) \in A_n$, define the set of descents
$\...
user732679
0
votes
2
answers
104
views
Prove that the coefficients of F(x) are positive integers [closed]
Consider the formal power series
$$F(x) = \sum_{k\ge0}(x+x^2-x^3)^k$$
How can I show that the coefficients of F(x) are positive integers?
I wrote the F as
$F(x) = 1/(1-x-x^2 +x^3) = 1/((x-1)^2(x+1))$
...
user732679
2
votes
0
answers
47
views
Can we characterize the “associate classes” of a unipotent quasi-commutative quasigroup as some combinatorial design?
$I_n$ is the $n \times n$ or order $n$ identity matrix, $J_n$ is the order $n$ matrix of all ones, and $n \in \mathbb{Z}^+$.
We define a Latin square $\mathcal{L_n}$ to be a set of $n$ permutation ...
- 317
5
votes
1
answer
91
views
Are there interesting combinatorial proofs which use more sophisticated grouping than sign-reversing involutions?
There are many combinatorial proofs which establish interesting identities by designing suitable "sign-reversing involutions" on a set of relevant signed objects.
For example, Benjamin and ...
- 729
1
vote
0
answers
39
views
Evaluating character functions
Immanants generalize the notion of determinant and permanent, and it is defined as $$Imm_{\lambda}(A)=\sum_{\sigma \in S_n}\chi_{\lambda}(\sigma)\prod_{i=1}^{n}a_{i,\sigma(i)}$$
where $\chi_{\lambda}$ ...
- 125
2
votes
0
answers
123
views
Clique-coclique bound for vertex-transitive graphs
Let $G$ be a vertex-transitive graph, with $A$ a clique and $B$ a coclique. Prove that $|A||B| \leq |G|$.
Some observations:
Let $a_1, a_2 \in A$ and $b_1, b_2 \in B$. If $f,g \in Aut(G)$ such that $...
- 608