# 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
1answer
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 ...
3answers
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 ...
1answer
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
8answers
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 ...
3answers
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 ...
4answers
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 ...
1answer
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 ...
2answers
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 ...
2answers
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 ...
1answer
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 ...
9answers
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 ...
2answers
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, ...
3answers
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 ...
3answers
340 views

### Multiplication of (0,1) matrices

is there an obvious lattice path counting interpretation for multiplying n by n (0,1) matrices ?
5answers
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 ...
2answers
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 ...
3answers
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 ...
3answers
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). ...
10answers
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 ...
3answers
403 views