Do NOT use this tag; instead you might use co.combinatorics or various more specific tags.

**7**

votes

**3**answers

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

**1**

vote

**1**answer

349 views

### Indexing combinations with repetition

Let $\Sigma$ be a finite set of symbols with total order. Let $C_k$ be the set of all $k$-multiset (unordered collection of $k$ elements from $S$, with repetition allowed). We can order all the ...

**1**

vote

**1**answer

108 views

### Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$.
I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I ...

**3**

votes

**1**answer

119 views

### Obtaining each set (hyperedge) in a set system (hypergraph) as a union of sets in a smaller set sytem

Let $V$ be a set and $E$ a set of subsets of $V$. I'd like to know the proper terminology for the following concept.
Let me call it "generator". A generator is a set $F$ of subsets of $V$ such that ...

**3**

votes

**1**answer

202 views

### Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...

**0**

votes

**0**answers

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

**1**

vote

**1**answer

994 views

### Graph Theory and Subgraphs [closed]

Let T = (V , E) be a tree with |V | = n ≥ 2. How many distinct paths are there (as sub graphs) in T?
I already have the answer to this question as (n/2). The problem that I'm having is finding ...

**3**

votes

**2**answers

174 views

### Question on weights and minimal degree

Edit: question has been changed from 'lexicographic' (cf. "D K"'s answer below) to 'degree' minimality.
Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k> 3$. Consider the set $M$ of all ...

**7**

votes

**1**answer

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

**1**

vote

**1**answer

169 views

### How to determine the number of a cube within a bigger cube?

Hi all,
I have a cube, sized 39 x 13 x 8. I need to find out how many of them can fit in a cube of 100 x 100 x 100. I need to find the highest number possible.
Do you know of a way to do that ...

**2**

votes

**1**answer

276 views

### On solution of a class of discrete-time Lyapunov equation

Hello members, let's consider the following equation
$$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$
where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment ...

**2**

votes

**1**answer

150 views

### On solution of a discrete-time equation

Hello, members.
I have a problem for the following problem
when I derive an optimization algorithm for stochastic singular systems
$$S(k+1)=A(k)S(k)A^{T}(k)+R(k)+F(k)S(k+1)F^{T}(k)$$
where ...

**1**

vote

**1**answer

406 views

### Distance between vertices in a vertex transitive graphs. [closed]

Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your ...

**6**

votes

**3**answers

945 views

### References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...

**3**

votes

**0**answers

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

**13**

votes

**1**answer

470 views

### Does erosion mix faster than a riffle shuffle?

It is a famous result of Aldous and Diaconis1 that
seven shuffles are necessary and suffice to approximately
randomize 52 cards.2
Here the shuffles are the standard riffle shuffle, where the ...

**0**

votes

**0**answers

133 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

**1**answer

133 views

### expected size of unbalanced biclique in random bipartite graph

I am discovering random graph and I am trying to prove the following result. This is a follow-up on a previous question of mine
what's an upper bound on the size of the largest biclique in random ...

**3**

votes

**1**answer

156 views

### what's an upper bound on the size of the largest biclique in random bipartite graph?

I am not an expert in random graph but I need the following result and I couldn't find any reference on this.
Let $G(X \cup Y,p)$ be a random bipartite graph where the set of edges is $X \cup Y$, $X$ ...

**4**

votes

**2**answers

533 views

### Looking for construction related to Erdos-Szekeres theorem

The Erdos-Szekeres theorem says that every $n$-permutation $p(1), p(2), \ldots, p(n)$ has either an increasing run or a decreasing run of length $\sqrt n$, where an increasing run is
$p(i_1) < ...

**4**

votes

**1**answer

330 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...

**27**

votes

**5**answers

3k views

### How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...

**1**

vote

**3**answers

434 views

### How do quantifiers limit scope?

I'm teaching a discrete math class at the high school level and realize that I'm fuzzier on a topic than I should be.
In their last problem set, I asked my students to translate "There is a triangle ...

**5**

votes

**0**answers

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

**3**

votes

**2**answers

350 views

### The cycle structure of twisted wires, connected

Suppose you have $n$ (blue) wires linearly arrayed at junction box $A$,
connected to a remote junction box $B$, where the wires are now
arrayed
along a line in a randomly permuted order, i.e.,
each ...

**17**

votes

**5**answers

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

**6**

votes

**1**answer

563 views

### Calculating a specific joint probability involving sums of binomial distributions

The following might look like a simple problem - but the question has been unanswered for more than a week on math.stackexchange.com, and I have asked quite a few of the Ph.d. students at our ...

**8**

votes

**2**answers

500 views

### Three half circles on the plane may not meet nicely

Let $H$ denote the union of the northen hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$
...

**6**

votes

**3**answers

559 views

### Cylinders dividing $\mathbb{R}^{3}$

Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$.
For each $n$ we may ask ourselves how to arrange the $n$ cylinders so ...

**5**

votes

**0**answers

827 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" ...

**10**

votes

**12**answers

1k views

### Continuous notions with compelling discrete analogues

Following up on the previous MO question "Are there any important mathematical concepts without discrete analogue?", I'd like to ask the opposite: what are examples of notions in math that were not ...

**9**

votes

**5**answers

549 views

### Minimal blocking objects with shadows like a cube

This is a more geometric version of the previous question,
"Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$.
View an $n \times n \times n$ cube $C_3(n)$ as ...

**5**

votes

**2**answers

286 views

### Lattice-cube minimal blocking sets

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...

**7**

votes

**6**answers

2k views

### Discrete Mathematics textbooks for undergraduates

For the first time, I will be teaching a course on Discrete Mathematics for electrical and computer undergraduates students.
I intend to focus on practical applications.
I would be grateful if ...

**7**

votes

**1**answer

809 views

### Bounding the entropy of a convolution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...

**-1**

votes

**1**answer

329 views

### Number of blocks in a t-(v,k,l) design with empty intersection with a given set U [closed]

Question
Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$?
The answer is: ...

**0**

votes

**1**answer

132 views

### expanding the sqare of sum

If there any way to expand the following?
$$\left(\sum_{i=1}^nx_i\right)^{\frac{1}{2}}$$
and more generally, a way to expand
$$\left(\sum_{i=1}^nx_i\right)^{\frac{p}{q}}$$
where $gcd(p,q) = 1$
...

**3**

votes

**2**answers

353 views

### anyone help me with this inequality

I'm have some difficulties in bounding the following inequality:
I want to find a c as small as possible s.t.
$$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq ...

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

**1**

vote

**1**answer

374 views

### Simple and general relation between continuant polynomials

Continued fraction $[a_0,a_1,...,a_n]$ may be expressed as quotient of two polynomials of $(a_0,a_1,...,a_n)$, named continuants (see http://en.wikipedia.org/wiki/Continuant_%28mathematics%29 )
...

**13**

votes

**7**answers

2k views

### Special arithmetic progressions involving perfect squares

Prove that there are infinitely many positive integers $a$, $b$, $c$ that are consecutive terms of an arithmetic progression and also satisfy the condition that $ab+1$, $bc+1$, $ca+1$ are all perfect ...

**8**

votes

**1**answer

375 views

### Die-rolling Hamiltonian cycles

Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$,
each of whose unit squares is labeled with a number
in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$.
Say that such a labeled $R$ is ...

**1**

vote

**0**answers

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

**3**

votes

**2**answers

222 views

### Designing a tree to match a distribution

I want to design a tree to approximate a given
sequence of numbers, in the following sense.
Let $X=(x_1,\ldots,x_n)$ be $n$ numbers, with $0 < x_i \le 1$
and $\sum_i x_1 = 1$.
For a rooted tree ...

**0**

votes

**0**answers

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

**3**

votes

**0**answers

126 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) & ...

**1**

vote

**2**answers

487 views

### Randomized algorithm?

The problem is as follows. Given a set $S$ of natural numbers of size $n$ where each $x_i \in S$ is from the set $[n^2]$. Elements of $S$ are not necessarily pairwise different, i.e., there can be ...

**2**

votes

**3**answers

877 views

### how to cover a set in a grid with as few rectangles as possible

In calculus, when estimating a area of a set in a 2-dimensional space, we use rectangles to approximate. To get sufficient precision, how many rectangles are needed if the shape of the set is close ...

**2**

votes

**0**answers

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

**4**

votes

**1**answer

840 views

### Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?
For example, consider $K_4$ with vertices ...