# 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,440 questions
10k views

### Different ways of proving that two sets are equal

I'm not sure if this is a soft question, or should be community wiki. I was explaining to a student how to prove that two sets were equal using what I called the 'oldest trick in the book': to show ...
778 views

### Local complementation in undirected graphs

Problem statement Let $G=(V,E)$ be an undirected graph whose vertices are either black or white. A local complementation of $G$ with respect to a black vertex $v$ consists in: complementing the ...
7k views

### Count of full, binary trees with fixed number of leaves

How many ways is there to build an arithmetic expression with fixed number of terms and fixed order? Let’s assume we have only one distinct operation that is neither commutative nor associative. The ...
22k views

### Finding a cycle of fixed length

Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph? All I know is that Alon, Yuster and Zwick use a technique called "color-coding", which has a ...
398 views

### Elements living in the conjugacy class and in the centralizer of an m-cycle in Am

Let m>1 be an odd natural number, x a m-cycle in Am, the alternating group in m letters, C the conjugacy class of x in Am. Questiom: How can I describe the elements in the set { j | x^j in C} in ...
742 views

### Is there a tournament schedule for 18 players, 17 rounds in groups of 6, which is balanced in pairs?

We are interested in a solution to the following scheduling problem, or any information about how to find it or its existence. This one comes from real life, so you will not only be helping a ...
1k views

### Is there a combinatorial proof of Cauchy-Schwarz?

I've only played with this a little for the past day or so, and haven't thought about it too hard, so it might be obvious. Obviously it's not fair to ask for a "combinatorial proof" of an inequality ...
607 views

### Hamiltonian paths where the vertices are integer partitions

I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n. Let the vertices of the graph G=G(n) denote all the p(...
387 views

### Is it always possible to choose two subsets with the same sum?

Given two positive integers $n, m$, let $A$ be a multiset of $n$ integers taken from { $1,2,\cdots, m$ }, and $B$ be a multiset of $m$ integers taken from { $1,2,\cdots,n$ }. Is it always possible ...
683 views

### Probability of n k-sided dice showing exactly m different faces

I found the following closed form solution for the abovementioned problem: $${1\over k^n}\cdot{k!\over (k-m)!}\cdot{\{{n\over m}\}}$$ with ${\{{n\over m}\}}$ being the Stirling Number of the second ...
4k views

### Defining “average rank” when not every ranking covers the whole set

Here's a mathematical modeling problem I came across while working on a hobby project. I have a website that presents each visitor with a list of movie titles. The user has to rank them from most to ...
2k views

### Cryptomorphisms

I am curious to collect examples of equivalent axiomatizations of mathematical structures. The two examples that I have in mind are Topological Spaces. These can be defined in terms of open sets, ...
1k views

### Is there a combinatorial reason that the (-1)st Catalan number is -1/2?

The $n$th Catalan number can be written in terms of factorials as $$C_n = {(2n)! \over (n+1)! n!}.$$ We can rewrite this in terms of gamma functions to define the Catalan numbers for complex $z$: ...
431 views

### What interesting class of Matroids are there that contains the class of Gammoids?

I am looking for a (already-studied or interesting) class of Matroids such that - Class of Gammoids are contained in it One example would be Strongly-base-orderable Matroids. I would also be grateful ...
2k views

### Topologies on an infinite symmetric group

Let $X$ be an infinite set, and let $G$ be the symmetric group on $X$. I want to understand $G$ by putting a topology on it, without imposing any more structure on $X$. What 'interesting' ...
723 views

### Describe a tree by junctions

I have n sectors, enumerated 0 to n-1 counterclockwise. The boundaries between these sectors are infinite branches (n of them). These branches meet at certain points (junctions). Each junction is ...
1k views

### Mathematical solution for a two-player single-suit trick taking game?

The question on games and mathematics that appeared recently on mathoverflow (Which popular games are the most mathematical?) reminded me of a problem I encountered some time ago : starting with the ...
1k views

### General form of amount of triangles that can be formed in an MxN point lattice

I've been searching for the answer for many years, both by researching by myself and reading about the subject. Now I'm wondering if this has a solution. The problem can be stated as follows. Given ...
3k views

1k views

### Jack polynomials as determinants

Jack symmetric polynomials are known to be generalizations of Schur functions $\chi_\lambda$, for which powerful Weyl determinant formulas are known. Are there any generalizations of two determinant ...
3k views

### Why do Littlewood-Richardson coefficients describe the cohomology of the Grassmannian?

I'm looking for a "conceptual" explanation to the question in the title. The standard proofs that I've seen go as follows: use the Schubert cell decomposition to get a basis for cohomology and show ...