All Questions
Tagged with enumerative-combinatorics co.combinatorics
69 questions
18
votes
2
answers
1k
views
A combinatorial interpretation for $n$-ary trees for negative $n$
The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation
$$
T_n=1+xT_n^n.
$$
This is usually defined for $n\ge 0$, but the functional equation can be ...
- 1,190
25
votes
7
answers
2k
views
Number of collinear ways to fill a grid
A way to fill a finite grid (one box after the other) is called collinear if every newly filled box (the first excepted) is vertically or horizontally collinear with a previously filled box. See the ...
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
3
votes
2
answers
370
views
Number of bounded Dyck paths with negative length as Hankel determinants
This is a continuation of my post Number of bounded Dyck paths with "negative length".
Let $C_{n}^{(2k+1)}$ be the number of Dyck paths of semilength $n$ bounded by $2k+1.$ They satisfy a ...
- 5,612
1
vote
0
answers
291
views
On the number of Eulerian orderings
This post is a sequel of Eulerian ordering of the integers modulo n.
Let us recall the definition of an Eulerian ordering:
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$....
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 ...
12
votes
2
answers
758
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 ...
- 1,324
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. ...
- 43.1k
10
votes
1
answer
491
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,612
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
9
votes
0
answers
409
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 ...
- 50.8k
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 $\...
- 13.9k
7
votes
1
answer
608
views
Reciprocity for fans of bounded Dyck paths
This is a continuation of some questions asked by Johann Cigler: Number of bounded Dyck paths with "negative length" and Number of bounded Dyck paths with negative length as Hankel ...
- 24.2k
7
votes
1
answer
169
views
Enumerative characterisation of boolean lattices II
This is a sequel of this post.
The boolean lattice $B_n$ is graded with rank numbers $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$, and $n2^{n-1}$ edges.
Question: Is a graded lattice with the ...
5
votes
1
answer
650
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 harder....
- 51
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}\...
- 43.1k
2
votes
2
answers
168
views
Existence of 3-distributed subsets
Denote $[n]=\{1,2,\dots,n\}$. Assume $n\geq2$.
Question. Is it true that given any $S_1,S_2,\dots,S_{2n}$ (repetition allowed) subsets of $[2n]$ with $a\in S_a$ and $\# S_a=n$ for all $1\leq a\leq ...
- 43.1k
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
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
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
21
votes
1
answer
2k
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 ...
- 3,209
20
votes
2
answers
920
views
Counting problems where unlabeled is easier than labeled
I was encouraged to post this question by Jim Propp during a meeting of the Cambridge Combinatorics and Coffee Club. It is a counterpoint to the MathOverflow question "Counting Problems where Labeled ...
- 24.2k
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
17
votes
1
answer
1k
views
Can this probability be obtained by a combinatorial/symmetry argument?
Suppose that $a_1,\dots,a_n,b_1,\dots,b_n$ are iid random variables each with a symmetric non-atomic distribution.
Let $p$ denote the probability that there is some real $t$ such that $t a_i \ge b_i$ ...
- 128k
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
15
votes
4
answers
3k
views
Collecting alternative proofs for the oddity of Catalan
Consider the ubiquitous Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$. In this post, I am looking for your help in my attempt to collect alternative proofs of the following fact: $C_n$ is odd if and ...
- 43.1k
14
votes
1
answer
696
views
Are the asymptotics of A003238 known?
Sequence A003238 of the OEIS counts ``rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins
1, 1, 2, 3, 5, 6, 10, 11, 16, ...
and it is ...
- 1,305
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
13
votes
2
answers
803
views
Two interpretations of a sequence: an opportunity for combinatorics
The sequence that is addressed here is resourced from the most useful site OEIS, listed as A014153, with a generating function
$$\frac1{(1-x)^2}\prod_{k=1}^{\infty}\frac1{1-x^k}.$$
In particular, look ...
- 43.1k
12
votes
1
answer
594
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. ...
- 43.1k
12
votes
2
answers
1k
views
An interesting identity: in search of a proof -Part I
I like the following binomial identity in that the RHS extracts the indeterminate $w$ from the LHS.
Question. Can you show that
$$\sum_{k=0}^n\binom{x+kw}k\binom{y-kw}{n-k}=\sum_{k=0}^n\binom{x+y-...
- 43.1k
12
votes
0
answers
642
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$....
- 43.1k
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 ...
- 43.1k
9
votes
0
answers
161
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,075
9
votes
2
answers
279
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 ...
- 43.1k
8
votes
1
answer
270
views
Sizes of connected components from a random choice in a grid
This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares. ...
- 13.4k
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
7
votes
2
answers
843
views
Decomposition of a natural number as sum of positive integers
Let $n \in \mathbb{N}$ be a positive natural number and denote by $f(n)$ the number of decompositions of $n$ of the form $n = a+b+c+d$ where $a,b,c,d > 0$ are also positive natural numbers such ...
- 8,998
7
votes
0
answers
692
views
How many solutions $\pm1\pm2\pm3...\pm n=0$
As the title said, I'm very interested how many variants to choose $n$ signs from all $2^n$ variants when expression lead to zero. I tried to get recurrent formula but nothing happened.
- 171
7
votes
0
answers
193
views
Factoring a function from a finite set to itself
Let $S$ be a finite set and $f: S \to S$ be a function. Let $k = |f(S)|$ and let $\alpha$ be the partition of $S$ into $f$-fibers, i.e. $\alpha = \{ \alpha_t \}_{t \in f(S)}$ where $\alpha_t = f^{-1}(\...
- 695
7
votes
1
answer
223
views
Result attribution for eigenvalues of a matrix of Pascal-type
A few years ago, I wanted to cite a result in a paper, for which I could not find a reference. I ended up not using the full strength of it, and the part that I needed could be easily proved. Still, I'...
- 1,190
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
6
votes
1
answer
131
views
Number of semistandard tableaux of all possible shapes fitting within some rectangle
Suppose $n$ and $k$ are two integers. Then I am interested in having a closed form for the sum
$$\sum_{\lambda \subset k \times n} S_\lambda (\mathbb{C}^n),$$
where $S_\lambda$ denotes the Schur ...
- 553
6
votes
1
answer
748
views
Enumeration of graphs with a given and bounded degree sequence
What is the best known asymptotic formula for the number of graphs with a given degree sequence $(d_1, ... ,d_n)$, when the degrees are bounded by a constant and the number of vertices $n$ goes to ...
- 1,633
6
votes
3
answers
444
views
Enumeration of lattice paths of a specific type
One of the approaches to "Special" meanders led (in particular) to the following question:
What is the number $a_{m,n}(\ell)$ of $\ell$-step paths from $(1,1)$ to $(m,n)$ using the ...
- 18.4k
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
6
votes
1
answer
460
views
Rational generating function and recursion
Let $\lambda$ denote a hook of size $d$ and $c(\Box)$ the content of $ \Box \in \lambda $. Let $ \text{Hooks}(d) $ be the set of hooks with $d$ boxes. Define
\begin{align}
B(d)&=
\frac{1}{d!} \...
- 685
6
votes
3
answers
515
views
Applying $\sum_i \partial_{x_i}$, $\sum_i x_i \partial_{x_i}$ and $\sum_i x_i^2 \partial_{x_i}$ to Schur polynomials
The operators $L_k=\sum_i x_i^k\frac{\partial}{\partial x_i}$, with integer $k$, take symmetric polynomials into symmetric polynomials.
Is it known how to write the result of the application of $L_0$, ...
- 1,549
5
votes
1
answer
196
views
Enumerating antichains modulo permutation
I encountered the following combinatorics problem in my research, and I'd like to know if there is a reference or an easy solution for such a problem.
Given a partially ordered set $\mathscr P$, an ...
- 903
5
votes
1
answer
398
views
Catalan sequences vs composition sequences
In the paper, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Pitman and Stanley studied the $n$-dimensional polytope
$$\Pi_n(\mathbf x)=\{y\in\...
- 43.1k