The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
0answers
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
2answers
258 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
1answer
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
0answers
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
2answers
309 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: ...
1
vote
2answers
509 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
2answers
380 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
2answers
405 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
1answer
288 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
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 ...
7
votes
1answer
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
2answers
981 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
2answers
743 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
1answer
176 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
1answer
306 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
1answer
200 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
2answers
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
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}$, ...
1
vote
1answer
160 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
1answer
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
0answers
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
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 ...
0
votes
1answer
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
0answers
174 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
5answers
906 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
0answers
828 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
0answers
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
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 ...
0
votes
2answers
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
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 ...
20
votes
1answer
809 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
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 ...
37
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 ...
9
votes
2answers
650 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
1answer
672 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 ...
3
votes
1answer
407 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
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
0answers
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
2answers
977 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
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: ...
12
votes
1answer
776 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
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 ...
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 = ...
0
votes
2answers
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
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 ...
0
votes
2answers
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
3answers
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
2answers
727 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
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 ...
7
votes
2answers
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. ...