The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
167 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 ...
36
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 ...
3
votes
0answers
85 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 ...
2
votes
1answer
174 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 ...
4
votes
2answers
152 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
3answers
1k views

Dissecting a square

Edited - some comments may now be out-of-date. I thought I had a complete set of solutions to this: ...
10
votes
2answers
430 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
103 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
2answers
325 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 $?
7
votes
1answer
292 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 ...
1
vote
1answer
153 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
0answers
117 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 ...
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 ...
5
votes
0answers
611 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
246 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 ...
0
votes
2answers
251 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
195 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
711 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
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 = ...
8
votes
2answers
552 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
413 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
297 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 ...
3
votes
1answer
777 views

Polya's theory of counting and commutative algebra

Hi. 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 ...
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 ...
12
votes
1answer
731 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 ...
2
votes
4answers
6k 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 ...
0
votes
0answers
248 views

Enumerating m-tuples of Integers Subject to Implication Constraints

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 ...
3
votes
3answers
264 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 ...
7
votes
2answers
726 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. ...
13
votes
2answers
632 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 ...