All Questions
51 questions
26
votes
2
answers
1k
views
Partitions to different parts not exceeding $n$
Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
- 109k
17
votes
1
answer
756
views
Congruences Ramanujan-style
Let $t\in\Bbb{N}$ and consider the sequences $p_t(n)$ defined by
$$\sum_{n\geq0}p_t(n)x^n=\prod_{i\geq1}\frac1{(1-x^i)^t}=(x;x)_{\infty}^{-t}.$$
The numbers $p_t(n)$ can be regarded as enumerating ...
- 43.2k
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
7
answers
3k
views
A special type of generating function for Fibonacci
Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$.
Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them:
$$\...
- 43.2k
14
votes
1
answer
755
views
Generating function of the Thue-Morse sequence
Let $T$ be the generating function of the Thue-Morse sequence; thus,
$T(x)=x+x^2+x^4+x^7+\dotsb$. It is known that $T$ satisfies the nice
congruence
$$ (1+x)^3 T^2(x) + (1+x)^2 T(x) + x \equiv 0 \...
- 23k
11
votes
3
answers
659
views
Identifying the generating function $ G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}. $
I have computed a generating function for a problem involving a particular series, and would like to know if anyone has any references or a categorisation for it? It's
$$
G(a,z) = \sum_{n=0}^{\infty} ...
- 347
10
votes
1
answer
625
views
Generating function for A261041
Let $a(n)$ be A261041 (i.e., number of partitions of subsets of $\{1,2,\dotsc,n\}$, where consecutive integers are required to be in different parts).
Let $b(n)$ be an integer sequence with generating ...
- 4,938
8
votes
2
answers
4k
views
What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?
For example, if $n = 10$ and $k = 3$, then the legal partitions are
$$10 = 7 + 2 + 1 = 6 + 3 + 1 = 5 + 4 + 1 = 5 + 3 + 2$$
so the answer is $4$. By choosing $k$ random elements of $\{1,\ldots,2n/k\}$, ...
- 195
8
votes
1
answer
368
views
generalizing Wilf's conjecture: Uppuluri-Carpenter numbers
The complementary Bell numbers have the exponential generating function
$$\sum_{n\geq0}\tilde{B}_nx^n=e^{1-e^x}.$$
Herb Wilf conjectured that $\tilde{B}_n=0$ only for $n=2$. By now, there are a few ...
- 43.2k
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
5
votes
2
answers
3k
views
Number of 1 in binary representation of n
Let $1(n)$ be the number of digits $1$ in binary representation of number $n$.
For example, $13=1101_2$ so $1(13)=3\\$
Is there explicit form of $\,\,\sum{1(i)x^i} $?
I checked OEIS and didn't find ...
- 443
5
votes
1
answer
168
views
On a generating function and vector $\nu$ of length $n$
Let $f(n)$ be an arbitrary function with integer values.
Let $a(n)$ be an integer sequence such that
$$
\frac{1}{1-x}=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x)
$$
Start with ...
- 4,938
5
votes
1
answer
204
views
Collapsed partitions and generating functions
Given $n\in\Bbb{N}$, the number of (unrestricted) integer partitions of $n$ are given by
$$\sum_{n\geq0}p(n)x^n=\prod_{j\geq1}\frac1{1-x^j}.$$
Define the collapsed partitions of $n$ to be the ...
- 43.2k
5
votes
1
answer
442
views
Generating function related to 2-residues of partitions
Question
Express the following power series in two commuting variables $x,y$ as an infinite product, or a short sum of infinite products:
$$
\frac{P(xy)^2}{(1-x)}\sum_{k=-\infty}^\infty(2k+1)x^{k^2}y^...
- 1,090
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
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
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
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
2
answers
609
views
Closed formula for the generating function of the sequence of powers
Does anyone know of a closed formula for the function
$f_k(x)=\sum_{n=1}^{\infty}{n^k x^n}$ ? That is, the generating function of the sequence $1^k,2^k,3^k...$.
It is not hard to see that $f_k(x)=\...
- 35
3
votes
1
answer
156
views
$q$-series and Stirling of the 1st kind
Denote the (unsigned) Stirling numbers of the $1^{st}$-kind by ${n \brack k}$ and define
$$\mathbf{F}_a(q)=\sum_{m\geq1}\frac{q^{am}}{(1-q^m)^{2a}} \qquad \text{and} \qquad
\mathbf{G}_b(q)=\sum_{m\...
- 43.2k
3
votes
1
answer
349
views
Generating function for numbers divisible by some primes
Consider the first $k$ primes $p_1 = 2, p_2 = 3, \dots, p_k$. Let $A_k$ be the set of numbers that are divisible by at least one $p_i$. We can represent this set as a generating function:
$$G_k(x) = \...
- 343
3
votes
1
answer
140
views
$R$-recursion for unsigned Genocchi numbers (of first kind) of even index
Let $G_n$ be A036968 (i.e., Genocchi numbers). Here
$$
\frac{2t}{1+e^t}=\sum\limits_{n=0}^{\infty}G_n\frac{t^n}{n!}.
$$
Also
$$
t\tan\left(\frac{t}{2}\right)=\sum\limits_{n=1}^{\infty}(-1)^n G_{2n}\...
- 4,938
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
2
votes
2
answers
315
views
5 different ways to define the same family of integer sequences
Let ${n \brace k}$ be a Stirling number of the second kind.
Let $A_n(x)$ be an Eulerian polynomial. Here
$$
A_n(x) = \sum_{i=0}^{n}i!{n \brace i}(x-1)^{n-i}.
$$
Let $a_1(n,p,q)$ be the family of ...
- 4,938
2
votes
1
answer
400
views
An infinite product: combinatorial interpretation
It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product
$$\prod_{k=1}^{\infty}\frac{1}{1-x^k}...
- 1,561
2
votes
1
answer
310
views
Generating function for A300483 (related to Chebyshev polynomial of first kind)
Let $a(n)$ be A300483. Here
$$
a(n) = 2\int\limits_{t \geqslant 0}T_n\left(\frac{t+1}{2}\right)\exp(-t)\,dt.
$$
where $T_n(x)$ is $n$-th Chebyshev polynomial of first kind.
Let $b(n)$ be an integer ...
- 4,938
2
votes
1
answer
160
views
An inequality on partitions into distinct bounded parts
Let $P(n,m)$ denote the set of all positive integer partitions of $n$ into parts that are pairwise distinct and bounded by $m$. Let $p(n,m) = |P(n,m)|$.
After some numerical experiments it appears
$...
- 305
2
votes
1
answer
335
views
Combinatorial meaning of a binomial expansion
Let $F$ be a generating function $F(x) = \sum_{i=0}^\infty f_i x^i$, and
suppose that we can do operations formally without worrying about
convergence issues.
Define the coefficients
\begin{gather*}
...
- 5,230
2
votes
2
answers
894
views
Proving generating functions equality
What do you use to prove the following equality (and possibly more general ones of the kind)?
\begin{align*}\sum_{r,s,t} \frac{q^{r^2+rs+s^2+st+t^2}}{(q)_r (q)_s (q)_t} z_1^{r+s} z_2^{s+t} = \sum_{a,...
- 21
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
1
vote
1
answer
344
views
Products involving exponents of tribonacci numbers
The Fibonacci numbers $F_n$ can be given by
$$\sum_{k\geq0}F_kx^k=\frac{x}{1-x-x^2}.$$
Among many many properties of this sequence, consider the following two results:
(1) the coefficients of the ...
- 43.2k
1
vote
1
answer
235
views
partition theory: meet the COP
Recall that $(a;q)_0:=1,\,(a;q)_n=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^{n-1})$ and
$(a;q)_{\infty}=(1-a)(1-aq)(1-aq^2)\cdots$. Let's introduce the following (generalized) concept.
A colored overpartition (...
- 43.2k
1
vote
1
answer
116
views
General case of the some $R$-recursions
Let $f(n)$ be an arbitrary function.
Let $a(n)$ be an integer sequence such that its ordinary generating function satisfies
$$
A(x)=\sum\limits_{i=0}^{\infty}\frac{x^i}{\prod\limits_{j=0}^{i}(1-f(j)x)...
- 4,938
1
vote
1
answer
99
views
$R$-recursion for the A307389
Let $a(n)$ be A307389 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x)=\exp\left(\frac{\exp(2x)-2\exp(x)+2x+1}{2}\right)
$$
The sequence begins with
$$
1,...
- 4,938
1
vote
1
answer
155
views
Log-concavity of sequence related to overpartitions
The number $p_1(n)$ of overpartitions of $n$ is generated by
$$\sum_{n\geq0}p_1(n)\,q^n=\prod_{k=1}^{\infty}\frac{1+q^k}{1-q^k}.$$
Let $t\in\mathbb{N}$. Now, extend this to construct a family of ...
- 43.2k
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
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
1
vote
0
answers
93
views
Application of the series reversion
Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.
Let $a(n)$ be an arbitrary integer sequence such that $a(0)=1$.
Let $b(n)$ be an integer sequence such that
$$b(2^m(2n+1))=\sum\...
- 4,938
0
votes
1
answer
195
views
Fibonacci and product polynomials
The motivation for my current question arises from this MO post by R. Stanley. Caveat. There's a slight alteration.
With the convention $F_1=F_2=1$ for the Fibonacci numbers, define the polynomials $...
- 43.2k
0
votes
0
answers
48
views
$R$-recursion for the A007165
Let $a(n)$ be A007165 i.e. number of $P$-graphs with $2n$ edges. Here ordinary generating function $A(x)$ satisfies
$$
A(x) = \frac{(1 + xA(x))(1 + 2xA(x))}{1 + 2xA(x) - (xA(x))^2}
$$
Let
$$
R(n, q) = ...
- 4,938
0
votes
0
answers
100
views
Recursion for the A266328 by analogy with non-standard recursion for factorials
Let $a(n)$ be A266328 i.e. an integer sequence with exponential generating function
$$
A(x)=\exp\int B(x) \,dx
$$
such that
$$
B(x)=\exp(-x)\exp\int A(x) \,dx
$$
where the constant of integration is ...
- 4,938
0
votes
0
answers
182
views
Expansion of continued fraction using recursion
Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.
Let $a(n)$ be an integer sequence with generating function $\frac{1}{G(0)}$ where
$$
G(j)=1-\frac{f(j)x}{G(j+1)}
$$
Here we have
$$
G(...
- 4,938