Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

11
votes
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 ...
3
votes
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 ...
2
votes
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
21
votes
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 ...
16
votes
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 ...
5
votes
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 ...
7
votes
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 ...
0
votes
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 ...
10
votes
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 ...
31
votes
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 ...
19
votes
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 ...
4
votes
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, ...
2
votes
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 ...
2
votes
3answers
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
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 ...
15
votes
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 ...
0
votes
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 ...
15
votes
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). ...
10
votes
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 ...
6
votes
3answers
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
3answers
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
3answers
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
1answer
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
1answer
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
2answers
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
3answers
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
4answers
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
6answers
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
2answers
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
2answers
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
5answers
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
3answers
8k views

Is 8 the largest cube in fibonacci sequence?

Can you prove that 8 is the largest cube in fibonacci sequence?
15
votes
5answers
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
3answers
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
1answer
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
3answers
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
1answer
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
3answers
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
6answers
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
6answers
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
3answers
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
2answers
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
1answer
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
6answers
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
5answers
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
3answers
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
8answers
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
4answers
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
9answers
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
5answers
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 ...