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.

124 questions
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: ...
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$). ...
40 views

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 ...
56 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 $$... 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=... 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^{... 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-... 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(... 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 ... 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: (... 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)... 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, ... 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 ... 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 ... 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, ... 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 ... 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 \... 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 ... 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 ... 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,... 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 ... 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 ... 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.... 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 ... 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 ... 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 ... 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) ...
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 ...