**2**

votes

**2**answers

138 views

### Number of ways of tiling a $2 \times n$ rectangle using rectangles with integer sides

How many ways are there of tiling a $2 \times n$ rectangles using rectangular tiles with positive integer side lengths?
I've done some work on this and have found a way of calculating this that's ...

**13**

votes

**2**answers

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

**2**

votes

**1**answer

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

**10**

votes

**1**answer

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

**0**

votes

**0**answers

43 views

### Enumeration of simple graphs with given degree distribution/sequence [duplicate]

Is there any exact formula for asymptotic/exact enumeration of simple graphs with given degree sequence? I just found some results about it, but the formula is hold on for some conditions, for example ...

**1**

vote

**1**answer

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

**2**

votes

**1**answer

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

**1**

vote

**0**answers

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

**3**

votes

**1**answer

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

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

**1**answer

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

**4**

votes

**1**answer

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

**1**

vote

**1**answer

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

**2**

votes

**0**answers

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

**3**

votes

**2**answers

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

**1**

vote

**1**answer

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

**3**

votes

**0**answers

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

**7**

votes

**2**answers

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

**9**

votes

**2**answers

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

**3**

votes

**0**answers

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

**2**

votes

**2**answers

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

**4**

votes

**3**answers

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

**3**

votes

**2**answers

53 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 ?

**7**

votes

**1**answer

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

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

**1**answer

216 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

**2**answers

289 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

**2**answers

484 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

**1**answer

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

**13**

votes

**2**answers

691 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

172 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

281 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

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

**5**

votes

**0**answers

805 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

260 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

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

216 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

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

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

**9**

votes

**2**answers

644 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

644 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

**1**answer

397 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

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

**3**

votes

**2**answers

969 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

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