All Questions
94 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
20
votes
6
answers
879
views
Hamiltonian paths where the vertices are integer partitions
I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n.
Let the vertices of the graph G=G(n) denote all the p(n) ...
- 323
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
2
answers
1k
views
hook-length formula: "Fibonaccized" Part I
Consider the Young diagram of a partition $\lambda = (\lambda_1,\ldots,\lambda_k)$. For a square $(i,j) \in \lambda$, define the hook numbers $h_{(i,j)} = \lambda_i + \lambda_j' -i - j +1$ where $\...
- 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
1
answer
495
views
powered partition function generator: 1/2 of them are zeros?
Ramanujan delivered his famous congruences
$$p(5n+4)\equiv_50, \qquad p(7n+5)\equiv_70, \qquad p(11n+6)\equiv_{11}0$$
for the integer partitions with generating function $F(x)=\prod_{k=0}^{\infty}\...
- 43.2k
14
votes
2
answers
571
views
Number of d-Calabi-Yau partitions
This problem arises from algebraic geometry/representation theory, see https://arxiv.org/pdf/1409.0668.pdf (chapter 2).
We call a partition $p=[p_1,...,p_n]$ with $2 \leq p_1 \leq p_2 \leq ... \leq ...
- 26.5k
13
votes
2
answers
1k
views
an identity for a sum over partitions
Write an integer partition $\lambda\vdash n$ in two different ways:
(1) $\lambda=\lambda_1\geq\lambda_2\geq\lambda_3\cdots\geq\lambda_k\geq1$
(2) $\lambda=1^{m_1}2^{m_2}3^{m_3}\cdots n^{m_n}$ for ...
- 43.2k
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
13
votes
1
answer
980
views
Generating function for certain partitions (with a restriction on the Durfee square)
First of all my apologies if this question is well known or obvious: this is not in my area of research.
Let $T(x)=\sum_{n=0}^\infty t_nx^n$, where $t_n$ is the number of partitions $\lambda$ of $n$ ...
- 934
12
votes
3
answers
815
views
Partitions into parts from an arithmetic progresion
Fix an arithmetic progression $R=(a, a+m, a+2m, \ldots)$, and assume that $gcd(a,m)=1$. Define $q_R(n)$ as the following coefficients:
$$\prod_{i=0}^\infty (1+ t^{a+mi}) = \sum_{n=0}^\infty q_R(n) t^...
- 17k
12
votes
3
answers
892
views
Set partitions and permanents
Let $a(n)=$ Number of ordered set partitions of $[n]$ such that the smallest element of each block is odd.
...
- 884
12
votes
0
answers
643
views
Wilf's conjecture: complementary Bell numbers
The complementary Bell numbers or Uppuluri–Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....
- 43.2k
11
votes
3
answers
1k
views
A problem on a specific integer partition
Let $n$ be a positive integer, we consider partitions of the following form :
$$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that :
$d_{i}\vert n$
$1=d_{1}<d_{2} \le d_{3} \le ... \le d_{r}$...
11
votes
1
answer
494
views
Which of these sums appear most often?
Let $N=\{1,2,3,\ldots, n\}$.
We sum all the elements of every nonempty subset of $N$.
Which sum(s) appears most often? (Let's call this sum a champion).
Using a simple pigeonhole argument a champion ...
- 3,866
11
votes
0
answers
290
views
Color your partitions by parity
Let $a_c(n)$ be the number of ways to partition a positive integer $n$ where each even part comes in $c$ colors. Then, we can supply the generating function
$$\sum_{n\geq0}a_c(n)q^n=\prod_{k\geq1}\...
- 43.2k
10
votes
4
answers
1k
views
Binomial coefficient in Andrews' partition book
First of all, I think MathOverflow is a very great community to discuss math, either basic or advanced, and I'm glad to participate here. It's my first post, so I'm sorry if i did anything wrong, and ...
- 103
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
9
votes
2
answers
1k
views
A property of 47 with respect to partitions into five parts
Is 47 the largest number which has a unique partition into five parts (15, 10, 10, 6, 6), no two of which are relatively prime?
- 3,707
9
votes
2
answers
388
views
Every possible number of partitions by restricting parts?
Write $p(n)$ for the number of integer partitions of $n$. For $S \subseteq \{1, \ldots, n\}$, let $p_S(n)$ be the number of partitions of $n$ with all parts in $S$. So $p(n) = p_{\{1,\ldots,n\}}(n)$....
- 4,589
8
votes
1
answer
472
views
In search of a combinatorial reasoning for a vanishing sum
Assume $s, j \in\mathbb{N}$. Define the set
$$\mathcal{A}_{j,s}:=\{(n_1,n_2,\dots,n_j)\in\mathbb{Z}_{\geq0}^j\vert \,
n_1+2n_2+\cdots+jn_j=j, \, n_1+n_2+\cdots+n_j=s\}.$$
Question. Is there a ...
- 43.2k
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
1
answer
573
views
Sum of squares and partitions
This is an off-shot from my previous post on MO.
Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$, denote $\ell(\lambda)$ to be the length of $\lambda$.
Let $r_2(...
- 43.2k
7
votes
1
answer
832
views
Identity involving a sum over all partitions of $n$
In some work I've been doing on the cohomology of the moduli space of curves, the following identity has come up:
$$\prod_{i=1}^n \frac{x^{i-1}}{x^i-1} = \sum_{(a_1^{r_1},\ldots,a_{\ell}^{r_{\ell}}) \...
- 44.8k
7
votes
2
answers
785
views
Inverse map for partition transform
Let $(a_n)$, $n\in\mathbb{N}$, be a sequence of complex numbers, then formally one has
(1)
$$\prod_{1}^{\infty}\left(1-a_nx^n\right)^{-1}=1+\sum_{1}^{\infty}\left(\sum_{j_1+2j_2+\cdots +nj_n=n}a_1^{...
- 2,480
7
votes
0
answers
251
views
Can the partition function $p(n)$ take perfect power values?
Recall that the perfect powers are those integers $m^k$ with $k,m\in\{2,3,\ldots\}$. I don't consider $0$ or $1$ as a perfect power.
Y. Bugeaud, M. Mignotte and S. Siksek [Annals of Math., 2006] ...
- 15.6k
6
votes
3
answers
432
views
is this a familiar gen. fn. for partitions?
The $2$-adic valuation of $n\in\mathbb{N}$, denoted $\nu(n)$, is the largest power $t$ such that $2^t$ divides $n$. The number of integer partitions of $n$, denoted by $p(n)$, has generating function
...
- 43.2k
6
votes
1
answer
305
views
Are the Fourier coefficients of $\eta(q^m)^m / \eta(q)$ non-negative?
In this paper, the following result is proved.
For any prime $p$, all the Fourier coefficients of
$$\eta(q^p)^p / \eta(q) = q^{\frac{p^2-1}{12}} \prod_{n=1}^\infty (1 - q^{pn})^p (1 - q^{n})^{-1}$$
...
- 427
6
votes
4
answers
1k
views
Counting refinements of partitions
Let $p$ and $q$ be partitions of $n$. We say $q$ refines $p$ if the parts of $p$ can be subdivided to produce the parts of $q$. For example, $(5,5,1)$ refines $(6,5)$ but not $(7,4)$. $(n)$ refines ...
- 1,226
6
votes
1
answer
444
views
A binary hook-length formula?
This is purely exploratory and inspired by curiosity.
Setup: For an integer $k>0$, let $k=\sum_{j\geq0}k_j2^j$ be its binary expansion and denote the sum of its digits by $\eta(k):=\sum_jk_j$. ...
- 43.2k
6
votes
1
answer
392
views
hook-length formula: "Fibonaccized": Part II
This is a natural follow-up to my previous MO question, which I share with Brian Hopkins.
Consider the Young diagram of a partition $\lambda = (\lambda_1,\ldots,\lambda_k)$. For a square $(i,j) \in \...
- 43.2k
6
votes
2
answers
581
views
Partitions, $q$-polynomials and generating functions
Recall the integer partition function $P(n)$ with generating function
$$\sum_{n\geq0}P(n)x^n=\prod_{k=1}^{\infty}\frac1{1-x^k}.$$
Let $[n]_q=\frac{1-q^n}{1-q}$ denote the $q$-analogue of the integer $...
- 43.2k
6
votes
1
answer
481
views
Partitions comprised only of divisors
How many of the partitions of a natural number $n$ are comprised only of its divisors? That is, if $$p(n)=\sum_{\sum_{1}^n kj_k=n:j_k\geq 0} 1_{\[j_1,j_2,...\]},$$
is the ordinary partition function (...
- 2,480
6
votes
0
answers
171
views
An inequality involving integer partitions
For integers $n\ge k\ge0$, let $p(n,k)$ denote the number of ways to write $n$ as a sum of $k$ positive integers (repetition allowed). For example, $p(6,3)=3$ since
$$6=1+1+4=1+2+3=2+2+2.$$
QUESTION. ...
- 15.6k
5
votes
1
answer
211
views
degree of a polynomial over set-partitions
Denote $(x)_t = x(x-1)(x-2)\cdots(x-t+1)$ and fix some $t_1,\dots,t_n\in\mathbb{N}$. Now consider the polynomials
$$f_n(x)=\sum_{\pi\in L[n]}(-1)^{\vert\pi\vert-1}(\vert\pi\vert-1)!\prod_{A\in\pi}(x)_{...
- 43.2k
5
votes
1
answer
374
views
Closed-form for the number of partitions of $n$ avoiding the partition $(4,3,1)$
Let $a(n)$ be A309099 i.e. the number of partitions of $n$ avoiding the partition $(4,3,1)$.
We say a partition $\alpha$ contains $\mu$ provided that one can delete rows and columns from (the Ferrers ...
- 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
212
views
A generalization of Erdős–Newman–Mirsky?
Given a sequence $S$ of natural numbers, write ${\bf Gap}(S)$ for the set of differences between consecutive terms. (So $|{\bf Gap}(S)|=1$ precisely for arithmetic progressions, hence the connection ...
- 17.6k
5
votes
0
answers
140
views
Complementary Bell numbers $B^{\pm}(24n+14)$
The complementary Bell numbers $B^{\pm}(n)$ are defined by the alternating sum of the Stirling numbers of the second kind, $S(n,k)$:
$$B^{\pm}(n)=\sum_{k=0}^n(-1)^kS(n,k),$$ and they count the ...
- 407
5
votes
0
answers
194
views
Lemmas involving two partitions of integers
Question: Does anyone know a reference to the following lemmas involving two partitions? (The proofs are not hard, and may well be previously recorded, but where?) First some notation. Let $r$ be a ...
- 1,991
4
votes
1
answer
330
views
Combinatorial Technique Needed
The following problem is likely too special for MO.
However I have no clue how to deal with it, so I'll just try. Nevertheless
it is a combinatorial problem and a discussion about general methods
in ...
- 2,074
4
votes
2
answers
395
views
Congruence for complementary Bell numbers
The Bell numbers $B(n)$ can be given as a sum of the (signed) Stirling numbers of the second kind $S(n,k)$ as $B(n)=\sum_{k=0}^nS(n,k)$. There are also the so-called complementary Bell numbers defined ...
- 43.2k
4
votes
2
answers
784
views
asymptotic for restricted partitions
Let $m$ and $n$ be two positive integers and denote by $P(n,m)$ the number of partitions of $n$ into $m$ non-negative integers.
Is there an asymptotic formula for $P(n,m)$ ?? Any reference is welcome....
- 2,384
4
votes
2
answers
307
views
Lower bounding a partition-related sum
We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\...
- 715
4
votes
1
answer
206
views
Partition numbers as the specific sums of the A161511
Let $p(n)$ be A000041 i.e. number of partitions of $n$ (the partition numbers).
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
Let $a(n)$ be A161511 i.e. number of $1\cdots0$ pairs in the ...
- 4,938
4
votes
1
answer
96
views
Separate the trivial partition by a linear hyperspace
Let $e=[1,1,\ldots,1]\in\mathbb{Z}^n$. I am looking for a way to find a vector $a\in\mathbb{Z}^n$ such that:
$\langle a,e\rangle=0$ and
for every nonnegative $v\in\mathbb{Z}^n$ such that $\langle e,v\...
- 3,041
4
votes
1
answer
308
views
3 divides coefficents of this $q$-series
Denote $\phi(q):=\prod_{j\geq1}(1-q^j)$ and let $\xi=e^{\frac{2\pi i}3}$ be a cube root of unity.
Define the sequence $u(n)$ by
$$\prod_{n\geq1}\prod_{s=1}^2(1-q^n\xi^{ns})(1-q^{2n}\xi^{ns})
=\sum_{n\...
- 43.2k
4
votes
1
answer
206
views
Prime numbers and number of partitions of $n$ into distinct parts with boundary size $2$
Let $a(n)$ be A227559, i.e., number of partitions of $n$ into distinct parts with boundary size $2$. Be careful here: offset is $3$.
I conjecture that $a(4n+2)=2n+1$ for $n>0$ if and only if $2n+1$ ...
- 4,938
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)$. ...
- 43.2k