All Questions
Tagged with co.combinatorics generating-functions
72 questions with no upvoted or accepted answers
15
votes
0
answers
271
views
Lie theoretic meaning to $e^{\text{cycle}} = \text{permutation}$?
It is well known that exponentiating the EGF(exponential generating function) for cycles gives the EGF for permutations: link here. Usually summarized under the catchy slogan ...
- 1,221
15
votes
0
answers
767
views
Wherefore art thou a Borcherds Product?
This question essentially asks how can one recognize (or rule out) that a generating function of combinatorial origin may be given as a Borcherds type product. I'll start with a motivational example: ...
- 85.6k
14
votes
0
answers
276
views
A conjectured rational generating function
In regard to my question here, let $G_n$
be a sequence of positive integers satisfying
$\lim_{n\to\infty}G_n=\infty$, such that the generating function
$\sum_{n\geq 1} G_nx^n$ is rational. Let
$$ P_n(...
- 50.8k
13
votes
0
answers
1k
views
Generalization of Cauchy's identity
Let $ s_{\lambda} $ be the Schur function associated to the partition $ \lambda $.
Cauchy's identity (as in Macdonald) states that
$$
\sum_{\lambda} s_{\lambda}(X)s_{\lambda}(Y) = \prod_{i,j}(1-...
- 151
8
votes
0
answers
106
views
Number of occurrences of certain generators in expressions in Coxeter groups
Let $W$ be a Coxeter group (finite or infinite) with (finite) set $S$ of Coxeter generators, and let $I \subseteq S$ be some subset. If $w\in W$ then I call $m_I(w)$ the minimum total number of ...
- 32.5k
7
votes
0
answers
162
views
A differential equation and recurrence related to P-partitions
I am interested in polynomials $G_n(z)$ defined by the recurrence
$$G_{n+1}(z) - 2G_n(z) + (1-nz)G_{n-1}(z)=0$$
for $n\ge1$ with the initial values $G_0(z) = 1$ and $G_1(z) = 1$.
The next few values ...
- 17k
7
votes
0
answers
279
views
A conjecture about Hankel determinants of path generating functions
Let $a_{n,k}=a_{n,k}(x,c)$ be the generating function $\sum_P w(P),$ where $P$ runs over all paths from $(0,0)$ to $(n,k)$ consisting of horizontal steps $(1,0)$, up-steps $(1,1)$ and down-steps $(1,-...
- 5,622
7
votes
0
answers
332
views
Estimating the alternating sum $\sum_{j \ge 1} (-1)^j e^{-j^2} j^k$
I have been trying to get a lower bound on the following alternating sum but without much success:
$$
\sum_{j=1}^T (-1)^j e^{-j^2} j^k .
$$
For small values of $k$, this is easy because the first term ...
- 381
7
votes
0
answers
174
views
A diagonal generating function for Fibonacci: Part II
In my earlier MO question, I mentioned although we have for the Fibonacci numbers that
$$F_n=[x^n]\left(\frac1{1-x-x^2}\right),$$
is there a function $F(x)$ such that $F_n=[x^n]\left(F(x)\right)^n$?
...
- 43.2k
7
votes
0
answers
530
views
Can we define the Mandelbrot set in terms of the generating function of the Catalan numbers?
For each complex number $c$, define $P_{0}(c)=0$ and $P_{n+1}(c) = (P_{n}(c))^{2} + c$ . The Mandelbrot set is the set of complex numbers c for which $|P_{n}(c)|$ stays bounded as $n\rightarrow \...
6
votes
0
answers
207
views
Parameter independence of Stanley's "content formula". Why?
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R. Stanley remarked following ...
- 43.2k
6
votes
0
answers
184
views
A class of symmetric functions
When attacking a symmetric problem via an asymmetric method, I encountered the following function: $$U_2(n, m) = \sum_{a = 0}^n\binom na (2^a + 2^{n - a})^m.$$
It is easy to see that this function is ...
- 3,432
6
votes
0
answers
101
views
Number of Dyck paths up to stable equivalence
Acyclic (connected) Nakayama algebras can be identified with Dyck paths via their top boundary Auslander-Reiten quivers.
Now two Nakayama algebras $A$ and $B$ should be stable equivalent in case ...
- 26.5k
5
votes
0
answers
105
views
Hooks, monomers, dimers and Young diagrams: Part II
As promised, I've upgraded my last question.
Consider the $k$-by-$n$ partition $\lambda_n=(n,\dots,n)$ and its corresponding Young diagram $Y_{n,k}$, which is a $k\times n$ rectangle of cells. Now, ...
- 43.2k
5
votes
0
answers
170
views
operation on Ord., Exp., Dri. generating functions
The ordinary, exponential and Dirichlet generating functions for a sequence $\{a_n\}_{n\geq0}$ are given (at least on the formal side), respectively, by
$$F(x)=\sum_{n\geq0}a_nx^n, \qquad E(x)=\sum_{n\...
- 43.2k
5
votes
0
answers
208
views
Asymptotics and combinatorics
Wright's expansion of
$$
(1-z)^b\exp[A/(1-z)^c], \text{for } A > 0, 0<c<1\tag{1}
$$
is, in the words of the late, great Mark Kac "well known to those that know it well".
(See, for example, ...
- 51
5
votes
0
answers
345
views
When does a triangle of numbers have a zero row sum?
Suppose we have a triangle of numbers defined by the recurrence relation
$$\left| n \atop k \right| = f(n,k) \left| n-1 \atop k \right| +g(n,k) \left| n-1 \atop k-1 \right| + [n=k=0],$$
for some ...
- 3,283
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
4
votes
0
answers
118
views
Something (which might be called multi-continued fraction) for the A112487
Let $a(n)$ be A112487 i.e. an integer sequence with exponential generating function
$$
A(x)=\exp\left(\int (A(x)+A(x)^2)\,dx\right), \\
A(0)=1
$$
However, the definition in the name of the sequence is
...
- 4,938
4
votes
0
answers
208
views
Extract this constant term
Given a Laurent polynomial $F$ in the variables $\mathbf{t}=(t_1,\dots,t_n)$, let $CT_{\vec{\mathbf{t}}}\,F$ denote its constant term.
For example, $CT_{t_1,t_2}((8t_1-\frac1{3t_1t_2})(5t_1t_2+t_2^2+\...
- 43.2k
4
votes
0
answers
414
views
Explicit formula for tournament sequence
I am looking for an explicit formula for a sequence. The sequence is generated as follows:
There is a tournament with $10$ teams. In the beginning, all teams have a 0-0 win-loss record. The teams are ...
- 41
4
votes
0
answers
144
views
Generalized Catalan generating series
Let
$$
\mathscr{B}_k(z) = \sum_{n\geq 0}{kn+1\choose n}\frac{1}{kn+1}z^n\,,
$$
then it is well known that
$$
\tag{1}\label{1}
\text{log}\mathscr{B}_k(z)= \sum_{n\geq 1}{kn\choose n}\frac{1}{kn}z^n\,.
$...
- 988
4
votes
0
answers
154
views
Hooks, monomers, dimers and Young diagrams: Part I
Following Richard Stanley's pointers regarding my earlier MO question, I decided to "scale-down" the problem and add a slight "twist" to it.
Consider the one-line partition $\lambda_n=(n)$ and its ...
- 43.2k
4
votes
0
answers
312
views
Unexpected result related to open question whether $\sum x^{n^3}$ can satisfy an ADE
In Stanley EC2, it is an open question whether $\sum b_nx^{n^3}$ can satisfy an ADE. Stanley remarks that if this is true then it leads to a "completely unexpected result about representing integers ...
- 220
3
votes
0
answers
70
views
$R$-recursion for the A249833 (similar to A235129)
Let $a(n)$ be A249833 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x) = 1 + \int A(x) + (A(x))^2\log A(x)\,dx
$$
The sequence begins with
$$
1, 1, 2, 7, ...
- 4,938
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
3
votes
0
answers
315
views
When does the Taylor coefficient of $e^{\sin x}$ vanish?
If $f(x)=\frac{a_1}{1!}x+\frac{a_2}{2!}x^2+\frac{a_3}{3!}x^3+\frac{a_4}{4!}x^4+\cdots$ is an exponential generating function for $\{a_k\}_{k\geq1}$ then
$$e^{f(x)}=1+\frac{a_1}{1!}x+\frac{a_1^2+a_2}{2!...
- 43.2k
3
votes
0
answers
111
views
Irreducible dimensions generating function for Lie algebra $\mathfrak{sl}_n$
Let $\lambda = \sum_{i = 1}^{n - 1} m_i \omega_i$ be the highest weight of irreducible representation $V(\lambda)$ of Lie algebra $\mathfrak{sl}_n$. As we know from the Weyl formula,
$$\dim V(\lambda) ...
- 645
3
votes
0
answers
123
views
$q$-series for the number of rectangles in a square lattice
Given a partition $\lambda\vdash n$ of $n$, look at its Young diagram $Y_{\lambda}$. Let $a(\lambda)$ be the number of squares (of all sizes) in $Y_{\lambda}$. For example, if $n=4$ then $a(4)=4, a(3,...
- 43.2k
3
votes
0
answers
209
views
Two kinds of generating functions
Sorry for a possibly off-the-topic question, but I am afraid to gain the necessary overview to give an answer (supposed the question is not ill-posed) is beyond my capabilities.
In the course of ...
- 9,720
3
votes
0
answers
312
views
Enumerating a class of polynomials
How many equivalence classes of $\Bbb F_2[x,y]$ polynomials with $x$ degree $n_x$ and $y$ degree $n_y$ are there such that each $y^i$ coefficient (polynomial in $\Bbb Z[x]$) is distinct and $x^i$ ...
user76479
3
votes
0
answers
467
views
Solving a doubly exponential generating function
I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...
- 396
3
votes
0
answers
204
views
closure properties of q-differential equations
I am interested in q-differential equations of the form
$p(f(z), f(qz),\dots,f(q^kz))=0$
where $p$ is a polynomial and $k$ an nonnegative integer. I wonder about the closure properties of the class ...
- 5,822
2
votes
0
answers
51
views
Recursion for A129179 similar to recursion for Pascal's triangle
Let $T(n,k)$ be A129179 (i.e., triangle read by rows: $T(n, k)$ is the number of Schroeder paths of semilength $n$ such that the area between the $x$-axis and the path is $k$ ($n \geqslant 0, 0 \...
- 4,938
2
votes
0
answers
64
views
On a $\sum\limits_{n=0}^{\infty}c_n x^n=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x^k)$ (slightly different question)
Please note that this question differs from one of the previous questions of mine.
Let $f(n)$ be an arbitrary function with integer values.
Let $c_n$ be an arbitrary integer sequence.
Let $a(n)$ be ...
- 4,938
2
votes
0
answers
103
views
$R$-recursion for the A235129
Let $a(n)$ be A235129 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A'(x) = 1 + A(x)\exp(A(x))
$$
The sequence begins with
$$
1, 1, 3, 12, 64, 424, 3358, ...
- 4,938
2
votes
0
answers
110
views
Asking for a generating function for an arithmetic sequence
For fixed integer $n\geq1$, let $c_m(n)$ be the number of divisors $d$ of $m$ such that $n<d\leq 2n$. Here is an experimental generating function for which I ask:
QUESTION. Is this true?
$$\sum_{m\...
- 43.2k
2
votes
0
answers
117
views
A multi-variable "Fibonacci polynomial"?
There is a tremendous literature on the Fibonacci sequence, including its polynomial analogue $F_{-1}=0, F_0=1$ and
$$F_n(x)=xF_{n-1}(x)+F_{n-2} \qquad \text{for $n\geq1$}.$$
What I have found is the ...
- 43.2k
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
2
votes
0
answers
98
views
Two-variable generating functions over coprime pairs
I am studying a sequence $(\alpha_{p,q})$ indexed by a pair of coprime integers; this sequence arises naturally in the study of a particular set of spaces in geometric topology, but unfortunately the ...
2
votes
0
answers
337
views
Inverse of partial sums of general harmonic series
I would like to understand better the scaling of the following summation as a function of $r$ and $p > 1$:
$$
S_r(p) := \sum_{m=1}^{r} \left( \sum_{k=r-m+1}^{r} \left( \frac{k^q}{\sum_{k'=1}^{r}...
- 199
2
votes
0
answers
154
views
Unrestricting The Parameters of a Functional Equation
Good evening. I am looking into methods of generalization of Bernoulli polynomials. First, define
$$\Phi_{N,k}(x)=\frac{1}{N}\sum_{j=0}^{N-1}\omega_N^{-jk}\exp\left(\omega_N^jx\right)$$
where $\...
2
votes
0
answers
103
views
Lagrangean equations for the generating function of quadrangulations
Let $M(z)$ be the generating function of edge-rooted connected quadrangulations, with $z$ marking the number of edges. I derived the following Lagrangean equations for $M(z)$:
$$M(z) = \psi(L(z)),~\...
- 21
1
vote
0
answers
57
views
Step back step forward algorithm for A108442
Let $a(n)$ be A108442. Here generating function is $\frac{1}{1-zA(z)}$ where
$$
A(z) = 1 + z(A(z))^2 + z(A(z))^3.
$$
Also
$$
a(n) = \sum\limits_{k=1}^{n}\frac{k}{2n-k}\sum\limits_{i=0}^{n-k} \binom{2n-...
- 4,938
1
vote
0
answers
47
views
Harmonic numbers multifold convolution
I have a question. If I define the multifold convolution of Harmonic numbers as
$\sum_{n_1=1}^{\infty} \cdots \sum_{n_k=1}^{\infty} H_{n_1} \cdots H_{n_k} \mathbf{1}_{\{n\}}(n_1+\dots+n_k)$
for the $k$...
- 471
1
vote
0
answers
82
views
Generating functions related to generating function of Catalan numbers
Let $C_n$ be A000108 (i.e., Catalan numbers). Here generating function is $C(x)$ such that
$$
C(x) = \frac{1-\sqrt{1-4x}}{2x}.
$$
Let $a(n)$ be an integer sequence with generating function $A(x)$ such ...
- 4,938
1
vote
0
answers
63
views
On a A162326 and vector $\nu$ of length $n$
Let $a(n)$ be A162326. Here
$$
a(n) = \frac{1}{n}(2(5n-7)a(n-1) - 9(n-2)a(n-2)), \\
a(0) = a(1) = 1.
$$
Also ordinary generating function is
$$
\frac{5 - \sqrt{\frac{1-9x}{1-x}}}{4}.
$$
Let $b(n)$ be $...
- 4,938
1
vote
0
answers
49
views
$R$-recursion for the A036765
Let $a(n)$ be A036765 i.e. number of ordered rooted trees with $n$ non-root nodes and all outdegrees $\leqslant 3$. Here
$$
a(n) = \frac{1}{n+1}\sum\limits_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\...
- 4,938
1
vote
0
answers
89
views
Suitable recursion for the A234289
Let $a(n)$ be A234289 i.e. integer sequence with exponential generating function
$$
A(x)=1+A(x)^2\int \frac{1}{A(x)}\,dx
$$
The sequence begins with
$$
1, 1, 3, 17, 147, 1729, 25827, 468593, 10012083, ...
- 4,938
1
vote
0
answers
80
views
Recursion for the A006014 using difference of binomial coefficients
Let $a(n)$ be A006014 i.e.
$$
a(n)=na(n-1)+\sum\limits_{j=1}^{n-2}a(j)a(n-j-1), \\
a(1)=1
$$
Also generating function $A(x)$ satisfies
$$
A(x) = x(1 + A(x) + A(x)^2 + xA'(x))
$$
Let
$$
R(n,q)=\sum\...
- 4,938