Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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.

Filter by
Sorted by
Tagged with
1
vote
0answers
32 views

Reference for a Dickson Determinant Polynomial

For $2\leq \ell \leq k$, consider the polynomial \begin{equation} P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)\in \mathbb{F}_2[x_1,\ldots, x_k] \end{equation} ...
1
vote
1answer
326 views

Proof that Paley Graphs are strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$

A Paley graph is strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$. I need to prove that, and obtain the parameters too. Proving it is regular valency $\frac{p-1}{2}$ is ...
1
vote
1answer
88 views

No triangles or rectangles in a Moore graph of diameter 2.

Can somebody explain why there cannot be any triangles or squares in a Moore graph with diameter 2? This was stated without proof in my class.
2
votes
0answers
81 views

Proving Crapo's Lemma

Let $L$ be a finite lattice with least and greatest elements $0, 1$, respectively, and let $X\subseteq L$. Let $n_k$ be the number of $k$-element subsets of $X$ with join $1$ and meet $0$. I want to ...
1
vote
0answers
51 views

Orbital dimension of the action of $S_n$ on 2-subsets

I have a question on a proof in a paper on the orbital dimension of a permutation group. Let $G \le S^\Omega$ be a permutation group. A base for $G$ is a subset $\Sigma \subseteq \Omega$ for which ...
8
votes
1answer
651 views

A question on Derangement Combinatorics

Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the ...
1
vote
0answers
79 views

Formula for $q$-Analogue of Eulerian Polynomial

Define $\text{d}(\sigma)$ and $\text{maj}(\sigma)$ to be the number of descents and the major index of the permutation $\sigma$, respectively. Define a $q$-Analogue of the Eulerian Polynomials by $A_n(...
2
votes
1answer
691 views

Counting restricted ordered rooted trees by the number of leaves and non-leaves

I have proved that the number of ordered rooted unlabeled trees on $n+1$ vertices with $j$ leaves is $\dfrac{1}{n+1}\binom{n+1}{j}\binom{n-1}{j}$. I did this by writing a recurrence using that fact ...
2
votes
2answers
799 views

A Variation of the even-town odd-town problem

Let assume facebook has $n$ users. Mark Zuckerberg decided that people are allowed to open groups under the following restrictions: 1) No two different groups can exactly the same participants. ...
10
votes
1answer
162 views

why $\frac{f_n}{f_kf_{n-k}}$ is an integer for this sequence

New Zealand 2013 TST problem: Let $r$ and $s$ be positive integers. Define $a_0 = 0$, $a_1 = 1$, and $a_n = ra_{n-1} + sa_{n-2}$ for $n \geq 2$. Let $f_n = a_1a_2\cdots a_n$. Prove that $\dfrac{f_n}{...
1
vote
2answers
55 views

Maximizing Signless Stirling Numbers

Let $c(n, k)$ denote the number of permutations in $S_n$ whose cycle decomposition has $k$ cycles. For a fixed $n$, I want to find $k$ such that $c(n, k)$ is maximized. I know that the $k$ I seek is ...
0
votes
1answer
204 views

Combinatorial Interpretation of $q$-analogue Stirling numbers?

I have a recursive definition of the $q$-analogue of the Stirling numbers of the second kind. They are given by the recurrence $S_{q}(n,k) = [k]_{q}S_{q}(n-1,k) + q^{k-1}S_{q}(n-1,k-1)$, where $[k]_q=...
2
votes
1answer
479 views

Number of permutations of $[n]$ with a multiple of $n$ inversions

We have a permutation $\left(a_1,a_2,...,a_n\right)$ of the set $\{1,2,...,n\}$. A pair $(a_i,a_j)$ is said to be an inversion of this permutation if $i<j$ and $a_i>a_j$. Find the number of ...
4
votes
1answer
88 views

Can the natural proof of this algebraic identity be simplified?

Let $x^4+c_3x^3+c_2x^2+c_1x+c_0$ be a real polynomial with no real root. Then there are two pairs of conjugate complex roots, $a_1\pm b_1 i$ and $a_2\pm b_2 i$, and one has the identity $$ c_1^2-...
0
votes
0answers
229 views

Generalization of Binary Bracketing

Is there possibly any natural approach to generalize the idea of binary bracketing (bracketing functions) to the continuous case, such that the well-known discrete version becomes a special case of ...
3
votes
0answers
62 views

What do you get when you pull the Bruhat Decomposition back to the Lie algebra via the exponential map?

If $G$ is a connected, reductive, complex group with Borel subgroup $B < G$ and Weyl group $W$, we can write $$G = \bigsqcup_{w \in W} B w B$$ If $\mathfrak{g}$ is the Lie algebra of $G$, we have ...
2
votes
0answers
443 views

Proving Identities using Partition and Generating Function

I have a problem with these two questions: Let $P_E(n)$ be the number of partitions of $n$ with an even number of parts, $P_O(n)$ the number of partitions of n with an odd number of parts, and $...
5
votes
1answer
426 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 ...
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
1answer
101 views

Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
4
votes
0answers
62 views

Is there anywhere some explicit Bruhat decompositions are written down?

Question in title: most places I see Bruhat decompositions treated they're only briefly mentioned and no examples are given. Also, I calculated the following regarding the Bruhat decomposition of $\...
14
votes
6answers
770 views

Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
1
vote
0answers
773 views

Pfaffian And Determinant

I am working in tilings using Pfaffian. There is a basic property, namely: Let $ B$ be a $n\times n$ matrix. Let $$ A = \begin{pmatrix} 0 & B\\ -B^T & 0 \end{pmatrix}$$ then $$\...
3
votes
1answer
83 views

Prove that $h_r(x_1,\dots,x_n)=\sum^n_{k=1}x^{n-1+r}_k\prod_{i\neq k}(x_k-x_i)^{-1}$

Let $h_r\left(x_1,\ldots,x_n\right)$ denote the $r$-th complete homogeneous symmetric polynomial in the $n$ indeterminates $x_1, \ldots, x_n$ (that is, the sum of all degree-$r$ monomials in these $n$ ...
-1
votes
2answers
372 views

Young tableaux of shape lambda. [closed]

Consider the partition $\lambda=(m,n-m)$ of $n$ (thus $2m \ge n$). The number of standard Young tableaux of shape $\lambda$ is given by $$f_{(m,n-m)} = \binom nm - \binom{n}{m+1}$$ a) Prove this ...
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(...
2
votes
0answers
189 views

Symmetrization of Powersum polynomials

Let $n\in\mathbb{N}$. Then, for $i\in\mathbb{N}$, the $i-$th power sum if defined to be the polynomial $p_i^{(n)}:=\sum_{j=1}^n x_j^i$ in $n$ indeterminates $x_1,x_2,\ldots,x_n$. Then let $\lambda:=(\...
7
votes
2answers
242 views

Given a list of $2^n$ nonzero vectors in $GF(2^n)$, do some $2^{n-1}$ of them sum to 0?

Let $G=(\mathbb{Z/2Z})^n$ written additively, $n>1$. (you can think of it as $\mathbb{F}_{2^n}$ but I didn't find that useful... yet) Let $v_i$ be nonzero elements of $G$ for $i \in \{1 \dots 2^n \...
11
votes
2answers
3k views

Identity involving partitions of even and odd parts.

First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions ...
7
votes
0answers
310 views

Uses of Chevalley-Warning

In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows: We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the ...