Stack Exchange Network

Stack Exchange network consists of 174 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
1answer
34 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
28 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
67 views

We have a connected graph with $2n$ nodes. Prove that exsist 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
25 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 ...
2
votes
0answers
58 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
35 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
99 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
90 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
180 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 ...
1
vote
2answers
87 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
32 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
329 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
226 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
94 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
179 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
68 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
108 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
90 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
146 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
143 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
32 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
19 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
38 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
34 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
189 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
108 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 ...
2
votes
0answers
36 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
31 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
75 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
80 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 ...
0
votes
0answers
42 views

Abelian groups have subexponential growth

A group $G$ is said to have subexponential growth if $$\underset{n \to \infty}{\limsup}|E^n|^{\frac{1}{n}}=1,$$ for any finite subset $E \subseteq G$, where $E^n=\lbrace g_1g_2...g_n \mid g_i \in E \...
2
votes
0answers
56 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
210 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
30 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
64 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
46 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
27 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
362 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
93 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
82 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
52 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
71 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....
1
vote
0answers
51 views

Murnaghan-Nakayama rule for general dimension of a hook

Let $m,r\in \mathbb{N}, n=rm$. The character of symmetric group $\chi^{\lambda}$ where $\lambda$ is of the from $(k,1^{n-k})$ evaluated at the conjugacy class of $S_{n}$ of the from $(r,\ldots,r)$, ...
1
vote
0answers
35 views

How does the sum of closed walks change when a new vertex is added to a subgraph?

Suppose I calculate the sum of all closed walks from vertex i in a subgraph of some graph (the subgraph is composed of a subset of vertices from the graph and all edges between those vertices from the ...
1
vote
1answer
290 views

Is there a explicit formula for the number of Semi-standard Young Tableaux over $\{1,\dots,n\}$ for a given partition $\lambda$ and a given type $\mu$

I was given an exercise to give all SSYT over $\{1,\dots,12\}$ of shape $\lambda=(4,4,3,1)$ and type $\mu=(4,2,2,2,2,0,\dots,0)$. Now I was wondering if there is an formula to say something about the ...
2
votes
1answer
103 views

Counting monic irreducible polynomials of a particular degree without use of finite fields?

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 ...
0
votes
2answers
90 views

What is the expected value of the product of the number of heads you get and the number of tails you get when you flip n coins? [closed]

Ex. If you get $h$ heads and $n-h$ tails the product would be $n(n-h)$ I want to know the expected value of this product.
4
votes
2answers
155 views

What do we mean when we say the Schur functions form a basis.

This has always bugged me. When we are examining symmetric functions (or polynomials if you prefer finitely many variables), we have an easy choice of basis with the monomial symmetric functions. As ...