Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

-1
votes
1answer
41 views

Combinatorical meaning of such expression

Any combinatorical meaning or interpretation of $$1^{\alpha_1}2^{\alpha_2}3^{\alpha_3}...s^{\alpha_s}\alpha_1!\alpha_2!...\alpha_s!$$ for partition ...
6
votes
1answer
226 views

Flooding a cycle digraph via chip-firing: $n^{k-1} + n^{k-2} + \cdots + 1$ bound (a Norway 1998-99 problem generalized)

Let $k > 1$ and $n$ be positive integers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Let $D$ be a digraph which has exactly $k$ vertices $v_0$, $v_1$, ..., $v_{k-1}$ and exactly $k$ arcs $v_0 ...
1
vote
1answer
52 views

Hadwiger-Nelson problem in higher dimensions

Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by $V(\text{HN}_n) = \mathbb{R}^n$; $E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ ...
5
votes
0answers
87 views

Intersections of the B-orbits and the orbits of some other Borel subgroups in the flag variety G/B

This is a follow-up of this previous question below: Intersections of $B$ and $B^-$ orbits in the flag variety $G/B$ Let $G = SL_n(\mathbb{C})$, $B$ be the standard Borel subgroup, and consider some ...
2
votes
1answer
109 views

Existence of Steiner system designs given $n,k,t$

I am familiar with the recent Keevash paper here which proves that given some $t,n,k,\lambda$ then provided standard divisibility conditions hold, and $n$ is suitably large, there exists a ...
5
votes
2answers
240 views

Combinatorial designs textbook recommendation

Good evening, I am currently taking a class which has combinatorial designs as the first topic, we are using Peter Cameron's book Designs, Graphs, Codes and their Links which I am finding extremely ...
2
votes
0answers
74 views

Adding a row to a Young Tableau via Novelli-Pak-Stoyanovskii

Let $T_{\lambda}$ be the set of standard young tableaux (SYT) of shape $\lambda_1\geq \lambda_2\cdots\geq \lambda_n$. Now consider pushing a row $\mu$ with $\mu\geq \lambda_1$ onto $Y$ to give shape ...
0
votes
0answers
47 views

Counting words with pattern and majority constraints [on hold]

Problem: I have an alphabet $X$ with $n$ letters (say $n=8$, $X=\{A, B, C, D, E, F, G, H\}$). I'm looking for words with $m$ letters (say $m=8$), with three constraints: a given letter (say $A$) is ...
7
votes
1answer
326 views

Quest for a human proof of a $q-$binomial identity

Let $$f(n,k) = \sum\limits_{j = - k}^k {{{( - 1)}^{k - j}}} \binom{n-j}{k-j}\binom{n+j}{k+j}.$$ Then $f(n,k)=\binom{n}{k}$ because it satisfies $f(n,k)=f(n-1,k)+f(n-1,k-1)$ and the obvious ...
6
votes
1answer
185 views

A variant to the Hadwiger-Nelson problem

Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$. What is $\chi(G)$? (This is a variant of the ...
2
votes
1answer
80 views

Minimal family of k-sets containing all t-sets

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member ...
4
votes
1answer
192 views

The number of monotone full binary trees

Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each ...
8
votes
3answers
261 views

Distinguishing combinatorial maps by their linearizations

Every (not-necessarily invertible) map $f$ from $[n]:=\{1,2,,,,.n\}$ to itself determines a linear map $L_f$ from ${\bf R}^n$ to itself that sends the basis vector $e_k$ to $e_{f(k)}$ for $1 \leq k ...
2
votes
0answers
114 views

Ticket lottery — distributing $n$ tickets among $N$ people fairly

Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > n$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend ...
9
votes
3answers
359 views

Is a distributive lattice planar iff it admits no B3 sublattice?

A finite lattice is planar if it admits a Hasse diagram which is a planar graph (we want the Hasse diagram to be represented in the plane so that the $y$-coordinate of each element respects the ...
3
votes
0answers
65 views

Efficiently computing (plethysm-like?)substitutions of symmetric functions

This is a rather technical question, it arose in connection of some calculations that I need to have better grasp of the question Formal group law over $\mathbb{F}_p$ and my own older one What is ...
2
votes
1answer
77 views

Stirling numbers of the second kind with maximum part size

The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...
5
votes
2answers
141 views

Number of Dyck paths with prescribed number of edges

I am trying to find a formula for the trace of certain matrix. To do that I was forced to determine the number of Dyck paths with prescribed number of edges. By a Dyck path I mean a lattice path from ...
4
votes
1answer
91 views

Countable hypo-hamiltonian graph

If $G = (V,E)$ is a graph, then a $\omega$-path is an injective map $p:\omega\to V$ such that $\{p(k),p(k+1)\}\in E$ for all $k\in \omega$. In a similar fashion, we define a $\mathbb{Z}$-path. Is ...
4
votes
1answer
196 views

Counting couples of square-free polynomials over finite fields

I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$: $$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\ y_2^2=h_2(t) ...
3
votes
2answers
189 views

Picking codewords that are close

I posted this question in http://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back. Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
2
votes
0answers
64 views

Exact growth rate of Longest Increasing Subsequence expectation

Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that ...
3
votes
1answer
209 views

How many hamiltonian paths can be removed from a complete directed graph before it becomes disconnected?

The question started from a problem brought home by a friend's 5th grader: "How many ways you can arrange 5 people sitting around a round table so that the people sitting to the left of any person are ...
0
votes
1answer
49 views

Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties: The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it). $T$ has a ...
3
votes
3answers
77 views

Block error-correcting codes over inhomogeneous alphabets

For $n := (n_1,\dots,n_N) \in \mathbb{N}_{>1}^N$, let $X_n := \prod_{j=1}^N [n_j]$, where as usual $[m] := \{1,\dots,m\}$. Are there any known generic constructions for (Hamming) sphere ...
5
votes
1answer
152 views

English translation of Witt's paper on the Mathieu groups?

Does anyone know of an English (or French) translation of Witt's paper Die 5-fach transitiven Gruppen von Mathieu ? (It's the one in which the Witt design is introduced. Well, I guess.) Here's an ...
2
votes
1answer
92 views

Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as: $$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$ where $f(1, 2)$ denotes the flow through arc $(1, ...
1
vote
0answers
114 views

Counting number of ways to place bags and marbles inside bags so all bags contain an odd number of marbles

There was a famous trick question posed once in math.stackexchange here. The question can be loosely translated to "Is it possible to place nine marbles into four bags so that each bag has an odd ...
6
votes
1answer
189 views

A combinatorial identity generalizing identity (3.111) from Gould's book

I am trying to prove the following identity, which I am sure is correct: $$ \sum_{m=0}^{K}(-1)^m{n \choose m}{(n-m)r-1 \choose n-1}=1, $$ where $K:=\left[n\frac{r-1}{r}\right]$ for some integer $r$, ...
3
votes
1answer
251 views

Number of semi-standard tableau

What is the number of semi-standard tableau (weakly increasing on rows and strictly increasing on columns) for the partition $2n=n+n$ with entries $\{1,2, \cdots ,n\}$ such that each $i$ appears ...
0
votes
1answer
98 views

Number of squares in a grid under certain conditions

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane. $A(n):$ # of squares with vertices on the grid. It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...
3
votes
3answers
338 views

Waring problem for binomial coefficients (generalization of Gauss' Eureka Theorem)

Is there a number k such that every natural number can be written as $\sum_{i=1}^k \binom{a_i}{3}$ for some natural numbers $a_i$'s?
1
vote
0answers
78 views

Occupancy problem with limited capacity and two types of balls [closed]

I am considering the following problem that I suspect to be standard. One has a set of $N$ balls composed of a fraction $\alpha$ of red balls and $(1-\alpha)$ of black balls (we assume $\alpha N$ is ...
3
votes
0answers
205 views

Solving a doubly exponential generating function

I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...
3
votes
0answers
57 views

Where does this identity involving sums of Hankel-like determinants over partitions come from?

For a partition $\lambda=( \lambda_1,\dots,\lambda_n)\vdash n$ with $\lambda_1\ge\dots\ge\lambda_n\ge0$ and any function $f:\mathbb Z\to\mathbb C$, define a Hankel-like $n\times n$ matrix ...
10
votes
0answers
281 views

Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
12
votes
0answers
239 views

Grothendieck on polyhedra over finite fields

In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most singular ...
4
votes
0answers
52 views

Is every planar point set be projections of vertices of a neighborly 4-polytope?

More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ be vertices of a neighborly polytope. This problem comes from a simple ...
5
votes
1answer
91 views

Beraha numbers and zeros of the chromatic polynomial of planar graphs

Question: What is the largest Beraha number known to be an accumulation point of real zeros of the chromatic polynomial of planar graphs? Background: The Beraha numbers $B_n=2+2cos(2\pi/n), ...
1
vote
0answers
110 views

counting how many boxes from a given Young tableau contribute to hook length made out of two YTs

Think of a Young diagram as a collection of rows with numbers of elements $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_d \geq \mu_{d+1}=0$ (and $\mu_k=0$ for $k>d$) and define for $s=(i,j)$ (where $i$ ...
7
votes
0answers
102 views

Dynamics of RSK

There is a way of viewing the RSK correspondence as a map (in fact, bijection) $A \overset{RSK}\longrightarrow \widehat{A}$ from $n\times n$ matrices with entries $\mathbb{N}$ to (weak) reverse plane ...
5
votes
0answers
114 views

LS paths construction

Let $W$ be the Weyl group of a simple Lie algebra $\mathfrak L$, and for a dominant weight $\lambda$ denote by $W_{\lambda}$ the stabilizer of $\lambda$ in $W$. Let $\leq$ be the Bruhat order on ...
3
votes
2answers
191 views

Number of subsum of a given set of integers

I am asking myself for few days the following but I can't find any references, although I am pretty sure this was already studied, because it seems quite natural: Given n integers $(e_i)$ chosen ...
1
vote
1answer
81 views

Rank changes with matrix edits

Assume we have rank $r$ real matrix $M\in\{0,1\}^{n\times n}$ (not constrained to symmetric). Assume $W\in\{0,1\}^{n\times n}$ is rank $1$ real matrix. Case $1$: $M+W\in\{0,1\}^{n\times n}$. Could ...
1
vote
1answer
63 views

Complex lines arrangements from a given wiring diagram

I'm working on some presentation of the fundamental group of the complement of a complex lines arrangement in $\mathbb{C}^{2}.$ In particular, in Arvola's article "The fundamental group of the ...
3
votes
1answer
92 views

Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...
0
votes
0answers
64 views

Decomposing matrices to lower ranks

Given real matrix $M\in\{0,1\}^{n\times n}$ of rank $r$. How many $M_i\in\{0,1\}^{n\times n}$ of rank $s$ does one need to write $M'=\sum_{i=1}^ta_iM_i$ for some $a_i\in\Bbb R$ where maximum absolute ...
3
votes
1answer
118 views

How many expressions can be formed with $k$ commutative and associative functions?

This is a generalization of a question I posted to Math.SE here. Suppose we have $k$ binary functions $f_1, f_2, \ldots, f_k$, all of which are commutative and associative, and $n$ indeterminates ...
16
votes
1answer
426 views

A congruence involving binomial coefficients

The following open problem was shown to me by Maxim Kontsevich. I state it in a different but equivalent form. Let $a(n)$ be the sequence at http://oeis.org/A131868, that is, $$ a(n) ...
3
votes
1answer
100 views

Enumerating matrices function of ranks

Is there an expression/approximate expression for number of real matrices $M\in\{0,1\}^{n\times n}$ of rank $r\leq n$? Is it known if $M$ is restricted to symmetric/skew-symmetric matrices?