The tag has no usage guidance.

learn more… | top users | synonyms

39
votes
6answers
3k views

Non-enumerative proof that there are many derangements?

Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exclusion principle ...
26
votes
6answers
2k views

Combinatorial Morse functions and random permutations

This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...
24
votes
3answers
1k views

What can be proved about the Ramanujan conjecture using elementary means?

The Ramanujan conjecture states that the coefficients $\tau(n)$ in the identity $$q\prod_{m=1}^\infty(1-q^m)^{24}=\sum_{n=1}^\infty\tau(n)q^n$$ satisfy the inequality $|\tau(n)|\leq d(n)n^{11/2}$, ...
20
votes
1answer
817 views

A strange sum over bipartite graphs

While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
19
votes
3answers
1k views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...
19
votes
1answer
1k views

Fibonacci, compositions, history

There are three basic families of restricted compositions (ordered partitions) that are enumerated by the Fibonacci numbers (with offsets): a) compositions with parts from {1,2} (e.g., 2+2 = 2+1+1 = ...
18
votes
1answer
512 views

Salié permutations and fair permutations

In October 2010, I published a Monthly problem that introduced the concept of a fair permutation, which is a permutation $\pi$ such that for every $i$, either $\pi(i) > i$ and $\pi^{-1}(i) > i$, ...
18
votes
2answers
988 views

Is this similar to a known combinatorial identity?

(Apologies if this is too obscure.) In joint work with Izzet Coskun we came across the following kind of combinatorial identity, but we weren't able to prove it, or to identify what kind of identity ...
18
votes
2answers
417 views

Counting problems where unlabeled is easier than labeled

I was encouraged to post this question by Jim Propp during a meeting of the Cambridge Combinatorics and Coffee Club. It is a counterpoint to the MathOverflow question "Counting Problems where Labeled ...
14
votes
2answers
735 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 ...
14
votes
2answers
234 views

Generating functions for objects with irrational sizes

A problem I'm investigating concerns a combinatorial class in which the 'atoms' have irrational sizes. It seems likely that this is something that has been considered before, but I haven't been able ...
14
votes
1answer
770 views

Are there enough additive permutations?

I am hoping to learn enough about additive permutations to help with a number theory problem. These permutations also have connections to difference sets, orthomorphisms, transversals, and other ...
14
votes
0answers
572 views

“Special” meanders

One of the open problems in combinatorics is enumeration of meanders. Here on MO I only could find them under the heading not-especially-famous-long-open-problems-which-anyone-can-understand. Since ...
13
votes
5answers
908 views

Is the following invariant of rooted trees a complete invariant?

Recall that rooted trees may be generated by starting with a trivial rooted tree (just a vertex), along with the operations of grafting a number of trees (identify their roots) and adding a new vertex ...
13
votes
1answer
536 views

Are the asymptotics of A003238 known?

Sequence A003238 of the OEIS counts ``rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins 1, 1, 2, 3, 5, 6, 10, 11, 16, ... and it is ...
13
votes
2answers
756 views

How many triangulations of the genus $g$ surface on $n$ vertices?

By "a triangulation of $X$", I mean a simplicial complex whose geometric realization is homeomorphic to $X$. Tutte showed that the number of combinatorially distinct triangulations $t(n)$ of the $2$-...
12
votes
1answer
782 views

Succesful applications of algebra in combinatorics

Hi. This may be a very general question. Are there any examples of problems in combinatorics which were open, but which found a solution when stated in algebraic terms? If yes, could somebody ...
12
votes
1answer
812 views

Two to the power of a triangular number: bijections

The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds (...
12
votes
0answers
173 views

Reference request: exponential growth rates of subword-closed languages are integers

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters. The ...
10
votes
2answers
312 views

Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...
10
votes
6answers
647 views

max # of words with restricted total content

This is the sort of problems in combinatorics with a rather innocent look that turn out to be quite challenging - at least for a bunch of physicists! :) Suppose we have a multiset $\mathbf{M}$ on a ...
9
votes
8answers
2k views

Which came first: the Fibonacci Numbers or the Golden Ratio?

I know that the Fibonacci numbers converge to a ratio of .618, and that this ratio is found all throughout nature, etc. I suppose the best way to ask my question is: where was this .618 value first ...
9
votes
2answers
652 views

An identity involving an infinite integral with a sinh in the denominator

I recently encountered the rather appealing looking integral, which appears in the theory of random matrices : $$\int_{-\infty}^{\infty}\prod_{j=1}^{p-1}(j^{2}+z^{2})\frac{zdz}{\mathrm{sinh}(2\pi z)} ...
9
votes
0answers
106 views

Cycles of length $2^n - 2$ in the De Bruijn graph

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$. ...
8
votes
1answer
2k views

Counting non-isomorphic graphs with prescribed number of edges and vertices

I'd love your help with this question. Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $p$ vertices and $q$ edges are there where $p+q=n$? Thank you very much. Crossposted at ...
8
votes
1answer
147 views

Exact enumerations from two-dimensional stat mech models

Exact enumerations corresponding to the dimer model on a hexagonal grid, the dimer model on a square grid, and the four-vertex (aka square ice) model on a square grid are known, namely: lozenge ...
8
votes
0answers
164 views

What is known about the number of permissible simplicial complexes given the number of k-cells?

Motivation: I am working on a problem that reduces to finding simplicial complexes given some data (details are unnecessary), but all I have managed to wrangle from my input is the number of cells of ...
7
votes
2answers
753 views

Has anyone tabulated 2-knots? Would anyone like to try?

I'd love to have a list of 'small' 2-knots, for some sense of small. It's not clear what one should filter by, but there are two obvious candidates Write a movie presentation, and count the frames. ...
7
votes
2answers
369 views

What is the number of noncrossing acyclic digraphs?

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...
7
votes
1answer
287 views

Number of median graphs?

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...
7
votes
1answer
336 views

Non-enumerative proof that there are many simple permutations?

Terence Tao asked for a non-enumerative proof that a positive proportion of permutations are derangements and got a great answer. Inspired by this, I'd like to ask about another family of permutations....
7
votes
1answer
2k views

Number of graphs with a given number of nodes, edges and triangles

Hi. Does anyone know if it is possible to enumerate the set of labeled/unlabeled graphs (loopless, undirected, only one edge between pairs of nodes) having a given number of nodes, edges and triangles?...
7
votes
1answer
410 views

More asymptotics for trees

This is a follow up to my recent question on the asymptotics of A003238. Lucia gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've ...
6
votes
1answer
286 views

A parity counting problem for subsets over finite fields

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$. For a subset $T\subseteq {\mathbb F}_p$, define $$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb F}_p,b)|...
6
votes
0answers
121 views

What is known about the $q$-analogue of the simplex?

I am interested in the field with one element. I am thus interested in combinatorial interpretations of the Gaussian binomial coefficients. Richard Stanley's "Enumerative combinatorics" mentions ...
6
votes
0answers
217 views

Counting Selections of Entries such having an Extremal Permutation of length n^2+1

Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$. Say a permutation $s$ of ...
5
votes
3answers
2k views

Dissecting a square

Edited - some comments may now be out-of-date. I thought I had a complete set of solutions to this: ...
5
votes
2answers
260 views

Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?
5
votes
3answers
517 views

Combinatorial counting with symmetry

Let $A$ be a set of objects where $|A|=n$. We want to count all the possible ways that we can arrange these objects into $n$ bags with exactly $n$ objects in each. We can reuse any object, however, no ...
5
votes
1answer
246 views

Set counting problem with a cap on the intersection between the set and a fixed partition

Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$. 1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there ...
5
votes
0answers
177 views

How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such ...
5
votes
0answers
836 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
4
votes
4answers
8k views

Non-isomorphic graphs of given order.

It is well discussed in many graph theory texts that it is somewhat hard to distinguish non-isomorphic graphs with large order. But as to the construction of all the non-isomorphic graphs of any given ...
4
votes
1answer
236 views

Imprimitive solutions to $x^2+y^3=z^7$

Poonen, Schaefer, & Stoll give the primitive solutions to $x^2+y^3=z^7$: $$ (±1, −1, 0), (±1, 0, 1), ±(0, 1, 1), (±3, −2, 1), (±71, −17, 2),\\ (±2213459, 1414, 65), (±15312283, 9262, 113), (±...
4
votes
1answer
118 views

Determining the number of hamiltonian paths of $K_n-C_n$

I would like to know information regarding the function $h(n)$ where $h(n)$ is the number of hamiltonian cycles the graph $K_n$ has after removing the edges that make up a hamiltonian cycle of $K_n$. ...
4
votes
1answer
433 views

Number of simplicial polytopes with a given f-vector

Plenty of very nice literature is available on the characterization of f-vectors of simplicial complexes of diverse sorts (results by Billera, Bjoerner, Kalai, Stanley, among others). I mention, as an ...
4
votes
2answers
172 views

Number of monomials of deg D where each variables has low degree

Let $D,n,d$ be three positive integers. I am looking for the number of monomials of degree $D$ in $n$ variables where each variable appears with exponent at most $d$. As a result of an application ...
4
votes
2answers
311 views

Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is: ...
4
votes
1answer
204 views

Reference request: enumeration under group action

Is there a reference for the following lemma (which is useful in counting unlabeled k-trees)? It seems to me that it should be known, but I haven't been able to find it anywhere. Let $G$ be a finite ...
4
votes
1answer
188 views

Statistics on partitions equidistributed with number of even parts

Fix a positive integer $n$. For a partition $λ$ of $n$, let $e(λ)$ be the number of even parts in $λ$. Using bijections, we can show the statistic $e(λ)$ is equidistributed on the set of partitions of ...