1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Is $m$ a parameter of the problem, or can it take any value within the constraints? $\endgroup$ – Brendan McKay Jul 2 '20 at 10:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Hopkins Jul 2 '20 at 13:19
  • $\begingroup$ @BrendanMcKay $m$ is any value within the constraints. $\endgroup$ – VS. Jul 2 '20 at 17:18
  • $\begingroup$ @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). $\endgroup$ – VS. Jul 2 '20 at 17:19
2
+50
$\begingroup$

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) $.

$\endgroup$
7
  • $\begingroup$ Is there a clean asymptotic expression for $f$ just as $f'$ does? $\endgroup$ – VS. Jul 8 '20 at 6:38
  • $\begingroup$ 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? $\endgroup$ – VS. Jul 8 '20 at 8:24
  • $\begingroup$ I think it is $e^{n+nn'}$. I think I made a mistake. $\endgroup$ – VS. Jul 8 '20 at 22:33
  • $\begingroup$ 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 $\endgroup$ – Pedro Juan Soto Jul 8 '20 at 23:38
  • $\begingroup$ By nice expression I was thinking a first order asymptotic. $\endgroup$ – VS. Jul 9 '20 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.