Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
56 views

Crystal operators

Define the operator $s_i$ on tableaux: Consider letters $i$ and $i + 1$ in row reading word of the tableau. Successively “bracket” pairs of the form (i + 1, I ). Left with word of the form $i^r (i +...
3
votes
0answers
56 views

skew Schur identity

Let $\lambda$ be a partition of size at least 2, and let $n>0$ be an integer. Prove that $$s_{\lambda/(1)}.h_{n}=\sum_{\lambda^{+}\supseteq \lambda\\\lambda^{+}/\lambda\ \text{hor.} \ n\ \text{...
0
votes
3answers
112 views

Number of permutations with all cycles of even length

For even $n$ (only!), let $e_n$ stand for the number of permutations with all cycle of even length. Let $E(x)$ be the exponential generating functions. Prove that $E(x) = (1 - x^2)^{-\frac12}.$ I ...
0
votes
0answers
26 views

Recurrence for $k$-ary trees

The question is to find a recurrence, and a generating function for the number of rooted complete $k$-ary trees with $n$ non-leaves, that is, those rooted trees in which each node has either 0 or $k$ ...
3
votes
1answer
95 views

Classification of groups whose any non-trivial element can be associate to another to generate all

Question: What are the groups (possibly infinite) $G$ satisfying the following property? $$ \forall g \in G \setminus \{ e \} \ \exists g' \in G \text{ such that } \langle g,g' \rangle = G.$$ ...
0
votes
2answers
42 views

Combinatorial problem discrete math

Find the no of ways of placing 6 identical balls into 3 distinct boxes in such a way that first box contains 0,1 or 2 objects,2bd box contains 1,2,3 objects and 3rd one contains 3 or 5 objects. Ans- ...
0
votes
1answer
43 views

Convergence of Exponential Generating Functions

In page 10 of "Enumerative Combinatorics by Stanley, volume 2", let $h(n)=2^{n \choose 2}$ be the number of graphs on an $n$-element vertex set $S$. And let $c(n)$ be the number of connected graphs on ...
0
votes
1answer
34 views

Citation/Reference for this Formula [closed]

Does anyone know any sources that could possibly be used as a citation of some form of the formula below? $$\sum_{n=0}^{k} (a+n)(b-n) = (k+1)ab + \frac{k(k+1)}{2}(b-a)+\frac{k(k+1)(2k+1)}{6}$$
2
votes
1answer
81 views

We have a connected graph with $2n$ nodes. Prove that exist spanning subgraph each node with odd degree.

We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree. Idea: Let $M$ be an adjacency matrix and work all over field $\mathbb{Z}_2$. Then if $M$ ...
2
votes
0answers
33 views

Chromatic Polynomial of Circulant Graph with Two Parameters

It is easy to get the Chromatic-Polynomial of a Circulant-Graph of size $n$ with one parameter $P[C_{n}(i),x]$. Is there a way to get an explicit formula for the chromatic polynomial of a circulant ...
3
votes
0answers
64 views

Question on Vertex Labeling (Related to Lucky Labeling of Graphs)

Suppose that for any bipartite planar graph $G=(V,E)$, we can find a vertex labeling $c:V\to \{1,2,3\}$ such that for any two adjacent vertices $u$ and $w$: $$c(u)-\sum_{v\in N(u)}c(v)\neq c(w)-\sum_{...
3
votes
0answers
47 views

Show COMBINATORIALLY the number of irreducible monic polynomials is the number of primitive necklaces

Show that the number of monic irreducible polynomials of degree $n$ over a finite field of size $q$ is the same as the number of primitive necklaces of size $n$ with $q$ colors. I have the formula $$...
1
vote
1answer
117 views

Vishnoi's Proof of Combinatorial Nullstellensatz

The question was already asked here: Question regarding a proof of the Combinatorial Nullstellensatz, but I am having trouble understanding the document in the comment, and so I was wondering if ...
1
vote
2answers
101 views

Applying Burnside's lemma to show there are $k+n-1 \choose k-1$ ways to store n stars in k bins?

Usually it is proven using multisets I think, but I wondered how Burnside's lemma could be applied. Everytime I tried to wrap it around my head the indices didn't seem to fit. So I TeXed it and ...
7
votes
3answers
215 views

How many $n$-pointed stars are there?

Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars ...
2
votes
2answers
110 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: (...
1
vote
0answers
42 views

Hook-length formula [closed]

Let $\lambda=(\lambda_1,\ldots,\lambda_n)$ be a partition of $d$. Then hook length formula gives us $$dim(\lambda)=\chi_{1^d}^{\lambda}=\frac{d!}{\prod h_{\lambda}(i,j)}$$ where $\chi_{a}^{b}$ denote ...
10
votes
1answer
343 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)...
5
votes
3answers
267 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 ...
2
votes
0answers
96 views

Seeking Algebraic Number Fields introductory text at amateur level.

I'm exploring "Singular Binary Bracelets": size p=2q+1 with p,q prime, q unit beads, resultant amplitude squared is integer. I will try to explain why I think that 'Algebraic Number fields' is needed, ...
4
votes
3answers
196 views

We are given an $18\times 18$ table, all of whose cells may be black or white.

We are given an $18\times 18$ table, all of whose cells may be black or white. Initially all the cells are colored white. We may perform the following operation: choose one column or one row and ...
4
votes
0answers
73 views

Constant sum of characters

Let $q$ be a prime power and $\omega=\exp(2\pi i/q)$. For a fixed $y\in\mathbb{Z}_q^n$, the map $$\mathbb{Z}_q^n\ni x\mapsto \omega^{x\cdot y}=\omega^{x_1y_1+\dots+x_ny_n}$$ is a character of $\...
2
votes
2answers
146 views

Paths must cross in Lindström-Gessel-Viennot on the lattice

The following question (which I am going to answer myself) serves to close a little gap in some combinatorial proofs that use the Lindström--Gessel--Viennot lemma. Namely, I will show a little lemma, ...
2
votes
2answers
109 views

Proof of an identity about integer partition

I'd like to know how to prove the following identity, $$\sum_{k=1}^n k\, p(n, k) = \sum_{r,s\ge 1, rs\le n} p(n-rs)$$ where $n\in N^+$. Here, $p(n)$ counts the number of possible partitions of $n$. ...
6
votes
3answers
151 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 ...
5
votes
2answers
148 views

There are $n$ different $3$-element subsets $A_1,A_2,…,A_n$ of the set $\{1,2,…,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

Determine all possible values of positive integer $n$, such that there are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not=...
0
votes
0answers
34 views

Holonomic functions and degree bounds

Let $A(x)$ is a generating function annihilated by the following differential equation of order $r$ and degree $d$. The degree of the differential equation is given by the maximal degree of the ...
0
votes
1answer
23 views

reference request: Type A crystal proof of Schur-positivity

In this question: https://mathoverflow.net/questions/272306/what-techniques-are-there-to-prove-schur-positivity, one of the techniques listed to prove Schur-positivity is called a Type-A crystal proof,...
2
votes
0answers
40 views

An infinite basis for an ad hoc vector space

To prove a combinatorial identity I'm building an ad hoc vector space that I will define below. First, I define the set of Pseudo Power Series. A Pseudo Power Series (pps) $\alpha$ is an ...
1
vote
1answer
40 views

Cyclotomic scheme is a Association scheme

I try to show that the following defines an association scheme: Let $\mathbb{F}_q$ be a field, $\omega$ a primitive element of $\mathbb{F}_q^\times$ and $s$ divides $q-1$. Define $r=\frac{q-1}{s}$, $...
5
votes
2answers
198 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 \begin{equation} \eta \big( \lambda \big) \ := \ \sum_{i=1}^k ...
5
votes
1answer
139 views

Young projectors in Fulton and Harris

In Section 4 of Fulton and Harris' book Representation Theory, they give the definition of a Young tableau of shape $\lambda = (\lambda_1,\dots,\lambda_k)$ and then define two subgroups of $S_d$, the ...
14
votes
1answer
275 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: ...
2
votes
1answer
47 views

What breaks down in the theory of affine hyperplane arrangments?

It appears to me that there is a substantial amount of combinatorial algebra and geometry supporting the theory of central hyperplane arrangements (See Topics in Hyperplane Arrangements, Aguiar and ...
0
votes
0answers
37 views

Guess the recursion

I want to know if there is a package in Mathematica or maple that can give back some recursion given a list of polynomial in $f_{n}(h)$. I want a recursion of the from $$ \sum_{k=0}^{N}a_{k}(h)f(n+k) ...
4
votes
1answer
79 views

Prescriptive version of counting hyperplane arrangements

In Hyperplane arrangement theory, Zaslavsky's Theorem necessarily bounds the number of bounded and unbounded regions in the complement of a real hyperplane arrangement. While this counting theorem is ...
2
votes
1answer
83 views

Counting solutions to equations involving partitions

This is a problem that has come up in my research and seems to be true from numerical tests via Mathematica. It should be provable in general, but I have been unable to show it so far. It would be ...
2
votes
0answers
61 views

About the determinant of a symmetric matrix with even diagonal

Let $A$,$B$ two integer, symmetric, $n\times n$ matrix with even diagonal. We suppose also that $A$ has odd determinant (so $n$ is even). Even discarding the hypothesis of even diagonal for $A$ it'...
8
votes
2answers
218 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 ...
0
votes
1answer
31 views

About combinatorics

$$x = -\sum_{k=1}^p \binom{p}{k} p^{k-2}\bigl(-xA(x)\bigr)^k$$ For degree $n>1$, the left hand side of the equation is equal to $0$. Setting $0$ equal to the degree $n$ term of the right hand side ...
2
votes
1answer
73 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)$.
0
votes
0answers
49 views

How can I enumerate sets of inequalities that give a nonempty feasible region?

My goal is this. I have variables $a_1, a_2, ..., a_n \geq 0$. I also must choose a set of inequalities. My choices are as follows: $\forall S \subseteq [n]$, choose $\sum \limits _{i \in S} a_i \geq ...
1
vote
1answer
28 views

Unbounded, Repeated Figures in Non-periodic Tilings

I was just wondering something about non-periodic tilings (of the plane, though I imagine the dimension is irrelevant for finite dimensions; would be interesting if it wasn't!). I assume we know what ...
9
votes
1answer
376 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 ...
4
votes
1answer
120 views

Interpretation of the numerator of the Hilbert series?

Let $R$ be a finitely generated graded ring over a field $k$. Let $R_\ell$ be the degree-$\ell$ homogeneous component of $R$. By the Noether normalization theorem, $R$ is finite over a graded ...
0
votes
1answer
33 views

How many ways to place $m$ labelled balls into $n$ labelled boxes such that at least one box has more than $k$ balls

There are $n^m$ ways to place $m$ labelled balls into $n$ labelled boxes with no constraints. When it comes to the problem such that at least one box has more than $k$ balls. My thought was Step 1....
1
vote
1answer
84 views

Is there any proof of this identity?

$$\prod\limits_{i=1}^{\infty}\frac{1}{1-yx^{i}}=\sum\limits_{k=0}^{\infty}\frac{y^k x^k}{(1-x)(1-x^2)...(1-x^k)}$$ I know its combinatorial proof through "inspection",but is it true when $x,y$ are ...
2
votes
0answers
54 views

Representation theory of the symmetric group

I'm trying to understand the representations of $k\mathfrak{S}_3$, where $k$ is a field of characteristic $2$. Could someone explain the permutation module $M^{(1^3)}$ has a filtration layers ...
0
votes
0answers
33 views

Is there any way to simplify $\frac{1}{2^{n - 1}}\sum_{i=0}^{n - 1} {\binom{n - 1}{i}}{a[i]}$?

Here $a[i]$ denotes the i'th element (0 indexed) of a tuple. The goal is to avoid the huge coefficients since I know the final result won't be very big (in proportion to the elements of the tuple). I ...
2
votes
0answers
88 views

Invariants in the ring of coinvariants

This seems to be part of folklore, but I can't find a proof anyqhere, only references to "a very nice proof of a special case by Arkady Berenstein in a seminar I attended in 1989". Okay, here it goes....