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
vote
0answers
48 views

state-of-the-art graph theory libraries like LEDA

I came across LEDA (library of efficient data types and algorithms) which implements graph theory algorithms: http://www3.cs.stonybrook.edu/~algorith/implement/LEDA/implement.shtml I want to ask: ...
11
votes
1answer
205 views

Who first noticed that Stirling numbers of the second kind count partitions?

When the Stirling numbers of the second kind were introduced by James Stirling in 1730, it was not combinatorially; rather, the numbers ${n \brace k}$ were defined via the polynomial identity $$ x^n = ...
-2
votes
0answers
83 views

Arranging books into bags [on hold]

I'm trying to find an algorithm to answer the following question (informal): given a (finite) set of distinct books of different (positive integer) sizes and a (finite) set of bags of different ...
11
votes
0answers
92 views

When is a group Fibonacci sequence contained in a single conjugacy class?

First a definition: a Fibonacci sequence in a group is a sequence in which the first two elements may be arbitrary, and from there on each element is a product (using the group operation) of the ...
2
votes
0answers
66 views

Lattice model for Affine Grassmannians of non type A

There is a Lattice model for affine Grassmannians of type A, due to Lusztig. It describes affine Grassmannians of type A as the moduli space of certain subspaces in an infinite-dimensional ...
4
votes
1answer
267 views

How to visualise Bollobas' 1965 theorem?

Theorem $[n]=\{1,\ldots,n\}$. Let $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ be such that $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$. Then $$\sum_{i \in I} ...
1
vote
1answer
62 views

Computing row-sum scaled unsigned Stirling nos. of the 1st kind

As the title suggests, I would like to compute probability vectors with elements proportional to (unsigned) Stirling numbers of the first kind by row. For easy reference, here is the Wiki page. For ...
2
votes
0answers
100 views

Semigroup nilpotents and compostional inversion

The integer coefficients of a general partition formula for the compositional inverse of a function are a refined version of the coefficients of the generating series for the number of nilpotents in a ...
2
votes
3answers
158 views
+50

Probability that a sum of intependent random variables hits a point

Let $X_1,\ldots,X_n$ be independent random elements of a normed space $X$. Suppose that $\sup_{x\in X}\mathbb{P}(X_i=x)=p_i$. What is the best known upper bound for $$\sup_{x\in X} ...
6
votes
2answers
133 views

Are sums of 0-1 Pareto efficient vectors Pareto efficient?

Does there exist an $m \times n$ matrix $A$ and a vector $x \in \mathbb{R}^m$ such that: The entries of $A$ are $\in \{0, 1\}$. For all pairs of columns $u, v$ of $A$ the entries of $u - v$ are ...
3
votes
0answers
136 views

What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...
3
votes
1answer
117 views

When are all sums of the elements of a set different?

Consider a set $S = \{x_1, \dots, x_n\} \subset \mathbb{Q}\setminus\{0\}$ and assume that for any $I, J \subset [n]$ with $I \neq J$ we have that \begin{equation} \sum_{i \in I} x_i \neq \sum_{j \in ...
0
votes
0answers
48 views

K-Permutations with forbidden numbers [on hold]

This question has some references to programming and not as many mathematical terms as you might like, but I think it's more appropriate in a mathematics forum. Introduction (Skip if you are ...
-1
votes
0answers
75 views

Combinatorial Proof Problem [on hold]

I'm having trouble solving this because I'm only familiar with algebraic proofs instead of combinatorial. $$\binom{3n}{3}=n^3+6n\binom{n}{2}+3\binom{n}{3},\quad\text{for }n\ge3.$$
3
votes
2answers
123 views

A problem on chains of squares — can one find an easy combinatorial proof?

Consider the unit square $ S = [0,1] \times [0,1] $. For each $ n \in \mathbb{N} $, we can tessellate $ S $ by the collection $$ A = \left\{ \left[ \frac{i}{n},\frac{i + 1}{n} \right] \times ...
2
votes
0answers
52 views

Number of maximal chains in Bruhat order

Is there a formula for the number of maximal chains between two permutation in the (strong) Bruhat order?
3
votes
1answer
153 views

A number array related to colored necklaces and the primes

I stumbled upon entry OEIS-A208535 on the enumeration of certain kinds of colored necklaces and noticed that the integers for the odd prime rows of the table there seem to be given by the Moreau ...
6
votes
0answers
89 views

What is known about the chromatic number for minimum-distance graphs in higher dimensions?

For a set of points in $\mathbb{R}^d$ with minimum distance $a$, the minimum-distance graph connect two points iff they are at distance $a$. We can also view it as the tangency graph for a set of ...
1
vote
0answers
62 views

Fundamental invariants for root subsystems

Let $\Phi$ be an irreducible root system of rank $\ell$. The fundamental invariants of $\Phi$ is a set of $\ell$ integers $d_1, \cdots, d_\ell$ canonically attached to $\Phi$. Now suppose $\Psi$ is ...
7
votes
0answers
159 views

On the ratio of Gilbreath sequences

Definitions: let $n \in \mathbb{N}_{>0} \cup \{ \infty \}$ and let $E_n$ be the set of sequences $(d_i)_{i=1}^n$ such that $d_1=1$, $d_i$ is an even integer (for $i > 1$) and $0<d_i \le i$. ...
8
votes
3answers
446 views
+50

Separating points in the plane II

Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all ...
5
votes
1answer
392 views

Is fourier analysis necessary to prove this?

I have a couple of inequalities that I want to prove. The proof is easy using fourier analysis but I am wondering whether there is a proof that does not use fourier analysis. 1) For any $c, s > ...
0
votes
0answers
43 views

quadratic knacksack problem, state of art [closed]

What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.
0
votes
0answers
39 views

Combining binary numbers [closed]

Assume you have n n-digit binary numbers, for example: ...
0
votes
1answer
101 views

Poisson approximation of random sub-graphs

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...
1
vote
1answer
150 views

A generalisation of Narayana-like numbers (walks on the 2D lattice)

I apologize in advance if this question has a trivial answer. I am pretty sure this kind of problem was already studied and I am mostly asking for good references. Given integers $0 < k \le n+1,$ ...
1
vote
1answer
107 views

Ordinary or Rational Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary or rational generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted ...
12
votes
2answers
273 views

Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...
3
votes
1answer
63 views

Are all marked order polytopes normal?

Richard Stanley showed that order polytopes have a unimodlar ttriangulation. In particular, this implies that they are integrally closed/normal. One can generalize order polytopes to marked order ...
1
vote
1answer
156 views

Name for series $\sum f_n x^n / (n! (n+k)!)$

Let $(f_n)_{n\ge0}$ be a real sequence. Then $\sum f_n {x^n \over n!}$ is called the exponential generating function of $(f_n)$. Let $k\ge0$ be a nonnegative integer. If we add another factorial ...
13
votes
2answers
354 views

What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$

Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...
1
vote
0answers
101 views

current status of combinatorial optimization solvers [closed]

What is the current status of the solvers in combinatorial optimization? For example, what is the "usual feasible size" for a traveller sale's man problem, say, how many nodes and edges are "usually ...
2
votes
2answers
118 views

Choosing subsets to cover larger sets

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ ...
3
votes
1answer
45 views

Average vertex degree in finite Delaunay triangulations in high dimensions

In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6. Does anyone know of a similar result in higher dimension? I ...
2
votes
2answers
83 views

Probability of a contiguous sub-sequence with different elements

Let $a$ and $b$ be two positive integers, and say $b\gg a$. Let $S$ be a random sequence with $ab$ elements, whose entries are all integers from $1$ to $a$, such that each number from $1$ to $a$ ...
8
votes
1answer
307 views

Coloring of the plane

I would like to know the minimum number k such that the plane R^2 can be coloured with k colors such that no colour contain all the possible distances. In other words, a colouring such that each color ...
6
votes
1answer
179 views

Some polytopes in $\mathbb R^n$ whose vertices have coordinates 1, -1 or 0

Let $n$ and $k$ be positive integers with $k\leq n$. Let $P(n,k)$ be the convex hull in $\mathbb R^n$ of the $2^k {n \choose k}$ vectors whose exactly $k$ coordinates belong to $\{\pm 1\}$ all the ...
1
vote
1answer
93 views

Evaluation of the multiple integral [closed]

Would you give me any suggestions or comments on evaluating the following $n$-dimensional integral? $$ \int_{[0,t]^n} h(x) dx $$ where $ x=(x_1 ,x_2 , \cdots, x_n ), h(x)= \prod_{k=1}^n min( ...
2
votes
0answers
44 views

Computing basis of a lower set given basis of complementary upper set

In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest ...
2
votes
0answers
76 views

Counting strings with alternating letters with generating functions

It is a classical problem that of finding the generating function (GF) of the number of strings with length $n$ having $m$ different letters (basically, the problem reduces to that of writing the ...
3
votes
0answers
76 views

Counting Problems where Labeled is Known but Unlabeled is Not

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula. To contrast, counting unlabeled trees is considerably ...
1
vote
3answers
93 views

Is there a formula for the number of labeled forests with $k$ components on $n$ vertices?

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. My question is: Is there a generalization of this formula for forests? Let $f_{n,k}$ denote the number of ...
5
votes
1answer
162 views

How to prove an elementary functional equation for polylogarithms?

Let $Li_s(z)$ denote the usual polylogarithm. The elementary functional equation $$Li_{-n}(z)=(-1)^{n-1}Li_{-n}(1/z)$$ holds for $n\geq 1$. I remember only that the proof used some reproducing ...
4
votes
1answer
211 views

Generalized Cauchy-Binet sum over a fixed subset of indices

I originally posted this on math.stackexchange, but it quickly got buried. I removed it not too long after, thinking of rewriting it for MO, but I didn’t have a chance to post it until now. Apologies ...
4
votes
1answer
495 views

An Intriguing Tapestry: Number triangles, polytopes, Grassmannians, and scattering amplitudes

$$Prelude \;\;on \;\;Two\;\; Threads$$ Last month the workshop New Geometric Structures in Scatering Amplitudes was hosted by CMI with the following partial overview: Recently, remarkable ...
2
votes
0answers
46 views

Counting rooted labelled trees with fixed height AND fixed # of vertices

Consider the set of rooted labeled trees in which each node may have up to $d$ children. It is well known that the number of such trees with $\leq v$ vertices is (approximately) $(ed)^v$ and that the ...
0
votes
0answers
76 views

G-equivariant coherent sheaves on Bott-Samelson Resolutions

Let $G$ be a Lie group, $B$ be a Borel subgroup. $G/B$ is the corresponding flag variety. Let $w$ be an element of the Weyl group $W$ with a reduced expression $w = s_1 \cdots s_n$. Let $X_w$ be ...
2
votes
1answer
95 views

enumeration of connected blocks in finite size square

Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected? By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we ...
1
vote
0answers
100 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
1
vote
1answer
138 views

How to understand a rooting of a dessin d'enfant?

As I understand it, rooted maps on surfaces were first introduced in enumerative combinatorics because they are easier to count than unrooted maps, which can have non-trivial symmetries. A map is a ...