**51**

votes

**39**answers

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

**-2**

votes

**1**answer

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

**27**

votes

**3**answers

629 views

### The coupon collector's earworm

I thank Nicolas Dupont for the following question
(and for permission to disseminate it further):
I have a playlist with, say, $N$ pieces of music.
While using the shuffle option (each such ...

**6**

votes

**0**answers

133 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

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

**8**

votes

**0**answers

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

**-2**

votes

**0**answers

103 views

### Flower Arrangements [on hold]

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

**12**

votes

**1**answer

749 views

+100

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

**15**

votes

**0**answers

438 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

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

**11**

votes

**1**answer

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

**-2**

votes

**1**answer

162 views

### patitions of the number n [on hold]

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

382 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

137 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

74 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

68 views

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

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

**8**

votes

**3**answers

600 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

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

**3**

votes

**1**answer

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

**5**

votes

**2**answers

182 views

### Dickson/determinant type polynomial (updated)

For $2\leq \ell \leq k$, consider the polynomial \begin{equation} P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)\in \mathbb{F}_2[x_1,\ldots, x_k] \end{equation}
...

**7**

votes

**0**answers

121 views

+50

### Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously but despite asking on math.se and offering a bounty, no progress has been made.
For a given positive integer $n$, consider all ...

**1**

vote

**1**answer

63 views

### Maximum size of a union of incomparable chains

The following question was asked on math.stackexchange, where it received no answers.
http://math.stackexchange.com/questions/1392669/maximum-size-of-a-union-of-incomparable-chains
Let ...

**3**

votes

**0**answers

217 views

### Existence of a block design

Let $\ell$ be an integer parameter. I want to ask the existence of the following design: There is a universal constant $\beta < 1$ such that for all sufficiently large $\ell$, the following holds:
...

**2**

votes

**2**answers

86 views

### Relation between number of non-negative and positive integers points in simplices

I asked this question on math.SE before, but did get not get an answer. Therefore I hope it is ok to post it here on this site..
Let $q \in \mathbb{R}_+$ and $0 < w_1 \leq w_2 \leq \ldots w_d \in ...

**1**

vote

**1**answer

91 views

### Number of binary sequences in which the number of $(1, 1)$ and $(0, 0)$ is prespecified

Consider a binary sequence $\mathbf{a}_n$ consisting of 1s and 0s.
Let us denote by $f(\mathbf{a}_n)$ the number of $(1, 1)$ and $(0, 0)$ in $\mathbf{a}_n$; I am not sure whether there is a formal ...

**2**

votes

**0**answers

77 views

### Combinatorial interpretation for a toric intersection number

Let $X$ be an $n$-dimensional toric variety and let $D$ be an effective divisor (eg nef or ample). Is there a combinatorial interpretation (eg in terms of the fan or polytope) of the intersection ...

**43**

votes

**6**answers

3k views

### How to recognise that the polynomial method might work

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let ...

**0**

votes

**0**answers

32 views

### Maximum norm of discrete Fourier transform [duplicate]

I have considerable numerical evidence that
for all $0\leq k\leq{{n-1}\over 2}$ ($n$ odd) there exists a subset $
S_k$ of {1,2,...,n} of cardinality $k$
such that the modulus square of ...

**20**

votes

**5**answers

2k views

### The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...

**8**

votes

**3**answers

742 views

### Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, ... algebras?
What I need from that ...

**2**

votes

**1**answer

202 views

### Existence of functions on finite sets with specific propertise

Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, ...

**15**

votes

**3**answers

1k views

### Rhombus tilings with more than three directions

The point of this question is to construct a list of references on the following subject: Fix vectors $v_1$, $v_2$, ..., $v_g$ in $\mathbb{R}^2$, all lying in a half plane in that cyclic order. I am ...

**9**

votes

**3**answers

342 views

### Minimum size of the union of sets

I came accross this combinatorial problem in my computer science research.
You are given a collection of k sets $S_1,...,S_k$ such that for any $i \neq j$, $ \vert S_i \setminus S_j \vert \geq p$ ...

**14**

votes

**0**answers

414 views

### Probability of many overlapping zero inner products on a circle

[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...

**2**

votes

**1**answer

156 views

### Schubert calculus and Pieri's formula

In the lecture notes Grassmannians: the first example of a moduli space. MIT Open Course Ware. page 7:
Are there any formal publications (books/papers) where I can find the formula?

**17**

votes

**0**answers

383 views

### Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief: When does a subset $S$ of the complex $n$th roots of unity have the property that
$$\prod_{\alpha\, \in \,S} (z-\alpha)$$
gives a polynomial in $\mathbb R[z]$ with ...

**10**

votes

**1**answer

632 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**1**

vote

**0**answers

53 views

### Finding all feasible solutions

Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, ...

**4**

votes

**2**answers

162 views

### irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...

**6**

votes

**2**answers

656 views

### Incidence geometry and matrices

Supposing I have a $0/1$ or $\pm1$ matrix $A$ of size $m\times n$, is there a minimum $d$ (that works for every $m\times n$ $A$) such that there exists $m$ lines $r_1,\dots,r_m$, $n$ lines ...

**21**

votes

**5**answers

725 views

### How many rearrangements must fail to alter the value of a sum before you conclude that none do?

This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...

**4**

votes

**1**answer

183 views

### Smoothening a measure, II

There is an almost invisible, but significant difference between the question below and that recently answered by Boris Bukh.
Given a probability measure $\mu$ supported on a finite set ...

**4**

votes

**2**answers

268 views

### Categories of finite objects

In my experience, category theory is very successful at providing powerful machinery to reason about large objects or objects unrestricted in size, for example (logical) models (via accessible ...

**2**

votes

**0**answers

235 views

### A variant frobenius problem

From Sylvester's theorem we know that using only coins of sizes $a,b$, we can change exactly $\frac{(a-1)(b-1)}2$ different big coins up to $(a-1)(b-1)$.
Denote sets ...

**-1**

votes

**0**answers

51 views

### bound on the size of a circuit [closed]

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...

**5**

votes

**1**answer

188 views

### a question on lattice invariants

Let $V$ be an $n$-dimensional vector space and $L$ be a lattice in $V$, i.e. a free $\mathbb{Z}$-module of full rank. Define the following two numbers. Let $\lambda$ be the minimal positive real ...

**7**

votes

**1**answer

616 views

### Combinatorics of lattice walks with forbidden points

If I'm not in error, the number of walks on a 2-dimensional integer lattice of length 2n steps from the origin to a point (x,y) has a nice closed form:
${2n \choose n + (x + y)/2}{2n \choose n + (x - ...

**1**

vote

**2**answers

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

**2**

votes

**1**answer

120 views

### Smoothening a probability measure

Given a probability measure $\mu$ supported on a finite set $S\subset{\mathbb R}^2$, define
$$ f(z):=\max\left\{\frac{\mu(x)+\mu(y)}2\colon \frac{x+y}2=z,\ x,y\in S \right\},
\ z\in{\mathbb ...