The enumerative-combinatorics tag has no usage guidance.

**38**

votes

**6**answers

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

**6**answers

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

**3**answers

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

**1**answer

810 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

**3**answers

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 ...

**19**

votes

**1**answer

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

**1**answer

510 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

**2**answers

986 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

**2**answers

414 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

**2**answers

732 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

**2**answers

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

**1**answer

737 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

**0**answers

568 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

**5**answers

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

**1**answer

534 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

**2**answers

748 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 ...

**12**

votes

**1**answer

779 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

**1**answer

811 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

**0**answers

170 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

**6**answers

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

**8**answers

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

**2**answers

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

**2**answers

304 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 ...

**9**

votes

**0**answers

104 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

**1**answer

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

**0**answers

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

**1**answer

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 ...

**7**

votes

**2**answers

752 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

**2**answers

368 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

**1**answer

283 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

**1**answer

334 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 ...

**7**

votes

**1**answer

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 ...

**7**

votes

**1**answer

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

**1**answer

284 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 ...

**6**

votes

**0**answers

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

**3**answers

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

**2**answers

259 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

**3**answers

508 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

**1**answer

234 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

**0**answers

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

**0**answers

831 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

**4**answers

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

**1**answer

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

**1**answer

432 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

**2**answers

171 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

**2**answers

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

**1**answer

202 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

**1**answer

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 ...

**4**

votes

**0**answers

181 views

### Counting Problems where Labeled is Known but Unlabeled is Not

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula.
To contrast, counting unlabeled trees is considerably ...

**4**

votes

**0**answers

174 views

### When can we determine an $f$-vector or rank-generating function from its unordered list of coefficients?

Let $f_i$ be the number of $i$-dimensional faces in a $d$-dimensional simplicial complex $\Delta $. Recall that the $f$-vector of $\Delta $ is the vector $(f_{-1},f_0,f_1,\dots ,f_d)$ where ...