# 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
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
340 views

### Multiplication of (0,1) matrices

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