Questions tagged [enumerative-combinatorics]

Filter by
Sorted by
Tagged with
-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$. ...
user avatar
  • 99
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 ...
user avatar
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 ...
user avatar
  • 383
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_{\...
user avatar
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 $...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 621
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 ...
user avatar
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\}$) ...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 1,716
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(...
user avatar
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 (*) ...
user avatar
  • 621
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)$. ...
user avatar
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)! ...
user avatar
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 ...
user avatar
  • 621
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 ...
user avatar
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,...
user avatar
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 ...
user avatar
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\...
user avatar
  • 18.8k
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 18.8k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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)...
user avatar
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=...
user avatar
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 ...
user avatar
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}...
user avatar
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-...
user avatar
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 ...
user avatar
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 ...
user avatar
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)...
user avatar
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_{\...
user avatar
  • 621
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/...
user avatar
  • 12.8k
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}$....
user avatar
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 ...
user avatar
  • 18.8k
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 ...
user avatar
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 ...
user avatar
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-...
user avatar
  • 390
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-...
user avatar
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 ...
user avatar
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}(\...
user avatar
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 ...
user avatar
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 ...
user avatar
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=...
user avatar
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 ...
user avatar
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 $\...
user avatar

1
2 3 4 5
8