Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
481
questions
12
votes
1
answer
547
views
Dividing a chocolate bar into any proportions
Suppose I have a chocolate bar of integer length $L$, and there are $m\leq L$ people that are going to share it. We do not know ahead of time how much each person should receive, all we know is that ...
- 121
12
votes
0
answers
516
views
$q$-analogue of the multinomial theorem?
The $q$-binomial theorem states that
$$
\prod_{k=0}^{n-1}(1+q^kt) = \sum_{k=0}^n q^{\binom k2}{n\brack k}_q t^k.
$$
This identity is a $q$-analogue of the binomial theorem
$$
(1+t)^n = \sum_{k=0}^n \...
- 5,594
12
votes
0
answers
327
views
The number of labeled pairs of edge disjoint trees and related questions
I wonder what is known on the following:
1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices?
2) (harder, it seems) What ...
- 24.2k
12
votes
0
answers
627
views
Wilf's conjecture: complementary Bell numbers
The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....
- 41.8k
12
votes
0
answers
266
views
Number of updown sequences of $1,1,2,2,\cdots,n,n$
I would like to count the updown sequences of the set $\{1,1,2,2, \cdots, n,n \}.$
Sequence $a_1, a_2, a_3, \ldots$ is an updown sequence if the sequence satisfies the following: $ a_1 \lt a_2 \gt a_3 ...
- 121
11
votes
5
answers
12k
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,628
11
votes
2
answers
976
views
How many finitely-generated-by-elements-of-finite-order-groups are there?
I do not know where this question is on the trivial to intractable spectrum.
Consider the set of isomorphism classes of groups finitely generated by elements of finite order. What is the cardinality ...
- 966
11
votes
1
answer
554
views
Equality of two $q$-series. Proof?
Recall the notation $(z;q)_n=(1-z)(1-zq)(1-zq^2)\cdots(1-zq^{n-1})$.
My earlier MO question did not find enough interest or yield an answer. Perhaps the modulo $2$ part might have thrown people off. ...
- 41.8k
11
votes
5
answers
911
views
The number of ways to merge a permutation with itself
Let $\sigma$ be a permutation of $[k]=\{1,2, \dots , k\}$. Consider all the ordered triples $(\pi, s_{1},s_{2})$, such that $\pi$ is a permutation of length $2k-1$ that is a union of its two ...
- 109
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,058
11
votes
1
answer
883
views
And, yet, another evaluation to Catalan numbers
Construct the $n$-tuple Cartesian product of the ternary set $X_n=\{0,1,2\}\times\cdots\times\{0,1,2\}=\{0,1,2\}^n$. Define its subset $W_n$ according to the rule (here $y=(y_1,\dots,y_n)$ is made use ...
- 41.8k
11
votes
1
answer
330
views
a Hankel matrix of involution numbers
Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. I always enjoy these numbers. Of course, here is yet another cute experimental finding for which I ask validity. ...
- 41.8k
11
votes
2
answers
1k
views
Hooks in a staircase partition: Part I
This quest has its impetus in a paper by Stanley and Zanello. I became curious about
What is the sum of all hooks lengths of all partitions that fit
inside the $n$-th staircase partition?
On the basis ...
- 41.8k
11
votes
1
answer
676
views
Two remarkable weighted sums over binary words
This question builds off of the previous MO question Number of collinear ways to fill a grid.
Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting ...
- 22.9k
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
3
answers
427
views
Enumerating all arrangements of intervals with given lengths
Suppose I am given a set of $n$ intervals, each having length $\ell_i$. Is there a bound on the number of possible orderings of their left and right endpoints? For example, if each interval is ...
- 3,929
10
votes
1
answer
366
views
Looking for a "clever" argument for a $q$-series identity
Consider the below $q$-series identity. One of the things I like about this expansion is how nicely the difference on the left hand side factors to the right hand side of the equation.
$$\prod_{k\geq1}...
- 41.8k
10
votes
2
answers
480
views
In search of a $q$-analogue of a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the all-familiar Catalan numbers. Then, the following identity has received enough attention in the literature (for example, Lagrange Inversion: When and How):
\...
- 41.8k
10
votes
2
answers
889
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,570
10
votes
1
answer
469
views
Real rootedness of a polynomial with binomial coefficients
It is possible to show using diverse techniques that the following polynomial:
$$P_n(x)=1 + \binom{n}{2} x + \binom{n}{4} x^2 + \binom{n}{6} x^3 + \binom{n}{8} x^4 +\ldots + \binom{n}{2\lfloor\tfrac{n}...
- 1,879
10
votes
1
answer
481
views
Number of bounded Dyck paths with "negative length"
Let $c(n,k)$ denote the number of Dyck paths of semilength $n$ which are contained in the strip $0 \leq y \leq 2k + 1.$
They satisfy the recursion $\sum_{j=0}^{k+1}(-1)^j \binom{2k+2-j}{j}c(n-j,k)=0$ ...
- 5,572
10
votes
1
answer
348
views
Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity
This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments ...
user82537
10
votes
6
answers
655
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
10
votes
0
answers
133
views
Smallest counterexample to Stein's conjecture?
An equi-$n$-square is an $n$ by $n$ array of cells filled with the symbols $1,2,\dots,n$ so that each symbol occurs exactly $n$ times.
(Every Latin square of order $n$ is an equi-$n$-square, but the ...
- 2,330
10
votes
0
answers
1k
views
Number of rectangles in an n-by-n grid of points
I am seeking a formula for the number of rectangles with vertices belonging to an $n \times n$ square grid of points. This is sequence A085582 in the OEIS. Note that the grid in question has $n^2$ ...
- 856
10
votes
0
answers
190
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,478
9
votes
8
answers
3k
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 ...
- 165
9
votes
2
answers
1k
views
Extracting constant terms: is there a direct way?
$\DeclareMathOperator\CT{CT}$
Let $\CT_t(f(t))$ denote the constant term of the Laurent polynomial of $f(t)$.
Define the two functions $F(x_1,\dots,x_n)$ and $G(y)$ by
$$F:=\prod_{i=1}^nx_i^{-1}(1-x_i)...
- 41.8k
9
votes
2
answers
820
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
9
votes
3
answers
905
views
Number of unlabelled planar graphs
What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?
- 195
9
votes
1
answer
449
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,329
9
votes
2
answers
274
views
Hooks in a rectangle: Part II
This problem is a follow up on my other MO question.
On the basis of experimental data, I'm prompted to ask:
Question. Let $R(a,b)$ an $a\times b$ rectangular grid, $h_{\square}$ the hook-length ...
- 41.8k
9
votes
1
answer
296
views
in need of a direct combinatorial/bijective proof
The following are very familiar and basic items, individually.
(1) The number $a(n)$ of rectangles (parallel to axes) in an $n\times n$ square grid.
(2) The number $b(n)$ of cubes (parallel to axes) ...
- 41.8k
9
votes
1
answer
207
views
Exact enumerations from two-dimensional stat mech models
Exact enumerations corresponding to the dimer model on a hexagonal grid, the dimer model on a square grid, and the four-vertex (aka square ice) model on a square grid are known, namely: lozenge ...
- 19.4k
9
votes
0
answers
278
views
The $n$ queens problem with no three on a line
The $n$ queens problem asks if we can place $n$ queens on an $n\times n$ chessboard such that no two queens attack one another. For example, when $n=8$, here are two solutions (images taken from ...
- 490
9
votes
0
answers
347
views
321-avoiding and parity-alternating permutations
It is classical that 321-avoiding permutations are enumerated by the Catalan numbers.
A permutation is parity-alternating if it sends even integers to even integers, and odd integers to odd. I am ...
- 15.6k
9
votes
0
answers
152
views
Number of tautologies of a given size?
Fix some complete set of $L$ logical connectives such as $\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$ - I'll assume all ...
- 1,065
9
votes
0
answers
393
views
Number of sets $S$ for which number of permutations in $S_n$ with descent set $S$ is odd
The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ is
defined by $D(w)=\{ 1\leq i\leq n-1\,:\, a_i>a_{i+1}\}$.
Given a set $S$, let
$\beta_n(S)$ denote the number of ...
- 49.5k
9
votes
0
answers
322
views
Why does Loday call the permutohedra "zylchgons"?
Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...
- 1,569
9
votes
0
answers
275
views
pattern-avoiding permutations vs multi-core partitions
Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. ...
- 41.8k
9
votes
0
answers
175
views
Cycles of length $2^n - 2$ in the De Bruijn graph
It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
...
- 78.7k
8
votes
2
answers
2k
views
The number of Dyck paths of length $2n$ and height exactly $k$
In A080936 gives the number of Dyck paths of length $2n$ and height exactly $k$ and has a little more information on the generating functions.
For all $n\geq 1$ and $\frac{(n+1)}{2}\leq k\leq n$ we ...
- 355
8
votes
1
answer
293
views
What is the Möbius function for the lattice of partial partitions?
Let $n$ be a positive integer. Let $P$ be the set of partitions of subsets of
$\{ 1, 2, \dotsc, n \}$ (so, for example, when $n=2$, the set $P$ contains $\emptyset$, $\{ \{1 \} \}$, $\{ \{2 \} \}$, $\{...
- 455
8
votes
2
answers
279
views
Counting $m\times n$ $\bigl({1\atop1}{1\atop0}\bigr)$-free $(0,1)$-matrices
Let $G_{m,n}$ denote the number of $m\times n$ $(0,1)$-matrices that avoid the submatrix $\bigl({1\atop1}{1\atop0}\bigr)$. (Submatrices need not be contiguous.) Here are some small values (not yet on ...
- 490
8
votes
2
answers
521
views
Combinatorial proof of fact about Eulerian numbers?
Let $A(m,n)$ denote the Eulerian numbers.
I'm looking for a simple combinatorial proof of the following fact.
Fact. If $p$ is prime and $0\le k < p-1$, then $A(p-1,k) \equiv 1 \pmod{p}$.
The ...
- 78.7k
8
votes
2
answers
520
views
Number of matrices with unit determinant and fixed sum of elements
Question. Let $\mathcal{M}_3$ be the set of $3\times 3$ matrices with non-negative integer entries and unit determinant. What is the number of $M\in \mathcal{M}_3$ with fixed sum of entries? What is ...
- 577
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?...
- 882
8
votes
1
answer
337
views
Bijective proof of formula for rooted binary forests
For $n\ge 1$, let $f(n)$ be the number of rooted complete (unordered) binary trees with $n$ leaves labeled from $1$ to $n$ ("complete binary" means that every vertex has either $0$ or $2$ children and ...
- 78.7k
8
votes
1
answer
375
views
Number of median graphs?
What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...
- 2,330
8
votes
1
answer
677
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 ...
- 882