Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
503 questions
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 {$...
- 32.1k
0
votes
1
answer
378
views
Rational solution for linear differential equation
The following is a recursion for one point monotone Hurwitz numbers
$$
d \, m_g(d) = 2(2d-3) \, m_g(d-1) + d(d-1)^2 \, m_{g-1}(d)\label{1}\tag{$*$}
$$
with initial condition $m_0 (1) =1$ and some of ...
- 685
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 ...
- 32.1k
4
votes
1
answer
271
views
The class of $(-1,0,1)$-matrices with all row sums and column sums equal to $0$
Let $n$ be an even positive integer and $W_n$ be the class of all $n\times n$ matrices with entries from the set $\{-1,0,1\}$ such that all row sums and column sums are equal to $0$.
For each $M\in ...
- 32.1k
13
votes
1
answer
2k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
- 32.1k
20
votes
4
answers
2k
views
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Is there a non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
It is a nice exercise with rational generating functions (or equivalently, ...
- 32.1k
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" ...
- 7,226
0
votes
1
answer
145
views
Rational solution of differential equation
The following is a recursion for one point monotone Hurwitz numbers
$$
d \, m_g(d) = 2(2d-3) \, m_g(d-1) + d(d-1)^2 \, m_{g-1}(d)\label{1}\tag{$*$}
$$
with initial condition $m_0 (1) =1$ and some of ...
- 7,226
1
vote
1
answer
209
views
Number of paths to a specific vertex in the Young's lattice
Consider the Young's lattice. What is the number of paths starting from the origin (0) to a specific Young diagram?
For instance, the Young diagram corresponding to the integer partition 1+1+1 has 1 ...
- 2,743
0
votes
0
answers
171
views
Total sum of characters over partitions with distinct parts
In my earlier quest, we looked at $\chi_{\mu}^{\lambda}=$value of an irreducible character of the symmetric group $\frak{S}_n$, where $\mu$ and $\lambda$ are (unrestricted) partitions of $n$. Then, ...
- 43.2k
7
votes
2
answers
480
views
Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?
Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
- 32.1k
7
votes
2
answers
712
views
Total sum of squares of characters of the symmetric group $\mathfrak{S}_n$
In my earlier MO post, I proposed the double sum $\sum_{\mu\vdash n}\sum_{\lambda\vdash n}\chi_{\mu}^{\lambda}$ regarding characters of the symmetric group $\mathfrak{S}_n$. Soon after, I started ...
- 43.2k
1
vote
1
answer
238
views
Binomial coefficient in a binomial coefficient
I am doing some research in combinatorics, and I found that I have to consider the following binomial coefficient :
$$ \binom{\binom{i}{j}}{k} $$
(In fact, I have to take the product for fixed $i,k$ ...
- 33.8k
4
votes
1
answer
698
views
Total sum of characters of the symmetric group $\frak{S}_n$
Let $\chi_{\mu}^{\lambda}$ denote a value of an irreducible character of the symmetric group $\frak{S}_n$, where $\mu, \lambda\vdash n$. When $\mu=(n)$, then it's known that
$$\sum_{\lambda\vdash n}\...
- 250
25
votes
3
answers
1k
views
The verbs in combinatorics: Enumerating, counting, listing and all that
Two closely related, but different tasks in combinatorics are
determining the number of elements in some set $A$, and
presenting all its elements one by one.
Question: What are some works in ...
- 60.5k
6
votes
2
answers
613
views
Counting $\pm 1$ and $0$'s in the character tables of $\frak{S}_n$
Let $\chi_{\mu}^{\lambda}$ denote a value of an irreducible character of the symmetric group $\frak{S}_n$, where $\mu, \lambda\vdash n$. When $\mu=(n)$, then it's known that
$$\sum_{\lambda\vdash n}\...
- 43.2k
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$?
- 32.1k
2
votes
0
answers
81
views
Number of nonisomorphic weighted hypergraphs of certain type
Let $G=(V,E)$ be an unlabeled simple hypergraph with weighted vertices and given properties:
$|v|⩾max(d(v);\;3)\;∀v∈V$, where $|v|$ denotes weight of vertice $v$ and $d(v):=\#(e:\;v∈e)$ - number of ...
- 651
7
votes
0
answers
183
views
Explaining $\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(a^i-1\right)$ by a free $S_n$-action
Here is an olympiad-level problem on elementary number theory:
Let $a$ be an integer and $n$ a positive integer. Prove that
\begin{align}
\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(...
- 33.8k
3
votes
0
answers
254
views
Enumerating multi-core binary partitions
An integer partition $\lambda$ of $n$ is called a binary partition provided that its parts are powers of $2$ (dyadic). Example: Let $n=3$. The binary partitions are $\lambda=(2,1)$ and $\lambda=(1,1)$ ...
- 1,676
6
votes
1
answer
242
views
$(q,t)$-Fibonacci polynomials: area & bounce statistics
This is related to my earlier (unanswered) MO post. Preserve notations from there.
We take advantage of the one-to-one correspondence between the $(s,s+1)$-core partitions and $(s,s+1)$-Dyck paths. ...
- 85.6k
1
vote
1
answer
248
views
mapping integers to k-ary trees
Is there an algorithmic way to map the natural numbers to unique k-ary trees?
I am familiar with the work of Tychonievich who created a mapping from integers to binary trees. https://www.cs.virginia....
- 37.7k
4
votes
0
answers
128
views
Asymptotics of holonomic recurrences and the Birkhoff-Trjitzinsky method
While reading about asymptotics of holonomic recurrences, I had the following impressions that are related to the divulgation of the theory:
I don't know what is the current status of the divulgation ...
2
votes
0
answers
290
views
Can ${2n \choose n}$ ever be divisble by $2n+1$ (for positive integer $n$)?
The question in the title arose from some semi-recreational number theory. A quick check on a spreadsheet shows the answer is negative for $1\leq n \leq 20$; I haven't tried to use any more serious ...
- 25.8k
1
vote
1
answer
261
views
Number of maximal independent sets in a hypergraph
Are there any known upper bounds on the number of maximal independent sets in a hypergraph? I'm aware that simple graphs have an upper bound of $O(3^{n/3})$. How about on the number of independent ...
- 13.4k
1
vote
0
answers
142
views
A holonomic function and its singularity
The following series where $q_i , h$ are constant parameters. $G(z)$ is a rational function.
$$F(x):=\sum_{d= 1}^\infty \sum_{k=1}^d (-1)^{d-k} \, s_{(k, 1^{d-k})}(\tfrac{q_1}{h}, \tfrac{q_2}{h}, \...
- 6,357
3
votes
1
answer
118
views
Using singularity analysis for probability at a threshold?
In some urn model with parameter $p$, the generating function
$$
f_p(z) \;=\; \frac{1+p\,z}{1-(1-p)\,z\,(1+p\,z)}
$$
is such that $[z^n]f_p(z)$ is the probability that an $n$-urn configuration has a ...
- 1,043
3
votes
0
answers
137
views
Positivity of sequences
Totally positive sequences $\lbrace a_n\rbrace_{n\in\mathbb{Z}}$ are defined as those such that the Töplitz matrix $A_{ij}=a_{i-j}$ is totally positive (all its minors are non-negative). An ...
1
vote
0
answers
69
views
LGV scheme: Any situations where the weights shift differently for each path?
In Cylindric partitions, Proposition 1, Gessel and Krattenthaler prove a formula for lattice paths on a cylinder
In our particular problem, we again have paths $((P_{1},k_{1}),...,(P_{r},k_{r}))$ but ...
- 5,474
1
vote
2
answers
1k
views
Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?
I am looking at doing some basic validation on a database of st-dags. It would be useful to have:
A formula for the number of non-isomorphic st-dags with n vertices
A formula for the same with n ...
- 5,590
10
votes
1
answer
497
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}...
- 109k
2
votes
2
answers
105
views
Calculating number of vertex-pairs with separate common ancestor
Given a tree-graph with one of the vertices designated as the root, what is the complexity of calculating the number of vertex-pairs $\lbrace u,v \rbrace$ of which $v$ is not nearer to the root than $...
- 63.9k
3
votes
1
answer
186
views
Is there a $q$-analogue to Shapiro's convolution identity?
Let $C_n=\frac1{n+1}\binom{2n}n$ denote the Catalan numbers.
This question is motivated by the (unanswered) MO post by Alexander Burstein and my own (answered by Fedor Petrov) MO post.
Specifically, ...
- 7,875
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
- 13.9k
3
votes
1
answer
366
views
A recurrence relation on Catalan numbers
In the classical problem of bracketing $n$ numbers, I know the response is $C_{n-1}$. I find this
$$C_{n-1}=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{i+1}\binom{n-i}{i}C_{n-1-i}$$
but I ...
- 4,713
2
votes
0
answers
171
views
Enumeration and encoding of simplicial complexes
I'd like to know how to enumerate and encode all (abstract) simplicial complexes of a given kind.
To start as simple as possible, consider the familiy $\mathcal{S}_n^{d}$ of simplicial complexes which ...
- 32.5k
3
votes
0
answers
154
views
Ehrhart-Macdonald reciprocity with multiplicities
Let $P$ be a convex lattice polytope in $\mathbb{R}^n$. The function $L(t, P) = |\mathbb{Z}^n \cap t\cdot P|$ is a polynomial, and we have an equality
$$L(-t, P) = (-1)^nL(t, P^{int}),$$
where $P^{int}...
- 645
3
votes
0
answers
258
views
Partitions of n into k distinct parts which are multiples of given numbers
Is there anything known about the number of partitions of an integer $n$ into $k$ distinct parts in the following way?
Let $a_1,\dotsc,a_k\geqslant1$ be given integers. In how many ways can we write $...
- 539
11
votes
2
answers
1k
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 ...
- 1,027
11
votes
5
answers
927
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
4
votes
0
answers
205
views
Dimension of a certain space of symmetric functions: Part I
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. A partition $\lambda$ is called a $t$-core if none of its hook lengths are multiples of $t$.
QUESTION. Consider the ...
- 43.2k
1
vote
0
answers
90
views
Dimension of a certain space of symmetric functions: Part II
This is the second installment of my earlier MO question.
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. Denote the set of all partitions with distinct parts by $\...
- 43.2k
4
votes
1
answer
423
views
Identity involving binomial coefficients and partitions
Working on a problem in the symmetric group I have stumbled upon the following equation:
$$\sum_{\substack{\pi=(1^{c_1},2^{c_2},\ldots,n^{c_n})\\\textrm{partition of }n}}(-1)^{n-\sum_{i=1}^nc_i}\frac{...
- 109k
1
vote
0
answers
94
views
Number of extremal $\{0,1\}$ matrices having permanent $1$ property
Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$?
I think it might be $\mathsf{poly}(n!)$ bounded.
Is there a function ...
- 13.9k
3
votes
0
answers
214
views
Does every finite lattice embed into a finite Eulerian lattice?
A finite Boolean lattice is a lattice isomorphic to the subset lattice of a finite set. Every Boolean lattice is Eulerian, namely, a graded lattice $L$ such that $\mu(a,b) = (-1)^{|b|-|a|}$ for all $a,...
6
votes
1
answer
437
views
Typo in Stanley, Enumerative combinatorics II, Cor. 7.23.9?
In Stanley, EC2, we have the following statement:
I think there is a typo in the first sum after "generating function",
and that $[n]_q!$ should be replaced by $(1-q)(1-q^2)\dotsb (1-q^n)$,
...
- 24.2k
0
votes
0
answers
299
views
Question on rank of matrices over $\mathbb F_2$
$A$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $k\leq n-1$.
$B$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $n$.
$T$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $1$...
- 13.9k
6
votes
3
answers
437
views
Eigenvalues of the Laplacian of the directed De Bruijn graph
We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...
- 1
6
votes
1
answer
350
views
What is the direct proof of the recurrence relation about lattice path enumeration given by Bizley?
Let $k$ be a nonnegative integer and let $m,n$ be coprime positive integers. Let $\phi_k$ be the number of lattice paths from $(0,0)$ to $(km,kn)$ with steps $(0,1)$ and $(1,0)$ that are never rising ...
- 5,822
3
votes
1
answer
198
views
Maximum number of subsets in which people co-exist with their friends
Let $P = \{1,\dots,p\}$ be a set of people. Consider partitioning $P$ into two disjoint sets, $A$ (of cardinality $a$) and $A^c = P-A$. Let us index $A$ as $A = \{A_1,\dots,A_a\}$. Each person in $A$ ...
- 34.3k