# Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

6,658 questions

**11**

votes

**1**answer

361 views

### Littlewood-Richardson-Type Rule for Cohomology Ring of Grassmannians

The ordinary Grassmannian of k-planes in n-space is a coset space for $GL_n$.
It is $GL_n$ mod a maximal parabolic. Here there is a nice basis given by Schubert varieties, which can be indexed by ...

**3**

votes

**3**answers

943 views

### Number of paths equal less than equal to a certain length

Hey,
I need to count the number of paths from node $s$ to $t$ in a weighted directed acyclic graph s.t. the total weight of each path is less than or equal to a certain weight $W$. I have an ...

**2**

votes

**1**answer

7k views

### Number of Shortest paths problem

Hey,
Is countinng the number of shortest paths in a weighted directed acyclic graph with nonnegative weights #P-complete?
If so, is there a proof I can read somewhere?
Thanks

**21**

votes

**8**answers

2k views

### Can we disallow finite choice?

When people work with infinite sets, there are some who (with good reason) don't like to use the Axiom of Choice. This is defensible, since the axiom is independent of the other axioms of ZF set ...

**16**

votes

**3**answers

2k views

### The Sylvester Gallai Theorem and Sections of Varieties with “Simple Topology”.

The Sylvester-Gallai theorem asserts that for every collection of points in the plane, not all on a line, there is a line containing exactly two of the points.
One high dimensional extension ...

**5**

votes

**4**answers

1k views

### Inverting Ramanujan's partition function, p(N)

Would someone be so kind as to enlighten me as to whether the integer partition function, p(N), can be (or has been) inverted and where the inversion is recorded? I'm trying to avoid reinventing the ...

**7**

votes

**1**answer

728 views

### Analogue of Sperner's lemma for Lefschetz theorem?

Sorry if this is easy/well-known, I don't know much algebraic topology and I'm just curious about this question.
One of the easier proofs of the Brouwer fixed-point theorem (we'll say for n = 2 for ...

**0**

votes

**2**answers

240 views

### What is the simplest non-recursive formulation for the following recursive function?

C(0) = 1
C(1) = 1
C(n+1) = Sigma(r, 0, n, C(r) x C(n-r))
Where Sigma() means: Sigma(index var, lower bound, upper bound (inclusive), function(r))
I'm not familiar ...

**10**

votes

**2**answers

1k views

### Number of faithful representations of a finite group

Is it known how many faithful linear representations a finite group G has on a complex vector space of given dimension? What if G is abelian?
I would even be interested in this special case: the ...

**31**

votes

**1**answer

3k views

### Is the set of primes “translation-finite”?

The definition in the title probably needs explaining. I should say that the question itself was an idea I had for someone else's undergraduate research project, but we decided early on it would be ...

**19**

votes

**9**answers

3k views

### How can I generate random permutations of [n] with k cycles, where k is much larger than log n?

I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...

**4**

votes

**2**answers

562 views

### “half arithmetic progressions” in dense sets

Fix a positive real number d>0. Szemeredi's theorem implies that for every integer k, there exists an integer N(k,d) such that if A is a subset of the interval [1,N] with density greater than d >0, ...

**2**

votes

**3**answers

562 views

### Variant of binomial coefficients

I've recently come across a variant of the binomial polynomials, and I'm curious if anyone has seen these before. If so, I'd love a reference, a name, etc.
First recall the following. If z is a ...

**2**

votes

**3**answers

340 views

### Multiplication of (0,1) matrices

is there an obvious lattice path counting interpretation for multiplying n by n (0,1) matrices ?

**5**

votes

**5**answers

1k views

### Bound on cardinality of a union

Suppose I have n finite sets A1 through An contained in some fixed set S, and I am given non-negative integers N and N1 through Nn such that each Ai has cardinality N, and each k-tuple intersection ...

**15**

votes

**2**answers

816 views

### Is there any meaning to a “nice bijective proof?”

From Zeilberger's PCM article on enumerative combinatorics:
The reaction of the combinatorial enumeration community to the involution principle was mixed. On the one hand it had the universal ...

**0**

votes

**3**answers

404 views

### Definition of longest common subsequences

Edit: I realized that I was confusing subsequences and substrings out of absent-mindedness. I've changed the post to reflect this. My question still stands.
I was shown this research problem: If x is ...

**15**

votes

**3**answers

1k views

### Injective proof about sizes of conjugacy classes in S_n

It's not hard to count the number of permutations in a given conjugacy class of Sn. In particular, the number of permutations in Sn whose cycle decomposition has ci i-cycles is n!/(Πi=1n ci!ici). ...

**10**

votes

**10**answers

1k views

### Algorithmic Combinatorics resources?

Some branches of combinatorics lend themselves naturally to algorithms; graph theory is a natural example. However, straight-up enumerative combinatorics relies much more on analytic and algebraic ...

**6**

votes

**3**answers

403 views

### Prime numbers and strings of symbols

Suppose you have N symbols (e.g. "1","2",...,"N" or "a","b",...,"$") and a string of these symbols (say, the first trillion digits of pi). Then does there exist a prime number whose N-ary ...

**7**

votes

**3**answers

851 views

### How can we count lines in an n-x-n rectangular array?

Is there a formula for the number of lines that contain exactly two points through an n x n rectangular array of points?

**6**

votes

**3**answers

755 views

### “Plateaus” to watch out for [closed]

I'm a lot earlier in my math education that most of the people on this site. Currently I'm studying computer science, and I'm interested in looking into statistical and optimization applications, as ...

**4**

votes

**1**answer

307 views

### Number of subdivisions of an n-gon

Suppose I have a regular n-gon. I want to draw some noncrossing diagonals to subdivide it into smaller polygons. In how many ways can I do this? The vertices are unlabeled, so I don't distinguish ...

**3**

votes

**1**answer

384 views

### Any work on the Adams-Watters triangle?

Does anyone know whether any arithmetical or asymptotic results have been obtained about the Adams-Watters triangle?

**6**

votes

**2**answers

487 views

### Can I finitely color Z^2 such that (x,a) and (a,y) are different for every x,y,a?

I ran into this obstacle in a harmonic analysis problem; I know epsilon about coloring problems.
Is it possible to finitely color Z^2 so that the points (x,a) and (a,y) are differently colored for ...

**10**

votes

**3**answers

646 views

### A “round” lattice with low kissing number?

Historically, the lattices with high density were studied intensively, e.g. E_8 lattice or Leech Lattice. However, there are situations that lattices with low kissing number are required. Specifically,...

**15**

votes

**4**answers

2k views

### Dyck paths on rectangles

The number of Dyck paths in a square is well-known to equal the catalan numbers:
http://mathworld.wolfram.com/DyckPath.html
But what if, instead of a square, we ask the same question with a rectangle? ...

**4**

votes

**6**answers

550 views

### Placing checkers with some restrictions

We are going to put n checkers on an (n x n) checkers board, with the following restrictions:
1) In each column there is EXACTLY one checker.
2) For i=1,2,...,(n-1), the first i rows cannot have ...

**3**

votes

**2**answers

755 views

### Helm's improvement to Beck-Fiala theorem

Beck-Fiala theorem states that if X is a finite set and H is any family of subsets of X, in which every vertex occurs in at most d sets of H, then there is a a function f:X->{±1} such for every ...

**6**

votes

**2**answers

402 views

### Asymptotics of the number of compositions whose summands are the divisors of a number?

Let $n$ be a natural number. Let $dc(n)$ be the number of compositions of $n$ where the summands are required to be in the set of divisors of $n$. Standard lore in analytic combinatorics yields the ...

**14**

votes

**5**answers

698 views

### Number of metric spaces on N points

Given $X = \{x_1, ..., x_n\}$, how many collections $C$ of subsets of $X$ are there such that $C$ is the listing of all open balls of some metric space?
The first nontrivial example is $n=3$; let's ...

**24**

votes

**3**answers

8k views

### Is 8 the largest cube in fibonacci sequence?

Can you prove that 8 is the largest cube in fibonacci sequence?

**15**

votes

**5**answers

1k views

### Pairs of shortest paths

It is known that the binomial coefficient $2n \choose n$ is equal to number of shortest lattice paths from $(0,0)$ to $(n,n)$. The Catalan number $\frac{1}{n+1} {2n\choose n}$is equal to the number of ...

**7**

votes

**3**answers

2k views

### Special cases for efficient enumeration of Hamiltonian paths on grid graphs?

While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time ...

**17**

votes

**1**answer

738 views

### Is there a Murnaghan-Nakayama Rule for GL(n,q)?

The Murnaghan-Nakayama rule for S_n is a combinatorial rule to compute the irreducible characters of the symmetric group. Is there a q-analogue of this rule for GL(n,q) to compute the irreducible ...

**5**

votes

**3**answers

1k views

### Asymptotics of a hypergeometric series/Taylor series coefficient.

I was planning on figuring this problem out for myself, but I also wanted to try out mathoverflow. Here goes:
I wanted to know the asymptotics of the sum of the absolute values of the Fourier-Walsh ...

**2**

votes

**1**answer

505 views

### Chains intersecting antichains in finite posets

I feel a little embarrassed to be asking this question here, since I think it should be much easier than I'm making it, but here goes:
Given a finite poset P, does there necessarily exist some chain ...

**5**

votes

**3**answers

779 views

### Is there a software package that does Schubert Calculus computations?

Is there a good software package for doing computations in the cohomology ring of Grassmannians? Things like, I can write down a polynomial in, in fact, special Schubert classes, but it's one where ...

**10**

votes

**6**answers

3k views

### Regular languages and the pumping lemma

Let's say that I want to prove that a language is not regular.
The only general technique I know for doing this is the so-called "pumping lemma", which says that if $L$ is a regular language, then ...

**13**

votes

**6**answers

3k views

### analog of principle of inclusion-exclusion

When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some ...

**12**

votes

**3**answers

818 views

### Is there a matrix whose permanent counts 3-colorings?

Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean:
Kirchhoff's theorem says that if you ...

**28**

votes

**2**answers

7k views

### Mean minimum distance for N random points on a one-dimensional line

Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...

**3**

votes

**1**answer

461 views

### Dance battles and de Bruijn sequences

I hope this doesn't fall under the "not interesting to mathemeticians" category.
I'm attempting to solve one of the facebook engineering puzzles. Essentially, the idea is that two dancers do a ...

**22**

votes

**6**answers

2k views

### Is there a topological description of combinatorial Euler characteristic?

There are a collection of definitions of "combinatorial Euler characteristic", which is different from the "homotopy Euler characteristic". I will describe a few of them and give some references, and ...

**6**

votes

**5**answers

3k views

### Definition of infinite permutations

I've been trying to find a definition of an infinite permutation on-line without much success. Does there exist a canonical definition or are there various ways one might go about defining this?
The ...

**6**

votes

**3**answers

894 views

### Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.

Aside from the Desargues graph, are there nice (at least vertex-transitive), small (say, less than 60 vertices), cubic, bipartite graphs with girth at least 6 and no 8-cycles? (or, even better, no ...

**22**

votes

**8**answers

2k views

### Points and lines in the plane

Does a positive real number $k\geq1$ exist such that for every finite set $P$ of points in the plane (with the property that no three points of $P$ lie on a common line and $|P|\geq3$), one can choose ...

**17**

votes

**4**answers

2k views

### Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.

Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$...

**11**

votes

**9**answers

2k views

### What is the Tutte polynomial encoding?

Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...

**13**

votes

**5**answers

2k views

### Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...