The discrete-mathematics tag has no usage guidance.

**4**

votes

**1**answer

170 views

### Recursive sequence of binomial random variables

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...

**0**

votes

**0**answers

44 views

### Factorial Sums over Compositions or ``Unlabeled Permutations"

Let $C_n$ denote subset of integer compositions of $n$ and $c=(c_1,c_2,\dots c_n)$
In a divergent sum, the sequence
$$
a_n=\sum_{c\in C_n} \prod_{c_i\in c} c_i!
$$
frequently shows up and one ...

**-4**

votes

**0**answers

63 views

### Proof equation is of O(log(n)) [on hold]

I am following a course of CS and we are getting Big Oh Notation ( discrete math)
We have to proof certain equations are of O(n^2) etc
I can solve easy equations like 3N + 4 and (n +1)^2 = o(n^2).
...

**6**

votes

**1**answer

325 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**2**

votes

**1**answer

618 views

### Probability generating function zero implies random variable is infinite

Let $V$ be a random variable supported on the nonnegative integers (including $\infty$) and $f(x) = \mathbf E x^V$ be the probability generating function. In our model $V$ is the number of visits to ...

**3**

votes

**0**answers

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

**0**

votes

**0**answers

57 views

### Summing up costs over a Markov chain

I apologize in advance if this question is too simplistic to be appropriate for MathOverflow. I have inquired in multiple places but have found little to indicate that this is a previously studied ...

**6**

votes

**1**answer

82 views

### Above/below directed graph on cells of arrangement of lines

This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...

**1**

vote

**0**answers

29 views

### Finding optimal set of permutations [closed]

I have the following data set of a human population. The data set captures households and relationships of the persons living in those households. My problem is how to group the individuals into ...

**3**

votes

**0**answers

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

**3**

votes

**3**answers

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

**8**

votes

**2**answers

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

**10**

votes

**1**answer

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

**7**

votes

**1**answer

786 views

### Integer solution to special system of linear equations

This problem appear in my research, but I am unable to solve it.
There should be an easy argument, but I have not yet found it.
Informal version
An integer $k\geq 2$ is fixed.
We are given a matrix ...

**2**

votes

**0**answers

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

**9**

votes

**1**answer

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

**5**

votes

**0**answers

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

**0**

votes

**1**answer

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

**2**

votes

**1**answer

145 views

### Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...

**5**

votes

**1**answer

155 views

### Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...

**19**

votes

**2**answers

658 views

### Generating random finite groups

I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability ...

**8**

votes

**7**answers

594 views

### Finite-space dynamical systems

This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...

**3**

votes

**0**answers

100 views

### “Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane.
Here is the setup:
Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...

**4**

votes

**1**answer

121 views

### Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...

**3**

votes

**1**answer

64 views

### Choosing k pairs l distance apart from n numbers

I need to choose $k$ pairs of numbers out of first $n$ natural numbers such that the elements in each pair are $l$ distance apart. For example, if $n = 10, k = 3$ and $l = 2$, $\{(1,3),(4,6),(7,9)\}$ ...

**7**

votes

**3**answers

482 views

### Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...

**-4**

votes

**1**answer

135 views

### What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]

Statement
"For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method."
...

**11**

votes

**2**answers

318 views

### The most number of points that realize only $k$ distinct distances

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$
in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances,
$\|p_i-p_j\|$.
Example. For points in the plane ...

**13**

votes

**2**answers

575 views

### Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n).
The restriction on the first type of bit string is that they must have the same ...

**13**

votes

**1**answer

387 views

### Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...

**1**

vote

**1**answer

154 views

### Enumerating Lattice points

Let $A \in \mathbb{R}^{d\times d}$ be an invertible matrix. Consider the set
$$P_d := A\mathbb{Z}^d = \{A x| x \in \mathbb{Z}^d \} \subset \mathbb{R}^d$$.
and
$$ Q_d := [-1,1]^d.$$
I am interest in ...

**1**

vote

**0**answers

62 views

### Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...

**5**

votes

**2**answers

296 views

### Minimum of squared sum minus sum of squares

I know that
$$
\min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2
$$
with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates.
I'm ...

**7**

votes

**1**answer

790 views

### A Question about Palindromic Numbers and System of Arithmetic Progression

Based from Harminc and Sotak's result, www.fq.math.ca/Scanned/36-3/harminc.pdf
We know that under certain condition, an arithmetic progression can contain an infinitely many palindromes.
My question ...

**1**

vote

**0**answers

31 views

### Estimates for derivatives of a positive discrete harmonic function

There is the following estimation (Duffin, Discrete potential theory, Theorem 5):
Let $f$ be a discrete harmonic function in a sphere of radius $R$ with the center $p$, all in $\mathbb Z^3$. Then, if ...

**0**

votes

**1**answer

160 views

### Number of squares in a grid under certain conditions

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane.
$A(n):$ # of squares with vertices on the grid.
It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...

**2**

votes

**0**answers

43 views

### A weaker version of Randell Isotopy Theorem

I am studying a problem in hyperplane arrangement theory related to the homotopy type of the complement manifold of a certain class of hyperplane arrangements.
In a well celebrated paper Richard ...

**1**

vote

**0**answers

42 views

### Simplifying closed form for Meta Operator

I was consider the set of linear operators:
$$O_{a,k} = \frac{f(ax^k) - f(x)}{ax^k - x} $$'
Particularly I am looking for the closed forms of the eigenfunctions of this operator, that is the ...

**19**

votes

**5**answers

838 views

### Three-halves-free words (analogous to square-free)

A square-free word
is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any
consecutive sequence of symbols in the string.
For alphabets of two symbols, the longest square-free ...

**16**

votes

**5**answers

2k views

### Has any attempt been made to classify finite groupoids?

I recently stumbled upon the Mathieu groupoid and I found them fascinating.
It appears as a subset of $S_{13}$ which is not closed under multiplication, but it turns out to be a groupoid with 13 ...

**2**

votes

**1**answer

111 views

### On a problem about $GF(2)^n$

For $A\subseteq {\mathbb F}_2^n$ let
$$
Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}.
$$
I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then
$$
...

**0**

votes

**0**answers

21 views

### On the stability analysis of a discrete difference system with multiplicative noise

If we assume that
\begin{equation*}
\rho \{\phi \otimes \phi+\psi \otimes \psi\}<1
\end{equation*}
where $\rho$ denotes the spectral radius, then can we verify the following inequality holds
...

**5**

votes

**1**answer

346 views

### A set of integers whose factorial can be written as a product of two factorials

I am trying to collect informations concerning the set
$$\mathcal{A}=\left\{n\in\mathbb{N} \mid (\exists k,l\in\{2,3,\dots,n-2\})(n!=k!l!)\right\}.$$
It seems not much is known about the set ...

**10**

votes

**1**answer

153 views

### Optimal shape for stabbing balls in $\mathbb{R}^3$

I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region,
say, within a unit-radius sphere $S$.
I shoot a ray/path through $S$, hoping to ...

**3**

votes

**1**answer

271 views

### Number of semi-standard tableau

What is the number of semi-standard tableau (weakly increasing on rows and strictly increasing on columns) for the partition $2n=n+n$ with entries $\{1,2, \cdots ,n\}$ such that each $i$ appears ...

**2**

votes

**1**answer

95 views

### Complex lines arrangements from a given wiring diagram

I'm working on some presentation of the fundamental group of the complement of a complex lines arrangement in $\mathbb{C}^{2}.$ In particular, in Arvola's article
"The fundamental group of the ...

**3**

votes

**1**answer

148 views

### Braid wiring diagrams and matroids

recently I started reading some articles about the presentation of the fundamental group of lines arrangements in $\mathbb{C}^{2}$ via Wiring diagrams.
I also found some relation with matroid theory. ...

**17**

votes

**1**answer

503 views

### Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...

**2**

votes

**1**answer

232 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**15**

votes

**7**answers

1k views

### Two questions from combinatorics on words

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...