All Questions
Tagged with enumerative-combinatorics generating-functions
28 questions
4
votes
1
answer
406
views
Inverse relationship between Stirling numbers of the first and second kind via generating functions
In combinatorics, a well-known result is that the matrix formed by the Stirling numbers of the second kind $\left(S(n,k)\right)_{n,k\geq 0}$ and the matrix of the signed Stirling numbers of the first ...
- 151
9
votes
2
answers
344
views
Counting $m\times n$ $\bigl({1\atop1}{1\atop0}\bigr)$-free $(0,1)$-matrices
Let $G_{m,n}$ denote the number of $m\times n$ $(0,1)$-matrices that avoid the submatrix $\bigl({1\atop1}{1\atop0}\bigr)$. (Submatrices need not be contiguous.) Here are some small values (not yet on ...
- 667
7
votes
1
answer
503
views
Combinatorial consequences of de Branges's Theorem?
I'm usually not a proponent of the mentality “here is a tool, what results can we prove with it?” (as I prefer to start at the other end with a well-motivated problem), but this famously entertaining ...
- 191
3
votes
0
answers
222
views
Number of partitions of set restricted by sum of square of part size
Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\...
- 405
4
votes
0
answers
211
views
Sum $f(n_1,n_2,\ldots,n_k) 1^{n_1} 2^{n_2} \ldots k^{n_k}$ over partitions
Use the notation $(n_1,n_2,\ldots,n_k) \vdash n$ to denote that $(n_1,n_2,\ldots,n_k)$ is a partition of the positive integer $n$, that is, $n_1+n_2+\ldots+n_k = n$ and $n_1 \ge n_2 \ge \ldots \ge n_k ...
- 261
2
votes
0
answers
178
views
Which combinatorial class do noncrossing partitions belong to?
Let $n$ be a nonnegative integer. The set $\lbrace 1,2,\ldots, n\rbrace$ is partitioned into blocks, with $p\left(n\right)$ possibilities (e.g., for permutations $p\left(n\right)=n!).$ For each block ...
- 329
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
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
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
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
20
votes
4
answers
2k
views
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Is there a non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
It is a nice exercise with rational generating functions (or equivalently, ...
- 24.2k
3
votes
0
answers
137
views
Positivity of sequences
Totally positive sequences $\lbrace a_n\rbrace_{n\in\mathbb{Z}}$ are defined as those such that the Töplitz matrix $A_{ij}=a_{i-j}$ is totally positive (all its minors are non-negative). An ...
10
votes
1
answer
491
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$ ...
- 5,612
2
votes
0
answers
119
views
Counting the number of simple labelled bipartite graphs 𝐺𝑛,𝑚 with 𝑘 edges such that 𝑑1 vertices have degree 1
I have tried to count the number of simple labelled bipartite graphs $G_{n,m}$ with $k$ edges such that $d_1$ vertices have degree 1.
Has this problem been studied?
So far the only related paper I ...
- 21
1
vote
0
answers
134
views
Counting unions of unlabelled connected graphs
My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...
- 183
10
votes
1
answer
357
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 ...
user82537
0
votes
1
answer
61
views
Ordered $m$-tuples with fixed number of changes
Given $1\leq k\leq m$, $2\leq d\leq c i\ln i$ and $2\leq i\leq c'\ln(mi\ln i)$ at some $c,c'>0$ how many sequences (lower and upper bounds) are of form $$z_1,\dots,z_m$$ on the condition that
$$0\...
- 1,826
2
votes
0
answers
66
views
Annihilator of the of the generating function not holonomic
The following is a generating function in $x,h$ with infinite parameters
$q_1,q_2\ldots,$ and $w_1, w_2,\ldots$.
$$\Psi(x, h)= \sum_{d=0}^{\infty} s_{(d)} (q_1, q_2, \ldots) \exp \bigg( \sum_{r=1}^{\...
- 685
7
votes
1
answer
203
views
Sufficient conditions for the coefficients of a generating function to dominate those of its square
Let $f(z)$ be a generating function (so in particular, its power series coefficients are nonnegative). I am interested in conditions which would ensure that for every $n$, the coefficient of $z^n$ in $...
- 2,339
8
votes
1
answer
344
views
Bijective proof of formula for rooted binary forests
For $n\ge 1$, let $f(n)$ be the number of rooted complete (unordered) binary trees with $n$ leaves labeled from $1$ to $n$ ("complete binary" means that every vertex has either $0$ or $2$ children and ...
- 82.6k
5
votes
1
answer
177
views
an algebra generated by some known series
Denote the e.g.f. for the number of (unordered) rooted labeled trees on $n$ nodes by
$$\Phi(x)=\sum_{n\geq1}\frac{n^{n-1}}{n!}x^n.$$
And, the related series $\Psi(x)=\sum_{n\geq1}\frac{n^n}{n!}x^n$. ...
- 43.1k
6
votes
2
answers
2k
views
Convergence issues with infinite product of formal series
Question first:
Show that if $s_1 < s_2 < \dots$ is an increasing sequence of positive integers and $P(x)$ is a nonzero polynomial then we cannot have
$$ P(x) \equiv \prod_{j=1}^\infty (1 - ...
- 1,207
2
votes
0
answers
187
views
Direct proof that a certain generating function is D-finite
Consider the set $T^{2,3}_n$ of all non-planar rooted trees with $n$ leaves labelled by $1,2,\ldots,n$ where each internal vertex can have two or three children. If we think of the binary / ternary ...
- 16.9k
15
votes
2
answers
363
views
Generating functions for objects with irrational sizes
A problem I'm investigating concerns a combinatorial class in which the 'atoms' have irrational sizes. It seems likely that this is something that has been considered before, but I haven't been able ...
- 674
7
votes
2
answers
448
views
What is the number of noncrossing acyclic digraphs?
A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...
- 195
1
vote
1
answer
304
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. ...
- 13k
0
votes
1
answer
312
views
Enumeration Result [closed]
Hi
I have a very soft question:
What exactly is the definition of an enumeration result?
Let say I want to enumerate some combinatorial structure and I came up with an equation for a generating ...
- 11
21
votes
1
answer
1k
views
A strange sum over bipartite graphs
While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
- 37.7k