0
$\begingroup$

What is a formula for number of monotonically decreasing sequences of non-negative integers of given length and sum? For instance, if length k=3 and sum n=5, then these are the 5 sequences that meet the criteria...

  • 5, 0, 0
  • 4, 1, 0
  • 3, 2, 0
  • 3, 1, 1
  • 2, 2, 1

I have some code that given a monotonically decreasing sequence, produces the next monotonically decreasing sequence with same length and sum.

Here is a table of number of these monotonically decreasing sequences of non-negative integers for various lengths and sums ...

length sum1 sum2 sum3 sum4 sum5 sum6 sum7 sum8 sum9 sum10 sum11 sum12 sum13 sum14 sum15 sum16 sum17 sum18 sum19 sum20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
3 1 2 3 4 5 7 8 10 12 14 16 19 21 24 27 30 33 37 40 44
4 1 2 3 5 6 9 11 15 18 23 27 34 39 47 54 64 72 84 94 108
5 1 2 3 5 7 10 13 18 23 30 37 47 57 70 84 101 119 141 164 192
6 1 2 3 5 7 11 14 20 26 35 44 58 71 90 110 136 163 199 235 282
7 1 2 3 5 7 11 15 21 28 38 49 65 82 105 131 164 201 248 300 364
8 1 2 3 5 7 11 15 22 29 40 52 70 89 116 146 186 230 288 352 434
9 1 2 3 5 7 11 15 22 30 41 54 73 94 123 157 201 252 318 393 488
10 1 2 3 5 7 11 15 22 30 42 55 75 97 128 164 212 267 340 423 530
11 1 2 3 5 7 11 15 22 30 42 56 76 99 131 169 219 278 355 445 560
12 1 2 3 5 7 11 15 22 30 42 56 77 100 133 172 224 285 366 460 582
13 1 2 3 5 7 11 15 22 30 42 56 77 101 134 174 227 290 373 471 597
14 1 2 3 5 7 11 15 22 30 42 56 77 101 135 175 229 293 378 478 608
15 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 230 295 381 483 615
16 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 296 383 486 620
17 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 384 488 623
18 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 489 625
19 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 626
20 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627

Relatedly, if we remove the "monotonically decreasing" requirement, then the answer would be the "combinations with replacement" formula:

$\frac{(sum + length - 1)!}{sum! \cdot (length - 1)!}$

And if I remove the "sum" requirement, I think there are some existing posts, like this one.

$\endgroup$
8
  • 2
    $\begingroup$ I think you meant sum $=5$ in your example, not $4$. $\endgroup$
    – lulu
    Commented Jan 26 at 21:49
  • 3
    $\begingroup$ This is often written as $p_k(n)$ where $k$ is the length and $n$ is the sum. These are the paritions of length $k$ of $n.$ en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$
    – Thomas Andrews
    Commented Jan 26 at 21:50
  • 1
    $\begingroup$ There aren't good closed formula for most partition counting. Certainly, that Wikipedia page gives no good formula for $p_k(n),$ just a recursive formula. $\endgroup$
    – Thomas Andrews
    Commented Jan 26 at 21:52
  • 3
    $\begingroup$ Probably better link for $p_k(n),$ so it is not buried in the general article. en.wikipedia.org/wiki/Triangle_of_partition_numbers $\endgroup$
    – Thomas Andrews
    Commented Jan 26 at 21:55
  • $\begingroup$ @lulu, yes, thanks, I did mean sum=5. $\endgroup$
    – JacobEgner
    Commented Jan 27 at 5:29

1 Answer 1

Reset to default
1
$\begingroup$

This is equivalent to the number of integer partitions of $n$ of length $k,$ and is usually denoted $p_k(n).$ There isn't a known closed form,but there is a recursion:

$$p_k(n)=p_k(n-k)+p_{k-1}(n-1).$$

There are also generating functions for $p_k(n).$

Wikipedia page for this function.

Wikipedia page more generally about integer partitions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .