**37**

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

**20**

votes

**1**answer

801 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

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

**13**

votes

**2**answers

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

**12**

votes

**2**answers

667 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

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

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

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

**7**

votes

**2**answers

747 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

354 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

326 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

402 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

**2**answers

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

**6**

votes

**0**answers

214 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

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

**5**

votes

**0**answers

791 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

**1**answer

112 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

**3**answers

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

**4**

votes

**2**answers

273 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

199 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

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

**3**

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

**3**

votes

**1**answer

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

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

**3**

votes

**2**answers

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

**3**

votes

**1**answer

140 views

### Enumerating matrices function of ranks

Is there an expression/approximate expression for number of real matrices $M\in\{0,1\}^{n\times n}$ of rank $r\leq n$?
Is it known if $M$ is restricted to symmetric/skew-symmetric matrices?
Does ...

**3**

votes

**2**answers

52 views

### Enumerating Tri-vertex transitive polyhedra n > 3 faces

How many unique vertex transitive polyhedra exist where each vertex has 3 incident edges
for polyhedra with n (= # faces) > 3 ?

**3**

votes

**1**answer

385 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

**2**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

112 views

### Counting perfect matchings with integrals

Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to ...

**3**

votes

**0**answers

100 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

**2**answers

368 views

### Enumerating solutions to an underdetermined non-homogenous linear system of Diophantine equations

I have a large, under-determined system (60 equations and 116 unknowns) of linear Diophantine equations. I am aware of the algorithms typically used to solve these systems, which is not my question.
...

**2**

votes

**1**answer

111 views

### Stirling numbers of the second kind with maximum part size

The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...

**2**

votes

**1**answer

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

**2**

votes

**1**answer

123 views

### Counting elements with certain word length in abelian groups

Given a (finite) abelian group $G = \langle S \mid R \rangle$, has the problem of counting the number of elements which can be expressed as a word (in $S$) of length $\leq k$ been studied? If so, ...

**2**

votes

**0**answers

51 views

### Counting labelled graphs according to sets of size 3

In this question we are counting labelled simple graphs. No concept of isomorphism is involved.
Let $G(n,e,t)$ be the number of labelled simple graphs with $n$ vertices, $e$ edges, and $t$ sets of ...

**2**

votes

**0**answers

154 views

### combinatorial rectangles

Consider the set $S$ of all $m\times m$ matrices with $0-1$ entries with exactly $T$ combinatorial rectangles of all $0$s or all $1$s that partition each matrix in a non-overlapping manner.
Is there ...

**1**

vote

**2**answers

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

**1**

vote

**1**answer

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

**1**

vote

**1**answer

164 views

### A generalisation of Narayana-like numbers (walks on the 2D lattice)

I apologize in advance if this question has a trivial answer. I am pretty sure this kind of problem was already studied and I am mostly asking for good references.
Given integers $0 < k \le n+1,$ ...

**1**

vote

**1**answer

56 views

### Number of different normalized inner products

Let $u,v\in\{0,1\}^n$ be $0-1$ vectors with $n$ components.
Let $I=\langle u,v \rangle$. Clearly $I$ can take values in $\{0,1,\dots,n-1,n\}$.
How many different values can $$I'=\frac{\langle u,v ...

**1**

vote

**1**answer

184 views

### Counting matrices of special types

How many symmetric and non-symmetric $n\times n$ matrices with $0/1$ entries are there such that every row is distinct and every column is distinct? (I am looking for a proof as well).
If only every ...

**1**

vote

**0**answers

131 views

### Counting number of ways to place bags and marbles inside bags so all bags contain an odd number of marbles

There was a famous trick question posed once in math.stackexchange here. The question can be loosely translated to "Is it possible to place nine marbles into four bags so that each bag has an odd ...

**1**

vote

**0**answers

164 views

### Distinct determinants of circulants

If $M$ is a circulant integer matrix of size $n\times n$ whose entries are randomly chosen from $\{0,1\}$ value, how many different determinants does $M$ possibly take value in?
For $n=1,2,3,4$, I ...

**1**

vote

**0**answers

148 views

### Distinct Numbers

Let $x_{ij}\in\{0,1\}$ for ${i=1}$ to ${m}$ and for ${j=1}$ to $n$. How many different values does $$\prod_{i=1}^m\sum_{j=1}^nx_{ij}$$ cover?
Is there an $a_{ijk}\in\Bbb R$ (there is a $a_{ijk}\neq0$ ...

**1**

vote

**0**answers

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

**1**

vote

**1**answer

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

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