The enumerative-combinatorics tag has no usage guidance.

**3**

votes

**0**answers

102 views

### Enumerating simple algebraic groups and their irreducible representations

Motivation
Everything is over an algebraically closed field.
Given a faithful representation $G \to \textrm{GL}(V)$, one may try to pin down what the group $G$ exactly is (e.g., the in the case of ...

**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$?

**3**

votes

**1**answer

220 views

### Are all symmetric idempotent Latin squares known?

Are all symmetric idempotent Latin squares known?
There is such a square of order $n$ if and only if $n$ is odd. However, is there a classification of all of them?
(The motivation for the question ...

**14**

votes

**0**answers

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

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

**2**

votes

**2**answers

511 views

### Enumeration of labeled connected bipartite graphs given partite sets

What would be the closed-form expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n - m $?

**3**

votes

**2**answers

381 views

### Counting polynomials with same coefficient sum and a given value at a point

Call an univariate polynomial $f(x) = \sum_{i=0}^{n}a_{i}x^{i} \in \Bbb{Z}[x]$ symmetric if $a_{i} = a_{n-i}$ and $a_{0} = a_{n} > 0$.
For a given $\sum_{i=0}^{n}a_{i}$ and $a_{i} \geq 0$, how ...

**0**

votes

**2**answers

407 views

### Morse matching with 0-cells and (n-1)-cells

Suppose one has a Morse matching (acyclic matching) of a poset $P$ of rank $n$ in which the only unmatched cells are 0-cells and $(n-1)$-cells, the same number $k$ of each one.
If $P$ is connected ...

**3**

votes

**1**answer

290 views

### bounded partitions and bounded signed partitions of integers

Define a bounded signed partition of length $m$ and of bounded height $h$ of an integer $n$ by a relation:
$$n = \pm a_{1} \pm a_{2} \pm a_{3} \pm \dots \pm a_{m}$$ where each $a_{i}$ is a integer in ...

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

**7**

votes

**1**answer

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

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

**13**

votes

**2**answers

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

**3**

votes

**1**answer

179 views

### Number of isomorphism classes of triangulations of a convex polygon

The number of triangulations of a convex $n$-gon is $C_{n-2}$ the $n-2$nd Catalan number. What I am wondering, is if there is a way to enumerate the isomorphism types of these as graphs? I am ...

**1**

vote

**1**answer

307 views

### Enumerating unlabeled trees with degree at most 3

Does anyone know if there is currently any research or any potential bounds on the number of trees on $n$ vertices with degree at most $3$? One can bound this above by $C_{n}$ the $n$th Catalan ...

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

**3**

votes

**2**answers

161 views

### Enumerating 0-1 finite boxes without null rays.

Here rays are called lines.
Call $M(a_1,a_2)$ the number for matrices of length $a_1$ and height $a_2$, made of $0$ and $1$, having neither null vector nor null co-vector. In other words any line (row ...

**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}$, ...

**2**

votes

**1**answer

162 views

### Statistics on Lehmer codes

I am looking at words $\alpha_1 \ldots \alpha_n$, where $\alpha_j \in \{ 1, \ldots, j \}$. Thinking of $\alpha_j$ as a height, these words can be interpreted as left-to-right paths on the positive ...

**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$, ...

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

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

**0**

votes

**1**answer

96 views

### Enumeration of quadrangulations with a boundary and simple faces.

I wish to enumerate all quadrangulations of a $2p$ gon with $n$ internal vertices. Quadrangles are required to have simple faces. Simple face means all four vertices of each quadrangle are distinct.
...

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

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

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

**1**

vote

**0**answers

261 views

### An Pure intriguing counting problem of index sets

Hi Guys. The problem here seems like a homework, but I think that it is not that easy.It comes from a theorem I recently proved.The content of the theorem is not important, the issue is that I have no ...

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

**0**

votes

**2**answers

262 views

### Enumeration Result [closed]

Hi
I have a very soft question:
What exactly is the definition of an enumeration result?
Let say I want to enumerate some combinatorial structure and I came up with an equation for a generating ...

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

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

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

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

**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)} ...

**1**

vote

**1**answer

676 views

### Cayley's Theorem regarding marked trees

Hello,
I have the following proof of Cayley's Theorem: Proof.
This proof counts orderings of directed edges of rooted trees in two ways and concludes the number of rooted trees with directed edges ...

**4**

votes

**1**answer

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

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

**8**

votes

**0**answers

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

**3**

votes

**2**answers

979 views

### Polya's theory of counting and commutative algebra

Do you know if there exist algebraic studies of the ring of the power series which emerge when using the theory of Polya for enumeration of sets with certain symmetries? For instance if some ideals ...

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

**12**

votes

**1**answer

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

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

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

**0**

votes

**2**answers

295 views

### Enumerating m-tuples of Integers Subject to Implication Constraints [closed]

How do I enumerate all $m$-tuples of positive integers $(a_1,...,a_m)$ subject to the following constraints?
For each $i$ in $\{ 1,\ldots,m \}$, there is a number $n_i \geq 0$ such that $a_i \leq ...

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

**0**

votes

**2**answers

1k views

### Convex Polyhedra

Exactly what set of mathematical tools (means: set of areas of mathematical knowledge) are appropriate to begin with to analyse (to enumerate face vectors associated with polyhedron, to calculate the ...

**3**

votes

**3**answers

274 views

### Are there infinite sets of stellations of polyhedra?

Lists of stellations of polyhedrons are given particular rules like in the book The Fifty Nine Icosahedra which follows "Miller's Rules".
There seems to be no "correct" ruleset to use, so more ...

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

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

**7**

votes

**2**answers

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