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.
212
questions
-1
votes
0
answers
56
views
Can you help me finding another non trivial families of groups indexed by an infinite countable ordered set? [closed]
Symmetric groups are indexed by nonnegative integers and Young subgroups are indexed by composition of integer. Some Coxeter groups are indexed by integer. Can someone help me finding another non-...
0
votes
0
answers
7
views
Local h-polynomial with V=3.
I'm trying to understand an example that Stanley gives in his article "Subdivisions and local h vectors". It is example 2.3 part d).
If #V=3 and $h(\Gamma,x)=h_0+h_1x+h_2x^2+h_3x^3$ (so $...
- 1
1
vote
0
answers
25
views
Subtracting four numbers in cycles
Arbitrarily give four positive numbers, assuming $A_1, B_1, C_1, D_1$;
In $A_1$ and $B_1$, subtract the smaller from the larger (0 if equal),
and the result is $A_2$; In $B_1$ and $C_1$, subtract the ...
- 1,756
0
votes
3
answers
90
views
Why is this probability > 1?
I'm going to blow my brains out.
I have 27 cards of red, blue and green cards. There is 9 of each color. I draw 12 cards. What is the probability that I have AT LEAST 6 blues, AT LEAST 1 red and AT ...
4
votes
1
answer
97
views
Is there a $q$-analog for the product of binomial coefficients?
The $q$-analog of the binomial coefficient $\binom{n}{k}$ may be defined as the coefficient of $x^k$ in $\prod_{i=0}^{n-1}(1+q^ix)$.
Classical arithmetic identities tend to have $q$-analogs. I am ...
- 1,608
3
votes
1
answer
62
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
21
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
25
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 $\...
- 3,892
1
vote
0
answers
16
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
15
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{...
- 73
-3
votes
1
answer
124
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
32
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 ...
- 584
2
votes
0
answers
139
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
77
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
157
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
0
answers
55
views
Forgotten Symmetric Functions
Let A be a partition of n of length $\lambda$. Define the forgotten symmetric
function $f_\lambda$ by $f_\lambda = \varepsilon_\lambda \omega(m_\lambda)$,
where $\varepsilon_\lambda = (-1)^{n-l}$ as ...
0
votes
2
answers
94
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
37
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
62
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 ...
- 700
1
vote
0
answers
27
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}$ ...
- 115
2
votes
0
answers
63
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 $...
- 584
18
votes
1
answer
570
views
Let $p$ be a prime number and $S\subseteq\{1,2,\cdots,p-1\}$ be a subset such that $|S|>p^{\frac{3}{4}}$...
Let $p$ be a prime number and $S\subseteq\{1,2,\cdots,p-1\}$
be a subset such that $|S|>p^{\frac{3}{4}}$. Prove that for every
positive integer $m$, there exist
$a_{1},a_{2},b_{1},b_{2},c_{1},c_{2} ...
- 88.5k
1
vote
1
answer
64
views
What is the Lie theoretic interpretation of conjugate of a partition?
For a partition $\lambda$ it is very well-known operation to take its conjugate partition $\lambda'$ which is obtained by transposing the Young diagram of $\lambda$.
A partition $\lambda$ can be ...
- 217
2
votes
0
answers
51
views
When does multiplying by an involution increase the Bruhat Order in the Symmetric Group?
Let $w \in \mathrm{Sym}(n)$ for some positive integer $n$. Let $r$ be an involution in $\mathrm{Sym}(n)$, and write it as the product of disjoint transpositions like so: $$r = \prod_{i=1}^k (a_i,b_i) $...
- 317
1
vote
0
answers
26
views
Determinant of $(p(x_i-x_j))_{1 \leq i,j \leq n}$ for polynomial $p(x)$.
Let $p(x) = a_0 + a_1 x + \ldots + a_k x^k$ be a polynomial.
Can anything be said in general about the determinant $\mathrm{det}_{1 \leq i,j \leq n} (p(x_i-x_j))$ for a collection of variables $x_1,\...
- 299
4
votes
1
answer
39
views
Can the product of two quasisymmetric functions (that are not symmetric) be symmetric?
Given two quasisymmetric functions (see definition below) that are not symmetric, must their product also not be symmetric?
From Stanley's Enumerative Combinatorics 2, recall that a function $f\in \...
- 83
1
vote
0
answers
35
views
Hyperplane arrangement : The Shi arrangement
I have been lately reading Hyperplane arrangement lectures by Richard Stanley on https://www.cis.upenn.edu/~cis610/sp06stanley.pdf . In lecture 5, Theorem 5.16 we define the characteristic polynomial ...
- 11
3
votes
0
answers
63
views
Common divisor of Gaussian coefficient expressions
I have a question about common divisors of some expressions involving Gaussian coefficients, in particular in the case ${n \brack 1}_{q} = \frac{q^{n}-1}{q-1}$ where $q$ is a prime power.
It is well ...
- 13.1k
0
votes
1
answer
87
views
Prove for all $λ$ contained in $k×l$ box, $w_λ=\sum_{x\in Add(λ)} w(x)-\sum_{y\in Remove(λ)} w(y)=kl-2|λ|$ is positive as long as $n=|λ|<\frac{kl}2$ [closed]
I am learning Algebraic Combinatorics from MIT-OCW. Doubt is from the Lecture Notes-$20$,
PDF Link for Notes
In Lemma $190$
For all $\lambda$ contained in a $k\times l$ box, $$w_\lambda=\sum_{x\in ...
- 11
0
votes
1
answer
86
views
generating function of finite sum involving $\left(\!\!\binom{n}{k}\!\!\right)$ [closed]
Notation:
$$
\left(\!\! \binom{n}{k}\!\!\right)={n+k-1 \choose k}=\frac{(n+k-1)!}{k!(n-1)!}
$$
where $n!$ is the factorial, i.e. $1\cdot 2\cdots n.$
Let $n,N\in \mathbb{Z}_{>0}.$ I'm stuck at ...
0
votes
0
answers
27
views
Binomial coefficient identities from h-vector of a simplicity complex. [duplicate]
My question is to show the below equality
$$\sum_{j=0}^{d}(-1)^{j}\binom{d}{j}\binom{d-j}{i}=0$$
when $d>i \geq 0$ for any integers $d,i$.
This inequality is came from Stanley's note. Given an $f$-...
- 1,697
1
vote
1
answer
71
views
Operations with Circulant Matrix using GAP
I am newbie using GAP software.
I need to know how to use GAP software for algebraic computations with circulant matrix.
Some examples would suffice.
Just for clarity
Circulant Matrix: In linear ...
- 119
14
votes
3
answers
279
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,669
1
vote
2
answers
143
views
Minimum value of factorial multiplication
I studied that if x + y + z = 3n (i.e if value of x+y+z is some fixed number which is multiple of 3) then minimum value of
x!y!z! is when x=y=z.
How can we prove this statement?
Attempt:
Well, I ...
- 333
1
vote
0
answers
17
views
Change of coordinate and Linear Ode
Let $G(z)$ be a rational function. So if we have a series
$$S(x):=\sum_{n}a_n x^n $$ where
$$ a_n = \prod_{i=1}^{n}G((i-1)h) $$
We can conclude that the series satisfies a Linear differential ...
- 1,015
3
votes
0
answers
68
views
Representation for the Bose-Mesner algebra and its dual.
If you are familiar with the algebra, just skip the following brief introduction, that is fine.
In the study of Bose-Mesner algebra. We know given that the commutative association scheme $\mathfrak{X}...
- 1,364
2
votes
0
answers
135
views
The Schwartz genus of a fibration
I'm working on the topological complexity of a path connected space, which is a particular case of the sectional category (or the Schwartz genus), but all the articles refer to an other article named &...
- 49
1
vote
2
answers
128
views
change of summation, Hermite polynomial formula from generating functions
Now given the exponential generating function of the Hermite polynomial $$e^{ux-(1/2)u^2} = 1+\sum_{n=1}^\infty \dfrac{u^n}{n!}h_n(x),$$how do I derive the closed form formula of the Hermite ...
- 315
1
vote
1
answer
99
views
Cycle indicator symmetric function and Polya's theorem
Let $G$ be a subgroup of the symmetric group $S_n$. Given a partition $\lambda$ of $n$, denote by $n_G(\lambda)$ the number of elements in $G$ of cycle-type $\lambda$. The cycle indicator function of $...
- 2,020
2
votes
1
answer
154
views
Operate an aviation network without condition: Each city has a direct flight to 3 other cities; There is always a flight visiting all cities once each
Problem. A country has $10$ cities. Operate an aviation network within $2$ following conditions:
a. Each city has a direct flight to exactly $3$ other cities.
b. From a beginning city, there is always ...
user822157
3
votes
0
answers
71
views
Is the poset of all subsets of a collection of sets rank-unimodal?
I'm working on Richard P. Stanley's Algebraic Combinatorics and have been stuck on this problem for a while:
Let $S_1, S_2,..., S_{k}$ be finite sets with $\#S_1 = \#S_2 = ... = \#S_{k}$. Let $P$ be ...
- 124
0
votes
1
answer
194
views
Prove or disprove that there exists no more specific match-ups involving these 4 third-placed teams for the round of 16 other than
UEFA EURO 2020 has been just started, still with the format of 24 teams. The top 2 in each groups will proceed to the round of 16 along with the best of 4/6 third-placed finishers. Prove or disprove ...
user822157
5
votes
0
answers
458
views
Suppose we have $n$ points in a plane, not all on the same line. Then they are determining at least $n$ different lines.
Suppose we have $n$ points in a plane, not
all on the same line. Then they are determining at least $n$
different lines.
Suppose points $T_1,...,T_n$ determine $m$
lines
$$\ell_i(x,y) :\;\;a_ix+b_iy+...
- 88.5k
5
votes
1
answer
127
views
Has anyone found this formula before? [closed]
I found this formula.
\begin{equation}
\sum_{\lambda \vdash n}\frac{2^{l(\lambda)}}{z_{\lambda}}=n+1
\end{equation}
where $\lambda \vdash n$ means that $\lambda$ is an integer partition of $n$, $l(\...
1
vote
1
answer
42
views
On the dimension of an abstract simplicial complex built from minimal vertex covers of a finite simple graph
Let $G$ be a finite simple graph on a vertex set $\{x_1,...,x_n\}.$ Let us call a vertex cover of $G$ to be minimal if none of its proper subset is a vertex cover. Let $C_1,...,C_h$ be the collection ...
- 1,344
0
votes
0
answers
74
views
Hall Scalar product calculation: $\langle h_3p_6, s_{(5,4)}\rangle$
This is a problem from an old qualifying exam I am reviewing:
Calculate: $\langle h_3p_6, s_{(5,4)}\rangle$ where $\langle \cdot,\cdot \rangle$ is the Hall scalar product defined by $\langle s_\lambda,...
3
votes
1
answer
420
views
Infinite product of infinite sums of formal power series: proof?
Teaching a course on algebraic combinatorics has made me aware of a technical fact about formal power series that is used throughout the subject, but that I have never seen formally stated, let alone ...
- 17k
3
votes
1
answer
76
views
Prove that the Following Graph Has $p F^2_p$ Spanning Trees
I am working on Algebraic Combinatorics by Richard P. Stanley.
Problem 4 on Chapter 9 reads:
Let $p \ge 5$, and let $G_p$ be the graph on the vertex set $\mathbb{Z}_p$ with edges $\{i, i+1 \}$ and $\{...
- 502
4
votes
0
answers
113
views
Generalized Hertzsprung Problem
The Hertzsprung Problem goes as follows: In how many can we place exactly $n$ non-attacking kings on a $n \times n$ chessboard such that there is exactly $1$ king in each row and column where $n \in \...
- 842
8
votes
1
answer
530
views
Let $B\subset A = \{1,2,3,...,99,100\}$ and $|B|= 48$. Prove that exist $x,y\in B$, $x\ne y$ such that $11\mid x+y$.
Let $B\subset A = \{1,2,3,...,99,100\}$ and $|B|= 48$.
Prove that exist $x,y\in B$, $x\ne y$ such that $11\mid x+y$.
Proof: Let $P_0:= \{11,22,...,99\}$ and for $i=
1,2,...49$ and $11\nmid i$ make ...
- 88.5k