Questions related to counting the number of elements of some finite sets, or to other problems in enumerative combinatorics.

learn more… | top users | synonyms

2
votes
2answers
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
2answers
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
2answers
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
0answers
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
2answers
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
3answers
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
2answers
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
1answer
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
0answers
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
1answer
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
2answers
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
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 ...
5
votes
0answers
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
0answers
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
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
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
1answer
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
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
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
1answer
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
1answer
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
1answer
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
2answers
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
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
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
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 ...