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.

14
votes
2answers
388 views
+50

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: ...
0
votes
0answers
16 views

Linear Combinations of Solutions to a Search Problem

Let $P_1=(X_1,U_1)$ be a search problem with the domain of search $$X_1=\{x \in Z_2^n | wt(x)\leq k\}$$ and the set of admissable tests be $U=Z_2^n$ (where $wt(x)$ is the hamming weight of $x$). ...
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}$, $...
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 +...
0
votes
3answers
145 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 ...
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
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
96 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
44 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- ...
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 ...
2
votes
1answer
82 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$ ...
0
votes
1answer
44 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
35 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
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$. ...
1
vote
1answer
119 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 ...
7
votes
3answers
219 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
0answers
35 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 ...
1
vote
2answers
63 views

Exercise on number of walks in a graph

The following is an exercise (Exercise #2 (a), Chapter 3, page 28) from Richard Stanley's Algebraic Combinatorics. Let $G$ be a finite graph (allowing loops and multiple edges). Suppose that ...
4
votes
1answer
5k 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. ...
3
votes
0answers
66 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_{...
12
votes
1answer
4k views

Undergrad-level combinatorics texts easier than Stanley's Enumerative Combinatorics?

I am an undergrad, math major, and I had basic combinatorics class before (undergrad level.) Currently reading Stanley's Enumerative Combinatorics with other math folks. We have found this book ...
4
votes
2answers
178 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 ...
8
votes
2answers
220 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 ...
5
votes
1answer
398 views

Properties of the 'forgotten' symmetric polynomials

In I.G. Macdonald "Symmetric Functions and Hall Polynomials" pg.22, the forgotten symmetric functions $f$ are introduced very briefly as the result of applying an involution $\omega$ to the monomial ...
1
vote
1answer
83 views

prove a polynomial identity..

The equation is that $h_m(x_1, \cdots, x_n, a)-h_m(x_1, \cdots, x_n, b)=(a-b)h_{m-1}(x_1, \cdots, x_n, a, b)$ where $h_m$ is a complete homogeneous symmetric polynomial. See and find several ...
3
votes
0answers
49 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 $$...
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=...
4
votes
3answers
197 views

Graph Theory - Application of Kirchoff's Matrix Tree Theorem

Calculate the number of spanning trees of the graph that you obtain by removing one edge from $K_n$. (Hint: How many of the spanning trees of $K_n$ contain the edge?) I know the number is $(n-2)n^{...
1
vote
2answers
376 views

Expressions for symmetric power sums in terms of lower symmetric power sums

The Newton symmetric power sums $p_k(x_1, \ldots, x_n)$, for $k \geq 1$, are given by $$ p_k(x_1, \ldots, x_n) = \sum_{i=1}^n x_i^k. $$ Do you know if it's possible to express $p_k$ in terms of (non-...
13
votes
3answers
2k 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(...
1
vote
2answers
102 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 ...
2
votes
2answers
111 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: (...
10
votes
1answer
348 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)...
2
votes
0answers
106 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, ...
1
vote
0answers
44 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 ...
5
votes
3answers
268 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
2answers
150 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, ...
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
74 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 $\...
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 ...
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
42 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 ...
5
votes
2answers
201 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 ...
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....
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 ...
5
votes
1answer
153 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 ...
4
votes
1answer
81 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 ...
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) ...
1
vote
0answers
151 views

Count the number of functional digraphs with special restrictions

Given a set of $n$ nodes, how can I count the number of possible functional di-graphs whose biggest connected component contains k node? With a restriction that no node can have an edge point to ...