Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
504 questions
3
votes
0
answers
115
views
Counting monomials modulo prime numbers
The present quest emanates from this study by R. Stanley, including his recent MO question. Define the product (polynomials after full expansion)
$$I_n(x)=\prod_{i=1}^n(1+x^{F_{i+1}})$$
based on the ...
- 43.1k
2
votes
0
answers
80
views
Inequality on polynomials
Recall $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ and the Gaussian polynomial $\binom{a}{b}_q=\frac{[a]!_q}{[b]!_q[a-b]!_q}$ with $[0]!_q:=1$.
Given two polynomials $U(q)=\sum_k\alpha_kq^...
- 43.1k
3
votes
1
answer
158
views
Random covering of a set
Let $A$ be a set of $n$ elements. Let $S_1,\dots,S_n$ be independent $k$-element random subsets of $A$. What is the probability that $S_1,\dots, S_n$ evenly cover $A$, i.e. each element of $A$ belongs ...
- 1,608
1
vote
0
answers
67
views
Counting pieces when an object is cut n ways
I was reading a passage from an old essay by Martin Gardner on the calculus of finite differences, and it seems to me that there is more that can and should be said about seemingly anomalous values of ...
- 19.7k
4
votes
0
answers
154
views
How many choices for $(f,g)$ such that $f \circ g = h$?
For $a,b,c \in \mathbb{N}$ let $[a] := \{1,...,a\}$ and suppose a map $h: [a] \rightarrow [c]$ is given. How many choices $(f,g)$ for maps $f: [a] \rightarrow [b]$ and $g: [b] \rightarrow [c]$ are ...
- 1,295
4
votes
0
answers
205
views
Non-crossing and crossing bijection in higher genus
This is a follow-up question of my SO post I'll briefly mention it here.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...
- 685
12
votes
0
answers
629
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,654
0
votes
1
answer
116
views
Enumerating (i.e. generating one by one) matrices of given rank over a finite field
Let be given positive integers $m,n,r$, with $r \leq \min(m, n)$, and a finite field of $q$ elements $\mathbb{F}_q$.
I'm looking for an efficient algorithm to enumerate (i.e., generate one by one) all ...
- 43
2
votes
1
answer
217
views
$q$-binomial sum, slightly
Recall that $[n]_{q}!=\prod_{j=1}^n\frac{1-q^{j}}{1-q}$ and $\binom{n}k_{q}=\frac{[n]_{q}!}{[k]_{q}![n-k]_{q}!}$. Then the $q$-binomial theorem states
$$\sum_{k=0}^n\binom{n}k_qq^{\binom{k}2}=\prod_{k=...
- 43.1k
2
votes
0
answers
108
views
number of ways to cover an $m × n$ rectangle
Given a positive integer $k\ge2$, let be $f_k(m,n)$ the number of ways to cover an $m × n$ rectangle with $mn/k$ tiles ( $1×k$ or $k×1$)
$f_2(m,n)$ is kasteleyn formula
$f_k(m,n)$?
- 683
3
votes
0
answers
144
views
Counting integer partitions below some Young diagram
Question: Given positive, coprime integers $m<n$, consider the Young diagram $Y$ formed by the lattice points in the Cartesian plane lying below the line from $(0,0)$ to $(m,n)$ and within the ...
- 956
0
votes
1
answer
132
views
Seeking a bijective proof enumerating two partition sets: Part II
An integer partition is a sequence $\lambda=(\lambda_1\geq\lambda_2\geq\dotsb\geq\lambda_k)$ of positive integers, for some $k\geq1$. Consider the following two sets of partitions of $n$. Fix a ...
- 43.1k
2
votes
1
answer
181
views
Seeking a bijective proof enumerating two partition sets: Part I
An integer partition is a sequence $\lambda=(\lambda_1\geq\lambda_2\geq\dotsb\geq\lambda_k)$ of positive integers, for some $k\geq1$. Consider the following two sets of partitions of $n$. Fix a ...
- 43.1k
3
votes
1
answer
209
views
Representing PSET as species
In symbolic method, one often considers two operators on ordinary generating functions, namely
$$
\operatorname{PSET}F(x) = \exp\left(F(x)-\frac{F(x^2)}{2}+\frac{F(x^3)}{3}-\dots\right),
$$
and
$$
\...
- 1,171
3
votes
1
answer
226
views
Sums over permutations relates to permutations?
Consider the permutation group $\mathfrak{S}_n$ on $n$ letters $\{1,2,\dots,n\}$. Let $\iota=(1,2,3,\dots,n)\in\mathfrak{S}_n$ be the identity permutation in a $1$-line notation. Given $\pi, \rho\in\...
- 43.1k
4
votes
0
answers
238
views
Number of partitions of a number which don't include 1
I'm looking for two things.
One is an asymptotic formula for the number of partitions (number of ways of writing an integer as a sum of smaller positive integers) with the condition that 2 is the ...
- 141
3
votes
0
answers
129
views
Is counting Latin squares #P-complete?
I feel like I should know the answer to this. I did some Googling and didn't easily find the answer...
Question: Is counting Latin squares #P-complete?
Obviously the corresponding decision problem &...
- 1,327
2
votes
1
answer
141
views
Counting monomials and $q$-Catalan polynomials
Define $N(F)$ to be the number of monomials of a multi-variable polynomial $F$. For example $N(x^2y+3xy-y^5)=3$.
If $\mathbf{x}=(x_1,\dots,x_n)$ and $F_n(\mathbf{x})=\prod_{k=1}^n(x_1+\cdots+x_k)$ ...
- 43.1k
1
vote
1
answer
132
views
Rotational invariance assumed, what is the number of $r$-sided simple polygons that can be inscribed into an $n$-sided regular polygon?
When I say that an $r$-sided simple (i.e., not self-intersecting) polygon is inscribed into an $n$-sided regular polygon, I mean that every vertex of the simple $r$-gon is also a vertex of the regular ...
1
vote
3
answers
176
views
Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
let $\boldsymbol{X}_1,\,\dots,\,\boldsymbol{X}_n$ be well-ordered sets of positive values and $\mathcal{R}:=\lbrace\left(x_1,\,\dots,\,x_n\right)\rbrace = \boldsymbol{X}_1\times\,\dots\,\times\...
- 13.2k
10
votes
0
answers
429
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.8k
3
votes
0
answers
274
views
Inequalities for Motzkin polynomials
Let us denote by $M_{n}(t)$ the $n$-th Motzkin polynomial. It is defined by $M_1(t) = M_2(t) = 1$ and
$$ M_{n}(t) = \sum_{i=0}^{\lfloor n/2\rfloor } \frac{1}{n-1-i} \binom{n-1-i}{i} \binom{n-1}{i+1} t^...
- 1,889
6
votes
0
answers
365
views
Is this just a numerical accident or what?
In a complementary proof for a matrix determinant of $a_{i,j}=\binom{n-1+i}j$, raised by BillyJoe, I showed the more general evaluation
$$\det\left(\binom{i+p}{j+k-1}\right)_{1\leq i,j\leq m}
=\prod_{...
- 43.1k
4
votes
0
answers
163
views
An identity for Schur polynomials
Given a partition $\lambda$, the Schur polynomials can be defined, among many other ways, as
$$S_{\lambda}(\xi_1,\dots,\xi_a)=\frac{\det\left(\xi_i^{\lambda_j+a-j}\right)_{i,j=1}^a}{\det\left(\xi_i^{a-...
- 43.1k
4
votes
1
answer
221
views
Reference for a definition of Catalan numbers
The $l$-th Catalan number ${2l\choose l}\frac{1}{l+1}$ is equal
to the number of sequences $s_0,\ldots,s_{l+1}$ of length $l+2$ with the following
properties:
(1) $s_0=s_{l+1}=1$ and $s_1,\ldots,s_l$ ...
- 17.9k
1
vote
1
answer
139
views
A big list of Narayana-enumerated objects
By a Narayana-enumerated object I mean an object whose count is given by the Narayana number $N(n,k)=\frac{1}{n} {n \choose k} {n \choose k-1}$. Can you give me a reference to some good big list of ...
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
2
votes
0
answers
87
views
Reference request on Plancherel measure for partitions whose parts differing by more than $1$
Given an (unrestricted) integer partition $\lambda$ of $n$, let $f_{\lambda}$ denote the number of standard Young tableaux (SYT) of shape the Young diagram $Y(\lambda)$ of $\lambda$. Then,
$$\sum_{\...
- 43.1k
4
votes
1
answer
349
views
The fraction $\frac{g_{\mu}}{f_{\lambda}}$ is an integer
Let $\lambda=(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{\ell(\lambda)}>0)$ be an integer partition of $n\in\mathbb{N}$; i.e., $\lambda_1+\cdots+\lambda_{\ell(\lambda)}=n$.
One may now associate $...
- 43.1k
5
votes
1
answer
347
views
Counting monomials and the Catalan numbers
Given a multi-variable polynomial $F$, denote the number of monomials by $N(F)$. Take for instance, \begin{align*}N(x(x+y)+(x+y)^2-(x-y)^2)=N(x^2+5xy)&=2 \qquad \text{and} \\
N((x+z)(x+y)^2)=N(x^3 ...
- 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
0
votes
0
answers
91
views
Addition theorem for Schur function in multivariable
Working with the following problem Expansion in Schur function of negative binomial exponent
I need to find the expansion of
$$ s_{\lambda}(x_1 + y , x_2 +y, \ldots, x_n +y)$$
in terms of schur ...
- 685
3
votes
1
answer
220
views
Agreement between two sets of data on partitions
Let $\lambda=(\lambda_1,\lambda_2,\dotsc,\lambda_{\ell(\lambda)})$ be an integer partition of positive numbers where $\ell(\lambda)$ is the length of the partition. One may associate a Ferrer diagram ...
- 43.1k
3
votes
1
answer
295
views
Generating function for "descents" and "cycle-types", in tandem
This question is inspired but not directly related to this recent Stanley's MO post.
The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ (the symmetric group on $\{1,\dots,n\}$) ...
- 43.1k
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
4
votes
1
answer
376
views
Counting permutations with a fixed number of descents and an extra condition
I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...
- 1,889
7
votes
0
answers
152
views
Inequality of product of discrete cosines
Let $k,a,b,c$ be odd positive integers. Consider the following inequality:
$$
\sum_{x,y \in [k]} \cos^a\bigg(\frac{2\pi}{k}\cdot x\bigg) \cdot \cos^b\bigg(\frac{2\pi}{k}\cdot y\bigg) \cdot \cos^c\bigg(...
- 71
3
votes
0
answers
135
views
Expansion in Schur function of negative binomial exponent
I want to know if there exist a known expansion or can be derived of the polynomial
$$ \prod_{i=1}^{m}\prod_{j= 1}^{n}(1-z(x_i + y_i))^{-w} \tag{*}$$
in terms of Schur function. That is asking for (*) ...
- 685
4
votes
1
answer
263
views
A refinment of Beck's conjecture
Let $\mathcal{O}(n)$ and $\mathcal{D}(n)$ denote the set of all integer partitions of $n$ into odd parts and distinct parts, respectively. Let $o(n)=\#\mathcal{O}(n)$ and $d(n)=\#\mathcal{D}(n)$. ...
- 43.1k
2
votes
1
answer
177
views
Another combinatorial identity
Is it true that
$$\sum_{r=0}^p \sum_{i=0}^r a_{n,p,r,i}=0$$
for all natural $n$ and all natural $p\ge2n$, where
$$a_{n,p,r,i}:=\frac{(-1)^r (n+p-r-1)! (n p-i (r-i))}{i!(r-i)! (n-i)!
(p-r+i)! (n-r+i)! ...
- 128k
2
votes
1
answer
199
views
Sequence of monotone tuples and permutation condition for rotation
I was doing some counting in $S_n$ symmetric group I encountered the following problem, which also someway related to central factorial number.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the ...
- 685
7
votes
1
answer
156
views
Is there an infinite combinatorics of common transseries expansions?
By now there is a rich understanding of generating functions in combinatorics, and the way that operations in power series are 'shadows' of richer constructions on combinatorial objects. This lifting ...
0
votes
1
answer
148
views
What is this numerically-generated function?
This question is an "outgrowth" of https://math.stackexchange.com/questions/4380919/ which led to a numerically-generated two-parameter function $f_b(n)$, where $b$ is the number base $2,3,4,...
- 103
4
votes
1
answer
329
views
Enumerating subsets with no triple appearing together more than once
This question is motivated by a real-world application related to an art project that involves displaying images, but my search hit a dead end after finding the wikipage about Kirkman systems (other ...
- 7,831
6
votes
0
answers
276
views
Power law correction factor in tree enumeration via naïve division
It is a theorem of Otter, building on fundamental work of Pólya, that the number of unlabeled trees on $n$ vertices is $\approx C \alpha^{n} n^{-5/2}$, where $C = 0.534\ldots$ and $\alpha = 2.955\...
- 24.2k
2
votes
0
answers
413
views
A (really!) cute identity between product of binomials
As an off-shot of my earlier MO question, I have found a "really cute" identity. The connection is revealed in the limit $q\rightarrow 1$.
So, I would like to ask:
QUESTION. Is there a ...
- 43.1k
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
4
votes
1
answer
225
views
Integer-valued polynomials from Pólya counting
Let finite group $G$ act on a finite set $X$ and hence on colorings $Y^X$, where $Y=\{1,2,\ldots,k\}$ is a set of colors. The Burnside-Pólya-Redfield-etc. counting theorem says that the number of ...
- 24.2k
6
votes
1
answer
260
views
Tanglegrams and functional equations of M. Somos
Recent references on the matter at hand include, a lecture slide The Konvalinka-Amdeberhan conjecture
and plethystic inverses and a preprint on Counting tanglegrams with species by I. Gessel; the ...
- 43.1k
2
votes
2
answers
126
views
Regular pseudographs
Is there a counting known for $3$-regular (or any $n$-regular) pseudo graph of a given order $|V|$? An asymptotic result for connected (or disconnected) graphs is good enough. It would be even better ...
- 397