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

learn more… | top users | synonyms

2
votes
0answers
182 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
364 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
470 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 ...
8
votes
1answer
7k 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
756 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
236 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
170 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
451 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
170 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 ...
18
votes
2answers
799 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
226 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 ...
14
votes
3answers
813 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
1k 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 ...
7
votes
9answers
474 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
433 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)]} ...
8
votes
3answers
1k 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 ...