The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
576 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
1answer
286 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
1answer
121 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
2answers
332 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
0answers
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 ...
1
vote
1answer
251 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 ) ...
12
votes
5answers
1k views

Special arithmetic progressions involving perfect squares

Some time ago the following rather easy problem appeared in an online publication called "Problems in Elementary NT" by Hojoo Lee: Prove that there are infinitely many positive integers $a$, $b$, $c$ ...
8
votes
1answer
361 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
0answers
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 ...
3
votes
2answers
203 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
0answers
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: ...
3
votes
0answers
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) & ...
1
vote
2answers
472 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
3answers
531 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
0answers
301 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. ...
1
vote
1answer
578 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 ...
3
votes
0answers
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\}$ ...
2
votes
0answers
142 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 ...
4
votes
2answers
317 views

Computer platforms for combinatorial search problems/mathematical music theory?

I'm finding programming various combinatorial searches (connected to mathematical music theory) in a general purpose computer language tedious, so I'd like pointers to computer platforms/environment ...
2
votes
4answers
428 views

Statistical computation in matrix. Rows before columns? riddle..

First I'll phrase the question as a riddle, and than as a general math problem. We have 12 lettered vases $(A,B,...,L)$, in each vase there are 30 numbered balls (1-30). In each ball there is some ...
1
vote
1answer
3k views

How to compute KL-divergence when PMF contains 0s?

From the Wikipedia page on Kullback-Leibler divergence, the way to compute this metric is to utilize the following formula: The way I understand this is to compute the PMFs of two given sample sets ...
3
votes
0answers
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 ...
5
votes
1answer
231 views

Reference sought for Conways observation on stable matchings.

Looking for a reference on the observation that the set of stable matchings form a distributive lattice. This is attributed to Conway by Knuth in "Marriages Stables" but I would like an explicit ...
0
votes
1answer
151 views

the maximal length of a special dicksonian sequence

First, we define a sequence $t_{1},t_{2},\cdots,t_{k}$ of n-tuples dicksonian, if $\forall 1\leq i < j\leq k,$ there does not exist a non-negative n-tuple t such that $t_{i}+t=t_{j}.$ For example, ...
0
votes
2answers
434 views

A non-associative three-valued logic

There are three elements: x, y, z and a relation C: x C y, y C z, z C x, x C x, y C y, z C z. Let us introduce two binary operations with respect to the C: "the leftmost" (L) and "the rightmost" ...
1
vote
0answers
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 ...
17
votes
2answers
708 views

Is there a discrete Cerf theory?

Towards the end of the 1990's, Robin Forman developed a discrete version of Morse theory, which concerns maps from a simplicial complex to $\mathbb{R}$ satisfying a combinatorial analogue to the ...
4
votes
0answers
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 ...
13
votes
3answers
775 views

Partitioning the integers $1$ through $n$ so that the product of the elements in one set is equal to the sum of the elements in the other

I asked this question at math.SE a couple of months ago and only got a partial answer, so I thought I would try here. It is known that, for $n \geq 5$, it is possible to partition the integers ...
8
votes
2answers
975 views

palindromic subsequences

I'd like any insight or references to the following two conjectures (see the glossary below for definitions): Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and ...
0
votes
0answers
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 ...
7
votes
9answers
427 views

What are some early examples of creation of lists / catalogues of (particularly) combinatorial objects?

A lot of effort in discrete maths / combinatorics is expended in the construction of lists, catalogues or census [sic] of combinatorial objects such as groups, graphs, designs etc. These catalogues ...
1
vote
0answers
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)]} ...
7
votes
3answers
936 views

How to characterize a Self-avoiding path.

I cannot find any answer to that apparently simple problem : On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}. Is there a rule ...