The discrete-mathematics tag has no wiki summary.

**6**

votes

**0**answers

716 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

393 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

611 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

208 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

119 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

97 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

130 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

657 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

297 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

141 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

207 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

165 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

420 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

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

**0**

votes

**0**answers

112 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

125 views

### Two variable recurrence equation with varying coefficients

Hello,
I have the following two variable recurrence equation for integers $j,k$:
$f(j,k) = (k/j)f(j-1,k-1) - (3 + k/j)f(j-1,k+2)$
where $f(j,0) = (3^j - 1)/j + 3jf(j-1,2)$, $f(0,0) = 0$, $f(0,k) = ...

**0**

votes

**0**answers

125 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

83 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

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

**0**

votes

**0**answers

395 views

### Covering a set of intervals

EDIT: I posted this question to http://cstheory.stackexchange.com/questions/4358/covering-a-set-of-intervals , which looks like a more appropriate venue for such a question.
Hello,
I'm trying to ...