[Python] Number of integer sequences of length n for which the sum is m

Overview

Challenge from Dwango Qualifying C --Kill / Death To solve, the sum is a certain value (positive) We needed the number of integer sequences and the number of unique combinations of them. Both can be enumerated on a two-dimensional array with $ O (nm) $ when the length of the integer sequence is $ n $ and the sum is $ m $.

Find the number of integer sequences

As an examplem=4, n=3When,● ● ● ●Can be considered to divide into three compartments, for example● ● | ● | ●It can be expressed as. This is a question of where to put $ n-1 $ | in $ m + n-1 $, and the number of combinations is $ _ {n-1 + m} C _ {n- It is calculated by 1} $, and in this example, there are $ _6 C _2 = 15 $.

4 0 0
3 0 1
3 1 0
2 0 2
2 1 1
2 2 0
1 0 3
1 1 2
1 2 1
1 3 0
0 0 4
0 1 3
0 2 2
0 3 1
0 4 0

Enumerate the number of integer sequences

Since it takes time to calculate $ _n C _r $ depending on how the value is taken, there are cases where it can be speeded up by enumerating the number of integer sequences. Here, the following recurrence formula is used. $ P (n, m) $ is the number of integer sequences of length $ n $ and sum $ m $.

P(n,m)= 
\begin{cases}
1 & (n,m=0)\\

P(n-1,m) & (m=0, 1 \leq n) \\
P(n-1,m)+P(n,m-1) & (1 \leq m, 1 \leq n) \\
0 & (otherwise) 
\end{cases}

The number of integer sequences up to the $ i $ th element whose sum is exactly $ j $ is the number of integer sequences whose sum is exactly $ j $ at the $ i-1 $ th element (that is, the $ i $ th element is (When $ 0 $) and the number of integer sequences whose sum is exactly $ j-1 $ up to the $ i $ th element. It can be implemented as follows.

P = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
    for j in range(1, m+1):
        cur[j] += cur[j-1]
    P.append(cur.copy())

Intuitive understanding of recurrence formulas

When enumerating an integer sequence of $ P (2,4) $

4 0 0
#Up to here is P(1,4)

0 4 0
3 1 0
2 2 0
1 3 0
#Up to here is P(2,4)

Now, if you subtract $ 1 $ from all the second elements of a sequence of integers whose length can be represented by exactly $ 2 $

0 3
3 0
2 1
1 2

And we get an integer sequence of $ P (2,3) $. Conversely, if you add $ 1 $ to all the second elements of $ P (2,3) $, the second element is greater than or equal to $ 0 $, so the sum that can be represented by exactly $ 2 $ in length is $ 4 $. You get a sequence of integers.

List the number of combinations

Find the number of unique combinations of the integer sequences listed earlier, excluding the same combinations in different orders. $ C (n, m) $ is a combination of $ n $ integers that sums $ m $, and is calculated by the following recurrence formula.

C(n,m)= 
\begin{cases}
1 & (n,m=0)\\

C(n-1,m) & (m < n, 1 \leq n) \\
C(n-1,m)+C(n,m-n) & (n \leq m, 1 \leq n) \\
0 & (otherwise) 
\end{cases}

The number of integer sequences up to the $ i $ th element whose sum is exactly $ j $ is the number of integer sequences whose sum is exactly $ j $ at the $ i-1 $ th element (that is, the $ i $ th element is (When $ 0 $) and the number of integer sequences whose sum is exactly $ ji $ up to the $ i $ th element. It can be implemented as follows.

C = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
    for j in range(i, m+1):
        cur[j] += cur[j-i]
    C.append(cur.copy())

Intuitive understanding of recurrence formulas

If you enumerate $ C (3,4) $,

4 0 0
#Up to here is C(1,4)

2 2 0
3 1 0
#Up to here is C(2,4)

2 1 1
#Up to here is C(3,4)

Will be. By the way, if the combination of integers whose length is exactly $ 2 $ and the sum is $ 4 $ is represented by *

2 * *
2 * *
0

3 * * *
1 *
0

If you transpose this and read it

2 2
* *
* *

2 1 1
* * *
*

And a combination of integers with a length of just $ 2 $ and a sum of $ 4 $ can be read as a combination of integers of any length with a maximum value of $ 2 $ and a sum of $ 4 $. Here, it can be seen that the integer combination after transposition always starts with $ 2 $, and thereafter it can be represented by the integer combination of $ C (2,4-2) = C (2,2) $.

reference

Math Girl ★ Play with the recurrence formula of partition number --incognita et cognita