Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
503 questions
3
votes
2
answers
402
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 ...
- 13.9k
0
votes
2
answers
539
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 ...
- 9
3
votes
1
answer
705
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 ...
- 13.9k
5
votes
1
answer
214
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 ...
- 51
9
votes
1
answer
459
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 permutations....
- 2,339
18
votes
2
answers
2k
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 ...
user5117
16
votes
2
answers
2k
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 $2$-...
- 7,857
6
votes
2
answers
7k
views
How many perfect matchings in a regular bipartite graph?
We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$.
What is an upper bound on the number of perfect matchings of $G$?
- 61
3
votes
1
answer
461
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 ...
- 143
1
vote
1
answer
592
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 number,...
- 143
5
votes
1
answer
327
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 ...
- 17k
3
votes
2
answers
231
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 ...
- 1,306
25
votes
3
answers
2k
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}$, ...
- 29k
2
votes
1
answer
244
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 ...
- 3,081
18
votes
1
answer
1k
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$, ...
- 82.6k
6
votes
0
answers
207
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 $f_{-1}=...
- 3,532
10
votes
6
answers
657
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 ...
- 101
0
votes
1
answer
123
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.
...
- 141
32
votes
5
answers
9k
views
How many binary operations are associative?
Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...
- 151k
7
votes
0
answers
355
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 ...
- 1,414
11
votes
5
answers
2k
views
Is it possible to have t triangles in some graph on n vertices?
Fix $n>4$. Is there a characterization of the set $T_n$ of all natural numbers $t$ such that there is some graph on $n$ vertices with exactly $t$ distinct triangles? For example, it's clear that {$...
- 1,068
13
votes
5
answers
1k
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 ...
- 1,325
7
votes
1
answer
1k
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" ...
5
votes
2
answers
566
views
Orbits of independent sets of the hypercube
How does one enumerate the distinct orbit classes of independent sets of the hypercube modulo symmetries of the hypercubes?
The counting of the number of independent sets in an $n$-dimensional ...
- 171
1
vote
0
answers
278
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 ...
- 393
19
votes
3
answers
2k
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 sub-...
- 3,463
0
votes
1
answer
312
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 ...
- 11
6
votes
0
answers
256
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 ...
- 393
21
votes
1
answer
1k
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.7k
29
votes
6
answers
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 ...
- 34.7k
47
votes
6
answers
5k
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 ...
- 114k
9
votes
2
answers
845
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)} ...
- 91
23
votes
3
answers
3k
views
Proofs of parity results via the Handshaking lemma
I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...
1
vote
1
answer
1k
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 ...
- 13
8
votes
1
answer
725
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 ...
- 902
10
votes
1
answer
7k
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 ...
- 101
10
votes
0
answers
191
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 ...
- 1,488
4
votes
3
answers
1k
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 ...
- 902
6
votes
3
answers
3k
views
Dissecting a square
Edited - some comments may now be out-of-date.
I thought I had a complete set of solutions to this:
...
- 119
13
votes
1
answer
1k
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 ...
8
votes
1
answer
3k
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 triangles?...
- 902
23
votes
2
answers
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 = ...
- 4,589
14
votes
5
answers
4k
views
Are there more connected or disconnected graphs on $n$ vertices?
Suppose we are talking about graphs with $n$ labeled vertices. Which graphs are more common: connected or disconnected?
- 1,765
0
votes
2
answers
318
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 n_i$...
- 11
13
votes
1
answer
728
views
Maximum number of distinct diagonals generated by permutations
Given a matrix $A \in \{0,1\}^{n \times n}$, let $diag(A)$ be the set of vectors $D \in \{0,1\}^n$ that are the diagonal of one of the $n!$ matrices obtained from $A$ via row permutations.
What is ...
- 131
36
votes
3
answers
7k
views
Distinct numbers in multiplication table
Consider the multiplication table for the numbers $1,2,\dots, n$. How many different numbers are there? That is, how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there?
I'm ...
- 2,821
7
votes
4
answers
11k
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 ...
- 2,855
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k
12
votes
5
answers
13k
views
Number of permutations with a specified number of fixed points
Let $F(k,n)$ be the number of permutations of an n-element set that fix exactly $k$ elements.
We know:
$F(n,n) = 1$
$F(n-1,n) = 0$
$F(n-2,n) = \binom {n} {2}$
...
$F(0,n) = n! \cdot \sum_{k=0}^n \...
- 9,720
3
votes
3
answers
311
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 ...
- 2,615