**1**

vote

**1**answer

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

**5**

votes

**2**answers

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

**2**

votes

**2**answers

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

**9**

votes

**3**answers

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

**4**

votes

**0**answers

268 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

**1**answer

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

**7**

votes

**0**answers

147 views

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

**0**answers

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

**2**

votes

**2**answers

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

**5**

votes

**1**answer

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

**3**

votes

**1**answer

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

**4**

votes

**0**answers

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

**1**

vote

**0**answers

39 views

### Composition law in the colored operad whose algebras are (symmetric) operads

In Berger-Moerdijk, Resolution of coloured operads and rectification of homotopy algebras (1.5.6) there is a description of the operad, whose algebras are non-colored symmetric operads.
I have some ...

**2**

votes

**0**answers

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

**14**

votes

**2**answers

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

**69**

votes

**48**answers

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

**18**

votes

**0**answers

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

**16**

votes

**1**answer

251 views

### Maximal number of subsets in $\{1,\dots,n\}$ such that neither is contained in a union of two others

What are known estimates for maximal $M$ for which their exists subsets $A_1,\dots,A_M$ in $\{1,\dots,n\}$ such that there do not exist different indexes $i,j,k$ for which $A_i\subset A_j\cup A_k$?
...

**25**

votes

**5**answers

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

**6**

votes

**1**answer

401 views

### Is every polynomial a factor of a trinomial?

We say that $T(X) \in \mathbb{Q}[X]$ is a trinomial if there exist $A,B,C \in \mathbb{Q}$ such that $T(X) = AX^n + BX^m + C$ for some $n \geq m \in \mathbb{N}$.
Is it true that for each ...

**0**

votes

**0**answers

58 views

### Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
...

**4**

votes

**0**answers

61 views

### shifted symmetric power sums

The functions $p^*_k(x)=\sum_{i=1}^N ((x_i-i)^k-(-i)^k)$ are analogues of power sum symmetric functions, called shifted symmetric by Okounkov and Olshanski. Define ...

**12**

votes

**1**answer

434 views

### Maximal Number of Pairs of Orthogonal vectors in a set of $n$ vectors in $\mathbb{R}^3$

Suppose you are given a set of $n$ non-zero vectors in $\mathbb{R}^3$. What is the maximum number of pairs of them that are orthogonal? The current guess is $\le 2n$.
EDIT: I forgot to add that no ...

**2**

votes

**0**answers

91 views

### What kinds of complexes can be collapsed to?

A simplicial complex $S$ is collapsible if there is a sequence of elementary collapses that bring $S$ down to a single point; I'll denote this as $S \searrow \{pt\}$. I am wondering about a similar ...

**5**

votes

**0**answers

131 views

### Minimal possible cardinality of a $(a_1, …, a_k)$-distributable multiset

Suppose we have a multiset $M$ of positive rational numbers. Sum of $M$ equals $1$. We'll call this multiset $n$-distributable for some $n\in \mathbb{N}$, if there exists a partition $M_1 \sqcup ... ...

**2**

votes

**0**answers

162 views

### Words with Local plus Global Constraints

While doing estimates on the complexity of an algorithm I have run into a word-combinatorial problem with both a local and a global constraint.
This seems to be a rather general situation and I'm ...

**4**

votes

**2**answers

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

**5**

votes

**0**answers

82 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**3**

votes

**0**answers

145 views

### How distributive are the bad Laver tables?

Suppose that $n\in\omega\setminus\{0\}$. Then define $(S_{n},*)$ to be the algebra where $S_{n}=\{1,...,n\}$ and $*$ is the unique operation on $S_{n}$ where
$n*x=x$
$x*1=x+1\,\text{mod}\, n$ and
if ...

**0**

votes

**1**answer

85 views

### Forbidden Tripartite Graphs

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...

**1**

vote

**0**answers

16 views

### Properties of Optimal k-Tour Spanners

Let the edge set of a Optimal k-Tour Spanner of a graph $G$ be equal to the edges of $G$ that lie on at least one optimal tour through exactly $3<k<n$ distinct vertices of $G$.
I would like ...

**10**

votes

**3**answers

505 views

### Self-Similar Graphs

Many fractals can be generated using and infinite sequence of graphs. For example, Sierpinski's Gasket could be generated by the following sequence of graphs.
Many definitions of fractal dimensions ...

**5**

votes

**2**answers

435 views

### What is the permutation group generated by those three given morphisms of the affine space $\mathbb{F}_q^3$?

Let $\mathbb{A}^3 = \mathbb{F}_q^3$. Consider the following three functions $\mathbb{A}^3\to\mathbb{A}^3$:
\begin{eqnarray*}
h: (x, y, z) &\mapsto& (x, y, xy - z) \\
u: (x, y, z) ...

**18**

votes

**1**answer

451 views

### Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...

**0**

votes

**0**answers

64 views

### Is there a general theory for the structure of the (semi)group generated by morphisms of an affine space $F_p^3$?

Consider an affine space $\mathbb{F}_p^3$, and assume we have a handful of morphisms $f_i : \mathbb{F}_p^3 \rightarrow \mathbb{F}_p^3$ given by $$f_i(x, y, z) =(P_i(x, y, z), Q_i(x, y, z), R_i(x, y, ...

**2**

votes

**0**answers

30 views

### s-arc transitivity and the Moore bound

Given a vertex $x$ of a graph, call the subgraph induced by all vertices of distance $\le n$ from $x$ the $n$-neighbourhood of $x$, denoted $N_n(x)$.
Let $G$ be a regular graph of diameter $n+1$. For ...

**4**

votes

**0**answers

71 views

### Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...

**13**

votes

**2**answers

1k views

### Is there a $q$-L'Hospital's Rule?

Let $\binom{n}{j}_q$ be a $q$-binomial coefficient and $(x;q)_n = (1-x)(1-qx)\cdots(1-q^{n-1}x).$
Consider the sum $$f(n,m,r,k)= \sum\limits_{j = 0}^{2n} {( - 1)}^{ j}q^{mj^2+rj}
...

**5**

votes

**1**answer

310 views

### Terminology in combinatorics

I met the following two combinatorial concepts during a study outside of combinatorics. I am wondering if there are common terminologies in combinatorics.
A finite graph $G$ has the following ...

**5**

votes

**2**answers

238 views

### Does the ring generated by the odd power sum symmetric functions have a name?

Let $\Lambda$ be the ring of symmetric functions and recall the power sum symmetric function $p_i = \sum x_1^i + x_2^i + \dots$ generate this ring. Let $\tilde\Lambda$ be the ring generated by the odd ...

**7**

votes

**0**answers

214 views

### Pattern Avoidance in Poset Permutations

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it.
A permutation on a ...

**5**

votes

**1**answer

102 views

### Matroids similar to the cycle matroid

Let $G=(V,E)$ be a graph (loops and multiple edges are permitted). Three following systems of dependent sets in $E$ define matroids:
1) Set $A\subset E$ is dependent if $A$ contains cycle. This is a ...

**9**

votes

**1**answer

414 views

### Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...

**-2**

votes

**1**answer

109 views

### Recursion, Common Term, Combinatorics [closed]

May we find the common term for recursive sequence? if yes that how to find the common term of recursive sequence such: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 ...
in a ...

**2**

votes

**0**answers

64 views

### A specific class of $(0,1)$-matrices

Let $T_n$ be the class of $(0,1)$-matrices of order n with no row sum equal to a column sum. Is there any name or research about this kind of matrix?
For any $A\in T_n$, let $S_A$ be the sum of all ...

**6**

votes

**1**answer

109 views

### Asymptotics of a Bivariate Generating Function

I have the following generating function,
$$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$
and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ ...

**1**

vote

**1**answer

144 views

### How do powers affect asymptotics in generating functions?

Let $a_n$ be a sequence of non-negative real numbers, and $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ its exponential generating function. Also, suppose $B(x) = \sum_{n=0}^{\infty} b_n ...

**0**

votes

**1**answer

137 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**1**

vote

**0**answers

155 views

### Probability of correlated residues

Given $N,c\in\Bbb N$, where $c\ll(\log N)^{1/b}$ for any $b>1$ is fixed, what is the probability that given $A_1,A_2,A_3\in\Bbb N$ with ...

**4**

votes

**1**answer

156 views

### Number of bases of a matroid

I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.