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$ Jul 2, 2020 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$ Jul 2, 2020 at 13:19
  • $\begingroup$ @BrendanMcKay $m$ is any value within the constraints. $\endgroup$
    – VS.
    Jul 2, 2020 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, 2020 at 17:19

1 Answer 1

3
+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, 2020 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, 2020 at 8:24
  • $\begingroup$ I think it is $e^{n+nn'}$. I think I made a mistake. $\endgroup$
    – VS.
    Jul 8, 2020 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$ Jul 8, 2020 at 23:38
  • $\begingroup$ By nice expression I was thinking a first order asymptotic. $\endgroup$
    – VS.
    Jul 9, 2020 at 4:23

Your Answer

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