Questions tagged [enumerative-combinatorics]

Filter by
Sorted by
Tagged with
35 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 ...
falagar's user avatar
  • 2,761
18 votes
0 answers
977 views

"Special" meanders

One of the open problems in combinatorics is enumeration of meanders. Here on MO I only could find them under the heading not-especially-famous-long-open-problems-which-anyone-can-understand. Since my ...
მამუკა ჯიბლაძე's user avatar
16 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 ...
Alexander Burstein's user avatar
24 votes
6 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 ...
Sebastien Palcoux's user avatar
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 ...
Tony Huynh's user avatar
  • 31.5k
2 votes
2 answers
353 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 ...
Johann Cigler's user avatar
1 vote
0 answers
279 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\}$....
Sebastien Palcoux's user avatar
12 votes
2 answers
720 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 ...
Gwyn Whieldon's user avatar
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. ...
T. Amdeberhan's user avatar
10 votes
1 answer
479 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$ ...
Johann Cigler's user avatar
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 ...
Blaise Compaore's user avatar
9 votes
0 answers
392 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 ...
Richard Stanley's user avatar
7 votes
1 answer
593 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 ...
Sam Hopkins's user avatar
  • 22.5k
7 votes
1 answer
168 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 ...
Sebastien Palcoux's user avatar
5 votes
1 answer
632 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....
J.D.'s user avatar
  • 51
4 votes
1 answer
567 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}\...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
1 vote
1 answer
290 views

Truncated sums of symmetric polynomials; reference request for an algebraic derivation

EDIT: This is a case of being too wrapped up in a formulation ($e_j,p_i,$ and the like) to try something simple. It did not occur to me to pull exp to the outside in the weeks I have stared at this. ...
Gerhard Paseman's user avatar
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 ...
Terry Tao's user avatar
  • 108k
31 votes
5 answers
8k 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 ...
Joseph O'Rourke's user avatar
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 ...
Liviu Nicolaescu's user avatar
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 ...
Gerhard Paseman's user avatar
20 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 ...
20 votes
2 answers
889 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 ...
Sam Hopkins's user avatar
  • 22.5k
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-...
Jernej's user avatar
  • 3,433
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$ ...
Iosif Pinelis's user avatar
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$-...
Matthew Kahle's user avatar
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 ...
T. Amdeberhan's user avatar
14 votes
1 answer
677 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 ...
Michael Albert's user avatar
13 votes
2 answers
799 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 ...
T. Amdeberhan's user avatar
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-...
T. Amdeberhan's user avatar
12 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?
Leonid Petrov's user avatar
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$....
T. Amdeberhan's user avatar
11 votes
1 answer
551 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. ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
8 votes
1 answer
244 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. ...
Wolfgang's user avatar
  • 13.2k
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 ...
1Spectre1's user avatar
  • 355
7 votes
1 answer
217 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'...
Alexander Burstein's user avatar
7 votes
2 answers
579 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 ...
Puzzled's user avatar
  • 8,832
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.
Sergey Zaitsev's user avatar
7 votes
0 answers
148 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 ...
Sprotte's user avatar
  • 1,045
7 votes
0 answers
188 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}(\...
Sophie M's user avatar
  • 675
7 votes
0 answers
340 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 ...
Niel de Beaudrap's user avatar
6 votes
2 answers
477 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 $\...
Turbo's user avatar
  • 13.6k
6 votes
1 answer
690 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 ...
Zur Luria's user avatar
  • 1,613
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$?
pnaky's user avatar
  • 61
6 votes
3 answers
439 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 ...
მამუკა ჯიბლაძე's user avatar
6 votes
1 answer
438 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!} \...
GGT's user avatar
  • 685
6 votes
0 answers
327 views

What is known about the $q$-analogue of the simplex?

I am interested in the field with one element. I am thus interested in combinatorial interpretations of the Gaussian binomial coefficients. Richard Stanley's "Enumerative combinatorics" mentions ...
Andrius Kulikauskas's user avatar