**4**

votes

**2**answers

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

**0**

votes

**1**answer

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

**10**

votes

**5**answers

2k views

### Simple/efficient representation of Stirling numbers of the first kind

Stirling numbers of the second kind can be expressed by means of a simple hypergeometric (considering $n$ fixed) sum
$$S_2(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n. \qquad (1)$$
...

**18**

votes

**7**answers

2k views

### undecidable sentences of first-order arithmetic whose truth values are unknown

Godel's undecidable sentences in first-order arithmetic were guaranteed to be true, by construction. But are there examples of specific sentences known to be undecidable in first-order arithmetic ...

**3**

votes

**0**answers

46 views

### A lower bound for orthogonal partial circulant matrices

Let us call an $m$ by $n$ matrix with $m<n$ a partial circulant matrix it is the first $m$ rows of some square circulant matrix.
Consider partial circulant matrices whose elements are either $-1$ ...

**12**

votes

**2**answers

262 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

**0**answers

24 views

### Current 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

110 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

**3**answers

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

**13**

votes

**2**answers

861 views

### A question about certain sets of permutations of the ordered pairs $(1,1),(1,2),\cdots,(1,n),\cdots,(n,1),(n,2),\cdots,(n,n)$

Let $n>1$ be a given positive integer. For any $0\leq k\leq n^2$, let $A_k$ be the set of permutations $((i_1,j_1),(i_2,j_2),\cdots,(i_{n^2},j_{n^2}))$ of the ordered pairs ...

**5**

votes

**3**answers

305 views

### Random RSK and Plancherel Measure

Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this ...

**3**

votes

**1**answer

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

**23**

votes

**5**answers

21k views

### How large is TREE(3)?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...

**53**

votes

**46**answers

7k views

### Important formulas in Combinatorics

Motivation:
The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...

**0**

votes

**0**answers

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

**4**

votes

**1**answer

99 views

### Are all marked order polytopes normal?

Richard Stanley showed that order polytopes have a unimoudlar triangulation.
In particular, this implies that they are integrally closed/normal.
One can generalize order polytopes to marked order ...

**-4**

votes

**0**answers

105 views

### Are polls good approximations [on hold]

Let $X$ be a finite set and $A\subseteq X$ and $m$ be a natural number satisfying $m\le |X|$ and $\epsilon$ be a small positive number.
I'm interested to know if one selects a random $Y\subseteq X$ ...

**4**

votes

**0**answers

108 views

### A generalization of coupon collector problem - $\geq1$ pick per experiment

Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back.
$N=1$ is standard coupon ...

**2**

votes

**0**answers

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

**23**

votes

**1**answer

1k views

### Order of products of elements in symmetric groups

Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying
$1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$
whose product has order ...

**30**

votes

**14**answers

4k views

### What does the generating function $x/(1 - e^{-x})$ count?

Let $x$ be a formal (or small, since the function is analytic) variable, and consider the power series
$$ A(x) = \frac{x}{1 - e^{-x}} = \sum_{m=0}^\infty \left( -\sum_{n=1}^\infty ...

**4**

votes

**1**answer

306 views

### global sections of structure sheaf on the toric Calabi-Yau

Let P be a lattice polytope and lying in $ N \times {1} \subset N \times \mathbb{R}$. Let $\sigma$ be the cone over this polytope and $X_\sigma$ be the corresponding toric variety, which is an ...

**1**

vote

**1**answer

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

**7**

votes

**2**answers

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

**11**

votes

**1**answer

296 views

### No limit shape for random Young diagrams under z-measure?

In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that:
An important difference between the Plancherel measures and ...

**3**

votes

**1**answer

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

**23**

votes

**0**answers

539 views

+100

### partition of infinite word onto permitted words

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, ...

**0**

votes

**1**answer

321 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**0**

votes

**1**answer

209 views

### The weighting function for the infinite product of necklaces

Let us consider the limit $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$ where $N(n,a)$ is the number of fixed necklaces of length $n$ composed of $a$ types of beads.
Let's rewrite the product in a way ...

**14**

votes

**0**answers

639 views

### What is the best lower bound for 3-sunflowers?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such ...

**29**

votes

**2**answers

866 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):
...

**59**

votes

**10**answers

7k views

### Why do Bernoulli numbers arise everywhere?

I have seen Bernoulli numbers many times, and sometimes very surprisingly. They appear in my textbook on complex analysis, in algebraic topology, and of course, number theory. Things like the criteria ...

**10**

votes

**1**answer

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

**6**

votes

**1**answer

466 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**5**

votes

**1**answer

469 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**-2**

votes

**1**answer

470 views

### Conjugate vertices and distinguishing properties

Motivation (added)
A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$.
A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by ...

**6**

votes

**0**answers

137 views

### Nonattacking configurations of k bishops on an m by n rectangular board

The number of ways to place k bishops in a nonattacking configuration on an n by n square board is a well known result and can for example be found in ...

**1**

vote

**0**answers

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

**-2**

votes

**0**answers

116 views

### Flower Arrangements [closed]

We have a $n\times m$ grid with $k$ flowers (not necessarily distinct). The grid is assumed to have horizontal and vertical symmetry. What is the value of $A(n,m,k)$, where $A(n,m,k)$ is the number of ...

**16**

votes

**0**answers

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

**4**

votes

**0**answers

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

**-2**

votes

**1**answer

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

**5**

votes

**1**answer

383 views

### Is the face poset a Heyting algebra?

Is the face poset of a simplicial or nice enough cellular complex a Heyting algebra in some natural way?
Edited to add: For the benefit of illustration, here's a few face posets:
the boundary of a ...

**5**

votes

**0**answers

161 views

### Congruences involving binary forms and primes of the form $x^2+y^2$

Let $a_s$ be
\begin{align*}
a_s=\sum_{k=0}^s{s+k\choose k}2^k,
\end{align*}
which is the coefficient of $x^s$ in
\begin{align*}
\frac{3-\sqrt{1-8x}}{2(x+1)\sqrt{1-8x}}.
\end{align*}
( see ...

**6**

votes

**0**answers

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

**10**

votes

**1**answer

218 views

### Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...

**0**

votes

**0**answers

74 views

### A simplicial complex which is collapsible but there exist a subdivision of it does not [closed]

Does anyone know a simplicial complex which is collapsible but there exist a subdivision of it which does not?

**8**

votes

**3**answers

602 views

### Arithmetic product of symmetric functions: why is it integral?

For every commutative ring $A$, let $\mathbf{Symm}_A$ be the ring of symmetric functions over $A$. Let $\mathbf{Symm}$ without a subscript denote $\mathbf{Symm}_{\mathbb{Z}}$.
We can define a ...

**14**

votes

**8**answers

51k views

### The factorial of -1, -2, -3, …

Well, n! is for integer n < 0 not defined -- as yet.
So the question is: How could a sensible generalization of the factorial for negative integers look like?
Clearly a good generalization should ...

**1**

vote

**1**answer

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