The discrete-mathematics tag has no wiki summary.

**2**

votes

**1**answer

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

**2**

votes

**1**answer

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

**6**

votes

**0**answers

735 views

### How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective.
I am interested in the size of ...

**5**

votes

**0**answers

84 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

490 views

### Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at
an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and
$b$ are natural numbers. For example, this set of ...

**5**

votes

**0**answers

756 views

### On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...

**4**

votes

**0**answers

218 views

### Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

124 views

### Citation for subset complement result

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* ...

**3**

votes

**0**answers

120 views

### Are there existing resources on modular-esque recurrence relations?

Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this?
$\begin{align*}
f_{n,k}(x) & ...

**3**

votes

**0**answers

134 views

### A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello,
What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain
$E = \{1,...,n\}$
and a partial function
$f: E^3 \to \{-1, 0, 1\}$
...

**3**

votes

**0**answers

725 views

### Method for variable substitution in multiple summation

I want to ask: is there any general method for variable substitution in multiple summation?
For example in the following equation a new variable $\lambda=n+m-2\mu$ is introduced to transform the LHS ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

405 views

### Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...

**2**

votes

**0**answers

167 views

### Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as
$$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),
$$
where all $c_{ij}<0$ (so that ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

71 views

### Cross-correlation of two functions which are not fixed

I am trying to cross-correlate two functions, but one of which is changing each 'step' of the cross-correlation.
I want to cross-correlate T(f) and ...

**1**

vote

**0**answers

210 views

### Trigonometric semialgebraic conditions for two floors to be unequal [edited]

EDIT: Since posting my original question I have simplified the problem to finding a sufficient condition for $\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$ which is trigonometric ...

**1**

vote

**0**answers

169 views

### recursion formula for odd holonomic function

suppose we have a map
$f:\mathbb{Z}\longrightarrow\mathbb{C}[t^{\pm}]$
with property that $f(i)=-f(-i)$.
The algebra
$\mathcal{T}=\mathbb{C}[t^{\pm}][L^{\pm},M^{\pm}]/[LM=tML]$ acts on $f$ by
...

**1**

vote

**0**answers

429 views

### Zeroes of a tricky function.

I am attempting to show that there does not exist an N past which every open unit interval (k, k+1) -where k is an integer- contains a zero of the following function:
$h(x)=\sum_{n=2}^{[\sqrt(x)]} ...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

143 views

### Lattice basis reductions and finding minimal values

While reading several articles about lattice basis reduction I am left with a few questions.
For one, I came across this piece of text
Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and ...

**0**

votes

**0**answers

131 views

### A good upper bound on the size of k-biclique in random bipartite graphs.

Let $G = (X \cup Y, E)$ be a random bipartite graph, where $X$ and $Y$ are the set of vertices and $E$ the set of edges. I want to find an upper bound of the largest biclique in which exactly $k$ ...

**0**

votes

**0**answers

85 views

### An upperbound related to inductively reducing a set by adding the two least elements

I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:)
Let ...

**0**

votes

**0**answers

207 views

### Partial Recurrence Equation

Hey people
I have the following equation, which I don't manage to solve.
The background of the problem is the clustergrowth of two chemical species, resulting in a final relation I'd like to solve:
...