Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
503 questions
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 ...
- 188k
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 ...
- 33.8k
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.2k
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.2k
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 $...
- 5,590
12
votes
1
answer
595
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. ...
- 24.2k
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
2
answers
463
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-...
- 1,091
7
votes
3
answers
2k
views
Combinatorial counting with symmetry
Let $A$ be a set of objects where $|A|=n$. We want to count all the possible ways that we can arrange these objects into $n$ bags with exactly $n$ objects in each. We can reuse any object, however, no ...
- 17k
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 ...
- 7,226
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\}$) ...
- 17k
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 ...
- 43.2k
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(...
- 6,357
10
votes
0
answers
2k
views
Number of rectangles in an n-by-n grid of points
I am seeking a formula for the number of rectangles with vertices belonging to an $n \times n$ square grid of points. This is sequence A085582 in the OEIS. Note that the grid in question has $n^2$ ...
- 856
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)$. ...
- 24.2k
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)! ...
- 7,226
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 ...
- 34.3k
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
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,...
- 34.3k
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 ...
- 34.3k
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.2k
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$ ...
- 1,989
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
1
vote
1
answer
204
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 ...
- 43.2k
2
votes
3
answers
742
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)...
- 3,255
1
vote
1
answer
166
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=...
- 17k
5
votes
1
answer
179
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 ...
- 128k
12
votes
1
answer
405
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}...
- 12.9k
3
votes
3
answers
396
views
Chebyshev polynomials and ballot numbers
I have asked this question a short time ago on mathstackexchange, but it has already fallen into the abyss of answered and uncommented questions. So I take the risk to ask it on mathoverflow.
Playing ...
- 17k
1
vote
0
answers
203
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-...
- 43.2k
2
votes
0
answers
50
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 ...
- 13.2k
15
votes
2
answers
1k
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 ...
- 1,906
9
votes
2
answers
1k
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)...
- 43.2k
10
votes
1
answer
358
views
Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity
This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments ...
- 1,446
6
votes
1
answer
281
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}$....
- 34.3k
14
votes
1
answer
647
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 ...
- 5,590
2
votes
0
answers
55
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 ...
- 847
0
votes
0
answers
75
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-...
- 12.9k
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.2k
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
1
vote
0
answers
85
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 ...
- 81
6
votes
1
answer
422
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=...
- 109k
6
votes
1
answer
773
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 ...
- 43.2k
5
votes
3
answers
758
views
How to prove the combinatorial identity $\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}k2^k=2^\ell n\binom{2n-\ell}{n}$ for $n\ge\ell\ge0$?
With the aid of the simple identity
\begin{equation*}
\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{k}}=2^n
\end{equation*}
in Item (1.79) on page 35 of the monograph
R. Sprugnoli, Riordan Array Proofs of ...
- 1,091
2
votes
0
answers
143
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 ...
- 867
4
votes
1
answer
298
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 $\...
- 43.2k
3
votes
1
answer
256
views
Two questions about Bell polynomials
In my research in Quantum Field Theory, I have encountered two questions that involve partial Bell polynomials:
Let $u$ and $x_i$ be indeterminates. I have checked that the following conjectured ...
- 34.3k
5
votes
2
answers
1k
views
Stirling numbers of the second kind with maximum part size
The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...
- 549