# Questions tagged [enumerative-combinatorics]

The enumerative-combinatorics tag has no usage guidance.

383
questions

-5
votes

1
answer

128
views

### Proving an identity involving polynomial roots [closed]

I was working on a combinatorics problem and noticed that the following identity holds, which was also necessary to solve the problem.
Consider the cubic: $x^3-2x+z=0$ and the roots are $a,b,c$. ...

1
vote

1
answer

75
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 ...

6
votes

0
answers

112
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 ...

2
votes

0
answers

77
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_{\...

4
votes

1
answer

261
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 $...

5
votes

1
answer

300
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 ...

11
votes

1
answer

429
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. ...

0
votes

0
answers

69
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 ...

3
votes

1
answer

196
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 ...

3
votes

1
answer

218
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\}$) ...

9
votes

0
answers

286
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 ...

2
votes

0
answers

119
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 \...

7
votes

0
answers

120
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(...

3
votes

0
answers

122
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 (*) ...

4
votes

1
answer

239
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)$. ...

2
votes

1
answer

149
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)! ...

1
vote

1
answer

143
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 ...

5
votes

0
answers

68
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

121
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,...

4
votes

1
answer

308
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 ...

6
votes

0
answers

260
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\...

2
votes

0
answers

383
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 ...

16
votes

1
answer

905
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$ ...

4
votes

1
answer

181
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 ...

6
votes

1
answer

238
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 ...

2
votes

2
answers

95
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 ...

1
vote

1
answer

158
views

### Interpret this matrix and its determinant

Let $n\geq1$ be an integer. Take the matrix $M(n)$, with entries, $M_{i,j}(n)=\sin\left(\frac{(i+j)\pi}2\right)$ if $i\neq j$ and $M_{i,i}(n)=x_i$.
I wish to ask (this question has been modified from ...

3
votes

3
answers

658
views

### Asking for a proof for a sum of products of binomials: an "interesting" identity?

The following identity must have received alternative proofs, including a combinatorial argument by David Callan as found at Bijections for the Identity $4^n = \sum_{k = 0}^n \binom{2k}k\binom{2(n - k)...

0
votes

1
answer

95
views

### Confusion in definition of class of structures and combinatorial class [closed]

I understand that a combinatorial class $\mathcal{A}$ is a set of objects, with a function of size $\lvert\cdot\rvert_{\mathcal{A}}:\mathcal{A}\to \mathbb{N}$. With objects of size $n$: $\mathcal{A}_n=...

5
votes

1
answer

160
views

### A common combinatorial description for a certain type of recurrences

For integer-valued sequences $(x_n)_{n=0}^\infty$, consider recurrences of the form
$$x_n=ax_{n-1}+(bn+c)x_{n-2} \tag{$*$}\label{star}$$
for $n\ge2$, where $a,b,c$ are integers.
There seem to be many ...

10
votes

1
answer

340
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}...

1
vote

0
answers

183
views

### Generalizing "partition into odd parts=partition into distinct parts"?

The number of partitions into distinct parts is known to agree with the number of partitions with odd parts. For instance, this follows from
$$\prod_{k=1}^{\infty}(1+q^k)=\prod_{n=1}^{\infty}\frac1{1-...

2
votes

0
answers

45
views

### Calculating permanents via Branch and Bound

Permanents can be interpreted as counting directed cycle covers of an asymmetric graph with unit cost edge weights.
That interpretation leads to a branch and bound algorithm for calculating the ...

15
votes

2
answers

866
views

### A rather curious identity on sums over triple binomial terms

While exploring the Baxter sequences from my earlier MO post, I obtained a rather curious identity (not listed on OEIS either). I usually try to employ the Wilf-Zeilberger (WZ) algorithm to justify ...

8
votes

2
answers

953
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)...

5
votes

1
answer

559
views

### Expressing symmetric function in power-sum basis

I am trying to prove the following identity
\begin{equation}
\prod_{i=1}^{m}(1-x_{i}z)^{-u}\prod_{j=1}^{n}(1-y_{i}z)^{-v} \prod_{i=1}^{m}\prod_{j=1}^{n}(1-(x_i +y_j)z)^{-w}\\ = \sum_{\lambda, \mu}c_{\...

0
votes

0
answers

27
views

### Volume interpretation of number of spanning trees in planar graphs

The number of spanning trees of a planar graph is $DET$ complete where $DET$ class is given in https://complexityzoo.net/Complexity_Zoo:D#det by corollary $21$ in https://mbraverm.princeton.edu/files/...

6
votes

1
answer

238
views

### Another generalization of parity of Catalan numbers

Recently, a question by T. Amdeberhan gathered up many enjoyable proofs that a Catalan number $C_n$ is odd if and only if $n=2^r-1$.
Noam D. Elkies' answer considered $F=\sum_{n=0}^\infty C_n x^{n+1}$....

11
votes

1
answer

287
views

### Bijective proof of recurrence for rooted unlabeled trees

Would've been a better question for Christmas than Thanksgiving, but alas...
Let $t_n$ denote the number of rooted, unlabeled trees on $n$ vertices (OEIS A000081). These are the isomorphism classes of ...

2
votes

0
answers

46
views

### Compact expression for triples of subsets with total sum zero

I am looking whether there is any compact way to write the following: Suppose we have an abelian group $G$. For a subset $A\subset G$ let $S_A$ be the sum of its elements. I want to find the number of ...

15
votes

4
answers

2k
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 ...

3
votes

2
answers

308
views

### Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$

Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-...

0
votes

0
answers

71
views

### Objects equinumerous with $3$-ary partitions?

There is a concept of the so-called RP-compositions of an integer discussed by K. Q. Ji and H. S. Wilf in Extreme palindromes. They proved the following result too:
Theorem. The number of RP-...

13
votes

2
answers

769
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 ...

7
votes

0
answers

166
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}(\...

1
vote

0
answers

77
views

### Varieties of trees with logarithmic degree function

I am interested in varieties of trees with a logarithmic degree function. I am currently looking at Bergeron, Flajolet, and Salvy's work "Varieties of increasing trees." They discuss exactly ...

6
votes

1
answer

273
views

### Sum of squares of multinomial coefficients

It is well known that the sum of squares of all binomial coefficients ${n\choose k}$ with a fixed $n$ is ${2n\choose n}$. That is, $\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}$.
But do we know what ...

6
votes

1
answer

391
views

### Constant term extraction using combinatorial Nullstellensatz

$\DeclareMathOperator\CT{CT}$Given a Laurent polynomial $g$, let $\CT(g)$ denote its constant term.
Consider the specific Laurent polynomial
$$f_n(x_1,\dots,x_r)=\left(1+\prod_{j=1}^r(1+x_j)+\prod_{j=...

2
votes

0
answers

101
views

### Enumerative geometry and restricted plane partitions

Donaldson-Thomas theory is an enumerative theory for virtual counts of ideal sheaves (with trivial determinant) of the structural sheaf $\mathcal{O}_{X}$ of some smooth projective manifold $X$.
There ...

4
votes

1
answer

247
views

### Enumeration of dominated Dyck paths

Using horizontal steps $(1,0)$ and vertical steps $(0,-1)$, consider the lattice paths starting from $(0,q)$ and reaching $(p,0)$ with $p$ horizontal and $q$ vertical steps. The set of such paths $\...