**3**

votes

**1**answer

79 views

### A follow up question to: Number of walks on integer lattice with self-edge at zero

Let $a(n)$ be the number of lattice paths in ${\mathbb{Z}^2}$ of length $n$ which start at the origin $(0,0)$ and end up at $(n,0)$ and have only up-steps $U:(i,j) \to (i + 1,j + 1)$, down-steps $D:(...

**1**

vote

**1**answer

52 views

### Hyperplane generic to a given arrangement

At the moment, I am reading the paper "on the connectivity of the realization spaces of line arrangements" of Nazir and Yoshinaga.
I would like to extend their Lemma 3.2 to higher dimension. However, ...

**3**

votes

**2**answers

148 views

### Combinatorial interpretation for coefficients of reciprocal of power series

I've seen a number of combinatorial interpretations for the coefficients of the compositional inverse (aka reversion) of a power series. Is there a known combinatorial interpretation for the ...

**8**

votes

**3**answers

707 views

### Zero sum of binomial coefficients

Is there a function $p:\mathbb N\to \{ 1,-1 \} $ and a fixed $N\in \mathbb N$ such that for every $n \geq N$ we get:
$\sum _{i=0} ^{n} p(i)\binom {n}{i}=0$
?
Obviously $p(i)=(-1)^i$ works for $N=1$...

**0**

votes

**0**answers

606 views

### Probabilistic Modeling Parameters Request

Before posing the question itself, it is indispensable to give the definition from which it arises. First of all, let us restrict our attention to the vectors $\overrightarrow{x} = (x_{1},x_{2},\ldots,...

**0**

votes

**0**answers

84 views

### Number Theory Characterization Problem

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, let us associate to it the set $S_{N} = \bigcup_{j=1}^{n}\{(a_{j},j)\}$. We're going to define a d-self-contained number as any natural number ...

**1**

vote

**1**answer

93 views

### estimating binomial coefficients

There is a beautiful paper on the arXiv by Andrew Suk containing an asymptotic result about the Erdös-Szekeres convex polygon problem. I am struggling with one of the estimates he makes on page 4. He ...

**2**

votes

**1**answer

63 views

### An inequality on partitions into distinct bounded parts

Let $P(n,m)$ denote the set of all positive integer partitions of $n$ into parts that are pairwise distinct and bounded by $m$. Let $p(n,m) = |P(n,m)|$.
After some numerical experiments it appears
$...

**75**

votes

**51**answers

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

**3**

votes

**2**answers

95 views

### How many cuts are required for a weighted-proportional cake-cutting?

In proportional cake-cutting, there are $n$ agents with equal entitlements to a "cake" (an interval). Each agent $i$ has a nonatomic value measure $V_i$ over the cake, and it is required to create a ...

**0**

votes

**1**answer

77 views

### Exact formula for computing n-step transition probability of random walks with self-transitions

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...

**8**

votes

**1**answer

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

**0**

votes

**0**answers

88 views

### graduate study in graph theory and combinatorics in canada [on hold]

I'm looking for any graduate programs related to graph theory or combinatorics in canada like in waterloo or simon fraser universities. any other suggestions?

**1**

vote

**1**answer

105 views

### Convexity of truncated expectation

Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$.
Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable ...

**8**

votes

**1**answer

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

**0**

votes

**2**answers

41 views

### Make multiple batches of maximum size, different sized objects

I am a software developer with a rather simple problem. I don't really know how to express it in mathematical terms - I'll just try to write it down:
I have multiple different files... let's say 20 ...

**3**

votes

**1**answer

95 views

### Catalogs/numbers/constructions of non-isomorphic conference matrices

I am interested in complete catalogs of non-isomorphic conference matrices, similar to those of Hadamard matrices. Do such catalogs exist? If yes, then where could they be found, and what is an ...

**2**

votes

**0**answers

61 views

### On the size of residue class

Let $n \in \mathbb{N}$ be a odd number. Let $S \subseteq \{1,3,5,7,...,n-2,n\}$ and $|S|$ is even number. Let $R_i^k=\{a \mid a \in S \text{ } \&\text{ } a\equiv i \text{ }(mod \text{ } k)\}$ ...

**4**

votes

**1**answer

178 views

### Number of walks on integer lattice with self-edge at zero

Consider the graph with vertices $V=\mathbb Z$ and edges
$$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$
that is,
the usual integer lattice with a self-edge at zero.
For some fixed parameters $a,b,n\in\...

**1**

vote

**1**answer

104 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

**4**

votes

**1**answer

229 views

### A variant of bin-and-ball problem

We have $n$ balls, each belonging to a group (e.g, color). There are $g$ groups ($g$ may be large but $g=o(n)$). We sequentially put the balls into $m$ bins in the following way: for each ball, we ...

**1**

vote

**0**answers

57 views

### A two variable recurrence relation with conditionals

I have arrived at the combinatorial problem of enumerating certain types of ballot paths. This has led to analyzing the sequence defined by the following recurrence
$$
f(n,m) = \begin{cases} f(n, \...

**8**

votes

**3**answers

520 views

### Is there a 2-connected k-regular graph without Hamiltonian path?

In this paper (Construction 2.6 p860) the authors have built examples of
connected $k$-regular graph without Hamiltonian path, but with a cut-vertex (i.e. it is not $2$-connected).
Question: Is ...

**2**

votes

**0**answers

136 views

### Card Game Feasibility 2

We play the following card game:
We are given a deck of $M$ unique cards, each with a color $c\in\left\{ 1,\dots,C\right\}$ , and a number $d\in\left\{ 1,\dots,D\right\}$, so $M=CD$.
We wish to ...

**8**

votes

**1**answer

73 views

### Schur positivity on 2 letter alphabets implies Schur-positivity on n letters?

Suppose we have a symmetric polynomial $P$ in $n$ variables.
We can partition this alphabet into sets with one or two letters, e.g. ${ {x_1}, {x_2, x_3}}.
We can thus see $P$ as an element in $Q[x_1]...

**21**

votes

**5**answers

1k views

### For which $n$ is there a permutation such that the sum of any two adjacent elements is a prime?

For which $n$ is it possible to find a permutation of the numbers from $1$ to $n$ such that the sum of any two adjacent elements of the permutation is a prime?
For example: For $n=4$ the permutation $...

**11**

votes

**2**answers

2k views

### Subdivision of triangles into congruent triangles

Recently some old notes of mine have gotten me to thinking about the problem of subdividing a triangle into $N$ smaller triangles, all congruent to one another. A little thought shows the following ...

**1**

vote

**1**answer

342 views

### Doing graph theory after a thesis in pure mathematics [closed]

I've just went through the 1st year of my PhD in France, it is related to Floer Homology. I didn't know what it was really about at that time, I chosed this subject because I thought it would combine ...

**8**

votes

**0**answers

649 views

### Path connected set of matrices?

Consider the collection of $n$ by $n$ matrices
$$S=\{ A: A_{ij}\le0,\quad (-1)^{c_i}\det A(P_i;Q_i)<0 \quad \text{for} \quad i=1,\ldots, k\}$$
where $c_i\in \{0,1\}$, $P_i$ and $Q_i$ are disjoint ...

**0**

votes

**1**answer

73 views

### Choosing directed subgraph in a triangulation

Consider triangulation $T.$
Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...

**3**

votes

**1**answer

77 views

### Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...

**3**

votes

**2**answers

269 views

### Create a graph with a specified number of spanning trees

I read that one of the current challenging problems in mathematics is constructing a minimal graph with a specified number of spanning trees (say, $k$).
However, is there a quick way to create some ...

**1**

vote

**1**answer

155 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...

**3**

votes

**2**answers

112 views

### Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...

**8**

votes

**0**answers

247 views

### What is intuition behind sets with more sums than differences?

There exist finite sets $A$ in, say, $\mathbb{Z}$, such that $|A+A|>|A-A|$. The minimal such set contains 8 elements and consists of, say, 0, 2, 3, 4, 7, 11, 12, 14. How should I find such an ...

**10**

votes

**7**answers

1k views

### Where on the internet I can find database of graphs?

I am studying graph algorithms.
I need database of graphs on which I can test my algorithms.
Where can I find reliable database of graphs of all kinds?
Thanks!

**1**

vote

**1**answer

239 views

### Some divisibility constraints in Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...

**4**

votes

**1**answer

117 views

### Sum of Young symmetrisers of a given shape

Preliminaries and notation:
Let $n\in \mathbb{Z}_{>0}$ and $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_s)\vdash n$ be a partition. Given a Young diagram of shape $\lambda$, we can associate it ...

**4**

votes

**0**answers

171 views

### Enumerating a class of polynomials

How many equivalence classes of $\Bbb F_2[x,y]$ polynomials with $x$ degree $n_x$ and $y$ degree $n_y$ are there such that each $y^i$ coefficient (polynomial in $\Bbb Z[x]$) is distinct and $x^i$ ...

**3**

votes

**1**answer

133 views

### Stirling numbers of the second kind with maximum part size

The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...

**1**

vote

**1**answer

41 views

### How to generate a Latin square $M'$ in the same main class as $M \in \mathrm{LS}(9)$ which agrees with $L$ in the most cells?

I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i \...

**3**

votes

**1**answer

148 views

### Collecting stones in n buckets

There are $n$ stones distributed in $n$ buckets (initially one stone in each bucket). At each step the content of each bucket is put in a random bucket, chosen independently out of a set of $n$ new ...

**19**

votes

**1**answer

1k 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}$, ...

**12**

votes

**0**answers

450 views

### Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers

Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...

**3**

votes

**1**answer

114 views

### Choosing $K$ “centers” from the space of permutations

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations $\pi_1,\...

**1**

vote

**0**answers

31 views

### Possible configurations of NR red balls and NB blue balls on a circle of L sites with D doubly occupied sites and B bonds (occupied nearest neighbors) [closed]

I am a physicist working on metal-insulator transition in crystalline materials due to Coulomb interaction between their electrons (with both spins up and down) depending whether they occupy the same ...

**3**

votes

**1**answer

241 views

### Comparison nauty vs. bliss of canonical form of bipartite graphs

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are
the 600-cell with 120 vertices and 600 facets (...

**1**

vote

**1**answer

196 views

### Simplify a equation

I have a problem simplifying the summation here:
$$
\sum_{x=0}^{n}\sum_{y=0}^{x} {n\choose{x}} {x\choose{y}} y!(x-y)!
$$
The last three terms can be simplified to x!, so the current summation ...

**5**

votes

**1**answer

290 views

### Paley graphs over $p^{2}$ vertices

I have proved that every Paley graph $P(p^{2})$ over $p^{2}$ vertices, where $p\geq 5$ is a prime number has a cospectral mate, i.e. for every prime number $p\geq 5$ there exists a graph $\Gamma_{p}$ ...

**2**

votes

**0**answers

57 views

### Effective “almost enumeration” of monotone boolean functions

Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$.
Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that:
1) $k = \log |\...