**2**

votes

**0**answers

74 views

### Number of self avoiding paths which are not ``tie together''

Consider the lattice $\mathbb{Z}^d$. Let $A_{n}$ be the set of returning self-avoiding paths (from $0$ to $0$) having length $n$. For any path $\omega \in A_{n}$, let $f(\omega)$ be the number of ...

**3**

votes

**0**answers

111 views

### Generating function of a sequence involving reciprocals of binomial coefficients

Question: Is there a closed-form expression for the following sum
$$
F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1}
$$
where $z\in\mathbb{C}$, and $r$, $k$ are non-negative ...

**20**

votes

**1**answer

409 views

### Bounding Schur symmetric polynomials on the unit circle

Recall the Schur polynomial in $n$ variables, indexed by the partition $\lambda$, with $\ell(\lambda) \leq n$, is given by
\begin{equation}
s_\lambda(x_1,\ldots, x_n) = a_{\lambda + \delta}(x_1, ...

**7**

votes

**4**answers

571 views

### fixed points of permutation groups

As is well-known (see, for example, a nice exposition by our own Qiaochu: https://qchu.wordpress.com/2012/11/07/fixed-points-of-random-permutations/) that the distribution of the number of fixed ...

**3**

votes

**1**answer

242 views

### Connections to physics, geometry, geometric probability theory of Euler's beta integral (function)

Euler"s integral for the beta function $B(s,\alpha) = $ (with $x = 1$)
$$ \frac{(s-1)!(\alpha-1)!}{(s+\alpha-1)!} x^{s+\alpha-1} = \int_0^\infty t^{s-1}\; H(x-t) \; (x-t)^{\alpha-1} dt = \int_0^x ...

**6**

votes

**1**answer

158 views

### q-Integer-valued polynomials

For $n \in \mathbb{Z}_{\geq 0}$, let $[n]_q := (1-q^n)/(1-q) = (1+q+...+q^{n-1})$ as is customary, with $[0]_q=0$.
Let $R$ be the subring of $\mathbb{Q}(q)[x]$ consisting of all $f$ such that ...

**4**

votes

**3**answers

256 views

### Maximum difference between heads and tails in absolute value

I toss a fair coin $n$ times. Some notation:
$S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$.
$M_n=\max(S_1,S_2,\dots,S_n)$,
...

**5**

votes

**1**answer

150 views

### A natural Lascoux-Schützenberger involutions on plane partitions

The Lascoux-Schützenberger involutions, $s_i$, that permute the weight of semi-standard Young tableaux are fairly known.
They satisfy some nice Coxeter relations, for example, if $v$ and $w$ are ...

**2**

votes

**0**answers

52 views

### Will the following construction leads to an counterexample of strong mapping conjecture on realizable oriented matroids?

The strong map conjecture asserts that any strong map $\mathcal{M}_1\rightarrow\mathcal{M}_2$ admit a factorization into an extension followed by a contraction. For which the counterexample has been ...

**5**

votes

**1**answer

159 views

### Determinant of symmetric Latin square

Let $n=2m$ be an even number. Let us construct $n\times n$ symmetric matrices $S_n$ in the following way. The entries are indeterminates $X_1,\ldots,X_{n-1}$. We choose a $1$-factorization of the ...

**2**

votes

**1**answer

100 views

### Combinatorics-the maximum number of subsets with a given property

Let $X$ be a set with $n$ elements. I would like to know the maximum number of subsets of $X$ such that the number of elements in the symmetric difference between any two of these subsets is at most ...

**2**

votes

**0**answers

69 views

### actions of the hyperoctahedral group

I am looking for actions (i.e., permutation representations) of the hyperoctahedral group $H_n$ studied in the literature, i.e., homomorphisms from $H_n$ to $\mathfrak S_X$, the set of bijections from ...

**1**

vote

**0**answers

71 views

### Computing the Edge Chromatic Polynomial of a graph

Is there a recursive formulae to compute the edge chromatic polynomial of a graph?
The following formulae is known for the vertex chromatic polynomial of a grapg $G$
$P(G,x)=P(G-uv, x)- P(G/uv,x)$ ...

**9**

votes

**0**answers

161 views

### Embedding $\beta\mathbb{N}$ into a product of Cantor sets

Let us consider $\beta\mathbb{N}$, the Stone-Czech compactification of the natural numbers (where we do not take $0$ to be a natural number, so the only idempotent elements are nonprincipal ...

**4**

votes

**1**answer

191 views

### Counting trees according to endpoints

Question: Is there a nice (or any) formula for the generating function
$$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$
where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints?
...

**2**

votes

**1**answer

74 views

### distinct multiple points in a space with at least one point lying in a subspace

Let $X$ be a topological space and $A$ a subspace of $X$. Given $k\geq 2$, let the unordered configuration space be
$$
B(X,k)=\{(x_1,x_2,\cdots,x_k)\in X^k\mid x_i\neq x_j \text{ for any } i\neq j\}
...

**5**

votes

**1**answer

161 views

### “Database” of simplicial polytopes/spheres

Reading through various papers on polytopes I have come across really interesting examples of simplical polytopes and non-shellable (or non-PL) simplicial spheres but sometimes it is hard to keep ...

**2**

votes

**0**answers

52 views

### Is there a distance function on Dyck/Tamari words of arbitrary length?

Consider sequences of well-formed parentheses (or up/down sequences) of the type counted by the Catalan numbers. See http://www-math.mit.edu/~rstan/ec/catalan.pdf
These are sometimes called Dyck ...

**6**

votes

**2**answers

247 views

### Is this algebra isomorphic to an incidence algebra?

This question is motivated by trying to establish a converse to Theorem 7.8 of our paper.
I have a finite poset $P$ with the following properties:
$P$ has binary meets (and hence a least element).
...

**-2**

votes

**1**answer

261 views

### Calculating a sum including large numbers [closed]

Let
$\theta(x)=\begin{cases}
0 & \text{ if } x<0 \\
1 & \text{ if } x\ge 0
\end{cases}$
Do you know any way to calculate this number:
...

**3**

votes

**0**answers

53 views

### What is the maximal number of partitions with this maximal intersection property?

Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of ...

**14**

votes

**3**answers

275 views

### Bicoloring of $\mathbb{N}^2$, avoiding set of patterns, is the maximal limit density rational?

Consider a bi-coloring of $\mathbb{N}^2$, (black and white), where we wish to maximize the limit (limsup) of the density of black squares in $[n] \times [n]$ as $n \to \infty$. Here, we identify each ...

**4**

votes

**1**answer

265 views

### Integer solution

For every prime $p$, does there exists integers $x_1$, $x_2$ and $x_3$ ($0\leq x_1, x_2, x_3 \leq \lfloor cp^{1/3}\rfloor$ and $c$ is some large constant) such that $\frac{p-1}{2}-\lfloor 2cp^{1/3} ...

**1**

vote

**0**answers

65 views

### Lp norm estimates for the inverse of the Laplacian on a graph

I am looking at a finite connected graph and I would like to know what is the best [i.e. largest] constant $\lambda_p$ in
$$
\sum_x f(x) =0 \implies \| \Delta^{-1} f\|_{\ell^p} \leq \lambda_p^{-1} ...

**7**

votes

**1**answer

164 views

### “Separated” version of Sauer's lemma on VC classes

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...

**1**

vote

**1**answer

71 views

### Similarity graph for continuous maps between Hausdorff spaces

Let $X, Y$ be topological spaces and $f,g: X\to Y$ continuous. Then we say that $f, g$ are similar if for all $V\subseteq Y$ open we have either
$f^{-1}(V) = g^{-1}(V) = \emptyset$, or
$f^{-1}(V) ...

**2**

votes

**0**answers

38 views

### exchange mappings between equal-sized subsets

We are given universe ${1,...,n}$ and all its $r$-sized subsets.
I want to find a family of bijections $\phi_{A,B}:A\mapsto B$ between every two $r$-sized subsets $A,B$, with the following property:
...

**-1**

votes

**1**answer

174 views

### Number of different factors of given size in primorial

Let $b_n$ be number of bits in product of all primes from $1$ to $n$ which is approximtely $b_n\approx n$.
What is the approximate number of distinct factors with number of bits ...

**13**

votes

**1**answer

324 views

### An introduction to Macdonald polynomials other (better?!) than SFHP

Long story short, I personally find Macdonald's celebrated book Symmetric Functions and Hall Polynomials somewhat difficult to read for various reasons. I also know for a fact that I'm not the only ...

**3**

votes

**2**answers

244 views

### Is the sumset or the sumset of the square set always large?

Let A be a finite subset of $\mathbb{N}$, $\mathbb{R}$, or a sufficiently small subset of $\mathbb{F}_{p}$.
Do we have a lower bound of the form $|A|^{1+\delta}$ on the following quantity:
$$\max ...

**1**

vote

**1**answer

84 views

### Probability of having no cycles of fixed length in $d$-regular graphs

According to this paper, the probability that a random $d$-regular graph of order $n$ has no cycles of length $c_1,c_2,\ldots,c_t$ is $$P=\exp\left(-\sum_{i=1}^t\mu_i+o(1)\right)$$ as ...

**7**

votes

**2**answers

402 views

### The sum of a series, continued

In this question the OP asks whether the sum
$$
f(q, \alpha) = \sum _{k=1}^{\infty } \frac{q^k \left(q^k-1\right)^\alpha}{(q;q)_k}
$$
is ever zero. An experiment with Mathematica indicates, to any ...

**7**

votes

**2**answers

218 views

### Upper bound on length of addition chain

An addition chain for $n$ is a finite sequence of integers starting at 1 and ending at $n$, such that each element is a sum of two previous elements. A short addition chain for $n$ can be used, for ...

**4**

votes

**1**answer

143 views

### Partitioning ${\cal P}([[1,n]])$

In an analysis of the Jacobi method for the computation of the spectrum of a Hermitian matrix, I face the following problem.
Denote ${\cal P}_2(n)$ the set of doubletons $\{a,b\}$ in ...

**3**

votes

**1**answer

96 views

### Method to construct a bipartite graph G' with 2n vertices from a graph G

I have seen mentioned in a talk an operation that takes a graph $G=(V,E)$ and constructs a new bipartite graph $G'=(V',E')$ such that $V' = V\times \{0,1\}$ and $E'=\{((i,1),(j,0)) : (i,j)\in E\} \cup ...

**3**

votes

**3**answers

133 views

### Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form:
$$\sum_{n=1}^k ...

**2**

votes

**0**answers

66 views

### Polynomials with positive coefficients passing through fixed points/range of Vandermonde matrices

I'll give two equivalent statements of the setup, then give my questions.
Fix integers $M \leq N$ and define the Vandermonde-like matrix $V_{M,N}[i,j] = (1 - \frac{i}{M})^{j-1}$ for $i \in ...

**0**

votes

**0**answers

69 views

### Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction
Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for ...

**1**

vote

**1**answer

69 views

### approximate diameter of polytopes in high dimensions

I just came across the following problem:
Let us consider the unit corner of the n-cube
$$
\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 ...

**8**

votes

**2**answers

192 views

### Repeats of all binary strings of length k

The question seems like it should be known, but I was not able to find it anywhere.
How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ ...

**1**

vote

**0**answers

56 views

### Is there an official name for the intersection of the join-irreducible representations of two lattice elements?

Given a lattice provided with a join-irreducible representation of its elements, there is a natural "intersection" operator $A \mathbin{\dot\cap} B$ that returns the join of the setwise intersection ...

**1**

vote

**0**answers

85 views

### What characteristic of a graph depend on the vertex labeling?

Different labeling on a graph produces class of isomorphic graphs. Two isomorphic graphs possess similar characteristic such as connectivity, degree distribution of vertices, equality of spectrum and ...

**18**

votes

**0**answers

559 views

### A Linear Order from AP Calculus

In teaching my calculus students about limits and function domination, we ran into the class of functions
$$\Theta=\{x^\alpha (\ln{x})^\beta\}_{(\alpha,\beta)\in\mathbb{R}^2}$$
Suppose we say that ...

**10**

votes

**1**answer

231 views

### Finding combinatorial models / statistics

In many cases in combinatorics and especially algebraic combinatorics with some representation theory, the main problem is about finding the correct statistic on a mathematical object.
For example, ...

**5**

votes

**0**answers

94 views

### “Edge Density” of Infinite Planar Graphs

Given an infinite planar graph $G$, let's denote by $\{H_1,H_2,\dots,H_m\}$ all the labeled graphs on $n$ vertices that appear as subgraphs of $G$. Also let
$$d_n=\frac{\sum_{i=1}^m \#E(H_i)}{nm}$$
...

**6**

votes

**0**answers

95 views

### Recursions which define polynomials?

Let $k$ be a positive integer and let
$$h(n,k,q)=\frac{1-(1+q^{k})q^{2k(n-1)+1}+q^{2}}{1-q^{2n-1}}h(n-1,k,q)-\frac{(1-q^{k(2n-3)})(1-q^{2k(n-1)})q^2}{(1-q^{2n-1})(1-q^{2n-3})}h(n-2,k,q)$$
with ...

**30**

votes

**2**answers

1k views

### The coupon collector's earworm

[EDITED mostly to report on the answer by Kevin Costello
(and to improve the gp code at the end)]
I thank Nicolas Dupont for the following question
(and for permission to disseminate it further):
...

**12**

votes

**2**answers

289 views

### What is the maximum size of a set system where the intersection of any two incomparable members is not in the set?

Let the set $\mathcal{F}$ consist of subsets of $[n]$. Suppose that for any incomparable $A$ and $B$ in $\mathcal{F}$, we have $A \cap B \notin \mathcal{F}$. What is the largest possible size of ...

**-3**

votes

**1**answer

184 views

### patitions of the number n [closed]

I'm having difficult with the following question :
A. Show that the number of partitions of n where in each one of them the even numbers appears at most once equals to the number of partitions of n ...

**1**

vote

**1**answer

147 views

### Injective subset function

Let $X$ be a non-empty set and let $F: X \to {\cal P}(X)$ be a function with the following property:
for $A \subseteq X$ we have $|A| \leq |\bigcup F(A)|$.
Does this imply that there is an ...