# Integer partitions into restricted parts

Given a linear diophantine equation $$x_1+\dots+x_n=m\leq nn'$$ how many solutions does it have with each $$x_i\in[0,n']\cap\mathbb Z$$? Looking for asymptotics that parametrizes well with both $$n$$ and $$n'$$ over different ranges for both situations

1. $$x_1\leq\dots\leq x_n$$ and

2. unordered.

• Is $m$ a parameter of the problem, or can it take any value within the constraints? – Brendan McKay Jul 2 '20 at 10:22
• Supposing they satisfy the conditions, are (2,1,1) and (1,2,1) both counted as solutions? If so, this is a question about integer compositions rather than partitions. – Brian Hopkins Jul 2 '20 at 13:19
• @BrendanMcKay $m$ is any value within the constraints. – VS. Jul 2 '20 at 17:18
• @BrianHopkins Yes it would be nice to know for both scenarios. When $x_i\leq x_{i+1}$ is forced (partitions) and not forced (compositions). – VS. Jul 2 '20 at 17:19

Since $$m$$ is a dummy variable (i.e. a bound variable) and $$n,n'$$ are "real" variables (i.e. they are free) perhaps we should rewrite the problem accordingly as $$$$compute the following $$f(y,z) = \#\left\lbrace (x_1,... , x_y )\mid x_1 + ... + x_y = m,\ x_i \in \mathbb{N},\ m \leq yz ,\ i < j \implies x_i \leq x_j \right\rbrace."$$ We can let $$f'$$ be the number if we omit the condition $$i < j \implies x_i \leq x_j$$ (i.e. $$f$$ corresponds to partitions and $$f'$$ corresponds to compositions). Intuition tells us that $$f$$ will likely have a closed form solution and $$f'$$ will probably only have solution expressible by generating functions (which are perfect for asymptotics). Let us confirm our intuitions:

Compositions (i.e. $$f'$$)

It is straightforward to see that if we let $$g(y,m) = \#\left\lbrace (x_1,..., x_y ) \mid x_1 + ... + x_y = m, \ x_i \in \mathbb{N}\right\rbrace,$$ then we have the identity $$f'(y,z) = \sum_{m=0}^{yz}g(y,m).$$ It is well known, see the famous stars and bars method in feller's introduction to probability theory, that $$g(y,m)= \binom{y+m-1}{m},$$

so that $$f'(y,z) = \sum_{m=0}^{yz}\binom{y+m-1}{m}= \binom{yz+y}{yz},$$ (or, using your notation, $$f'(n,n')=\binom{nn'+n}{nn'}$$)

where the last identity can be derived as a consequence of Chu Shih-Chieh's identity, see example 2.5.1 of Chuan-Chong & Khee-Meng's text on combinatorics. I also strongly recommend taking a peek at Flajolet & Sedgewick's text on analytic combinatorics for asymptotics and the more abstract symbolic method/species style which is necessary for the more difficult analysis of $$f$$.

Partitions (i.e. $$f$$)

It is straightforward to see that if we let $$g(y,m) = \#\left\lbrace (x_1,... , x_y ) \mid x_1 + ... + x_y = m, \ x_i \in \mathbb{N}, \ i < j \implies x_i \leq x_j\right\rbrace,$$ then we have the identity $$f(y,z) = \sum_{m=0}^{yz}g(y,m).$$

It is well known that if we define the generating function $$\mathcal{G}_y$$ as $$\mathcal{G}_y(x) = \sum_{m \in \mathbb{N}} g(y,m) x^m,$$ then we have that $$\mathcal{G}_y(x) = \prod_{k=1}^{y}\frac{1}{1-x^k},$$ see Flajolet & Sedgewick's text on analytic combinatorics or Andrews elementary text on partitions. One way to see this is to notice the following famous theorem attributed to Euler

The number of partitions of a number $$n$$ into at most $$l$$ parts is equal to the number of partitions of a number $$n$$ into parts all bounded by $$l$$

and the result follows by elementary generating function magic. Finally, theorem 5.1.1 of Chuan-Chong & Khee-Meng's text on combinatorics states that $$\mathcal{A}(x) = \sum_{n \in \mathbb{N}} a_n x^n \implies \frac{1}{1-x}\mathcal{A}(x) = \sum_{n \in \mathbb{N}} \left(\sum_{k \leq n} a_k \right) x^n;$$ therefore, if we define the generating function $$\mathcal{F}_y$$ as $$\mathcal{F}_{y}(x) = \sum_{n \in \mathbb{N}} f(y,n) x^n,$$

then we have that $$\mathcal{F}_{y}(x) = \frac{1}{1-x}\mathcal{G}_y(x) = \frac{1}{1-x}\prod_{k=1}^{y}\frac{1}{1-x^k}.$$

More explicitly we have that $$f(y,z) = [x^{yz}] \mathcal{F}_{y}(x) =[x^{yz}] \left(\frac{1}{1-x}\prod_{k=1}^{y}\frac{1}{1-x^k}\right)$$ where the operator $$[x^{k}]$$ is defined as follows: $$\mathcal{A}(x) = a_0+a_1x+ ... +a_nx^n+ ... \implies [x^{k}]\mathcal{A}(x) = a_k.$$ For the asymptotics please consult Flajolet & Sedgewick's text on analytic combinatorics where you will find a wealth of information and techniques for extracting the asymptoics of the coefficients of $$\mathcal{F}_{y}(x)$$.

• Is there a clean asymptotic expression for $f$ just as $f'$ does? – VS. Jul 8 '20 at 6:38
• So $f′(n,n′)$ is only exponential in $n$ because $\binom{nn′+n}{nn′}\approx(1+\frac1{n′})^{nn′}\rightarrow e^n$? That is surprising isn't it? – VS. Jul 8 '20 at 8:24
• I think it is $e^{n+nn'}$. I think I made a mistake. – VS. Jul 8 '20 at 22:33
• I doubt there is a nice expression for $f$ since partitions tend to not have nice expressions in general but there is a lot of literature written about them. The most famous asymptotic formula known for the partition function is $p(n) \sim \frac{1}{4n\sqrt{3}}\exp\left(\pi \sqrt{\frac{2n}{3}}\right)$ which is due to Hardy and Ramanujan, see en.wikipedia.org/wiki/Partition_function_(number_theory). Chapter 7 of g.co/kgs/pgs3uM also has a lot of material on partitions, mostly algebraic. The definitive text is probably Andrews "the theory of partitions" g.co/kgs/HPVXS4 – Pedro Juan Soto Jul 8 '20 at 23:38
• By nice expression I was thinking a first order asymptotic. – VS. Jul 9 '20 at 4:23