# Tagged Questions

**0**

votes

**0**answers

9 views

### Prove a theorem in combinatorics [on hold]

I want to show that for $k=1,...,(n-1)$ we have :
$\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}$
I have used induction on $k$, but I have not deduced the above relation.

**2**

votes

**1**answer

107 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 ...

**0**

votes

**0**answers

35 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} for n \ge 3.

**0**

votes

**1**answer

153 views

### Maximize combinatorial sum for boolean function

I am trying to maximize the function
$$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$
for a function ...

**1**

vote

**0**answers

32 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
...

**5**

votes

**1**answer

261 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 ...

**0**

votes

**0**answers

39 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?

**6**

votes

**0**answers

84 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 ...

**5**

votes

**0**answers

105 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$. ...

**1**

vote

**0**answers

55 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 ...

**10**

votes

**2**answers

232 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 ...

**1**

vote

**1**answer

148 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,$ ...

**5**

votes

**1**answer

379 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

**0**answers

43 views

### quadratic knacksack problem, state of art [on hold]

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

**0**

votes

**0**answers

73 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 ...

**0**

votes

**0**answers

37 views

**8**

votes

**0**answers

167 views

### An inequality for the ratio of standard Young tableau with {1,2,…,k} in the first row

For a partition $\lambda \vdash n$, define $\dim \lambda$ to be the number of standard Young tableaux of shape $\lambda$, and $\dim \lambda/(k)$ as the number of standard Young tableaux with ...

**4**

votes

**1**answer

484 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 ...

**1**

vote

**1**answer

105 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 ...

**13**

votes

**2**answers

351 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 ...

**5**

votes

**2**answers

4k views

### Number of trees with n nodes and m leaves

Even searching for " 'number of trees' leaves " didn't reveal what I am looking for: an approach for calculating the (approximate) number of trees with exactly n nodes and m leaves. Any hints from MO?
...

**3**

votes

**1**answer

62 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 ...

**4**

votes

**1**answer

208 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 ...

**1**

vote

**1**answer

154 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 ...

**0**

votes

**1**answer

452 views

### A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit

I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version:
Randomly assign (with replacement) $N$ balls to $M$ urns. ...

**2**

votes

**1**answer

188 views

### Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.
In the following all graphs are simple and connected.
Let $G$ be graph with vertex set ...

**11**

votes

**7**answers

2k views

### Cyclotomic Polynomials in Combinatorics

I am searching for a combinatorial significance of cyclotomic polynomials. The only examples I got are a paper by Neville Robbins http://www.emis.de/journals/INTEGERS/papers/a6/a6.pdf and two recent ...

**1**

vote

**0**answers

100 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

**2**answers

116 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$ ...

**8**

votes

**2**answers

3k views

### Generalization of a horse-racing puzzle

A well-known puzzle goes:
"Suppose that you have 25 horses and a racetrack on which you can race up to 5 horses. If the outcome of each race only tells you the relative speeds of the horses in the ...

**22**

votes

**1**answer

1k views

### Permutations of $(Z/pZ)^*$

Let $p$ be a prime integer, and let $(\mathbb Z/p\mathbb Z)^*$ be the set of non-zero elements of $\mathbb Z/p \mathbb Z$.
Denote by $S((\mathbb Z/p \mathbb Z)^*)$ the group of permutations of ...

**25**

votes

**2**answers

789 views

### Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...

**15**

votes

**1**answer

480 views

### 3D generalizations of permutations, RSK correspondence, contingency tables, etc.

I want to gather facts and questions related to 3D generalizations
of permutations, RSK correspondence, contingency tables,
etc. One reason I am interested in this is because it is potentially
related ...

**6**

votes

**1**answer

176 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 ...

**3**

votes

**1**answer

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

**2**answers

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$ ...

**3**

votes

**2**answers

105 views

### Unimodular triangulation and Ehrhart polynomials

Let $P$ be a convex lattice polytope. Then it has a polynomial Ehrhart function.
I am interested in what can be said about the Ehrhart polynomial when
$P$ has any of the properties
is integrally ...

**8**

votes

**1**answer

306 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 ...

**1**

vote

**1**answer

91 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

**0**answers

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

**2**

votes

**0**answers

43 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 ...

**1**

vote

**3**answers

92 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 ...

**3**

votes

**0**answers

74 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

**1**answer

157 views

### Name search for special Linear Integer Program

I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
...

**5**

votes

**1**answer

161 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 ...

**1**

vote

**1**answer

120 views

### maximizing a function involving factorial

Can someone suggest a way to calculate the maximum with respect to $x \ge 1$ of:
$$f(x)=\frac{1}{x!} \frac{1}{1-c^{1/\binom{x+n-1}{n-1}}}.$$
The constants $c$ and $n$ are parameters such that $c \in ...

**1**

vote

**0**answers

99 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.
...

**12**

votes

**2**answers

516 views

### Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product
$$ p=b_1 b_2 \cdots b_n$$
where each $b_i\in A$.
Clearly $n-1$ multiplications suffice to compute $p$; ...

**2**

votes

**0**answers

137 views

### Dissection of a polygon into convex polygons

Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...

**1**

vote

**2**answers

138 views

### Upper bounding number of integer partition by binomial coefficient

Let $n,p \in \mathbb N$ and consider the integer partition of
$$\lfloor \frac{n(p-1)}{2} \rfloor$$
into $p$ or less parts, each of which is less or equal to $n-1$.
Can the number of partitions be ...