蟻本「分割数」考察 その2

# 蟻本「分割数」考察 その2

## 概要

「[蟻本「分割数」考察](https://qiita.com/MyOden/items/4cf63128469f5833e4aa)」では
「n個の互いに区別できない品物を、m個以下に分割する方法の総数」
でなくて
「n個の互いに区別できない品物を、m個に分割する方法の総数」
に意識が行って時間を費やしてしまった。「n個の互いに区別できない品物を、m個に分割する方法の総数」を動的計画法でもとめてみたのでメモしておく。

## 漸化式
「n個の互いに区別できない品物を、m個に分割する方法の総数」をdp(n,m)とする。
「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を含まないものの総数をdpA(n,m)、「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を一つでも含むものの総数をdpB(n,m)とする。
例えば、n=10,m=3で考えるとdpA(10,3)は
{2,2,6},{2,3,5},{2,4,4},{3,3,4}
があるのでdpA(10,3)=4となる。dpB(10,3)は
{1,1,8},{1,2,7},{1,3,6},{1,4,5}
があるのでdpB(10,3)=4となる。

ところで「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を含まないものの総数はは、「n-m個の互いに区別できない品物を、m個に分割する方法」の総数と同じである。一方「n個の互いに区別できない品物を、m個に分割する方法」のうち要素に1を一つでも含むものの総数は「n-1個の互いに区別できない品物を、m-1個に分割する方法」の総通と等しい。
上の例で言うと
dpA(10,3)はdp(7,3)=4に等しく
{1,1,5},{1,2,4},{1,3,3},{2,2,3}
と対応する。
dpB(10,3)はp(9,2)=4に等しく
{1,8},{2,7},{3,6},{4,5}
と対応する。
したがってdp(n,m)には漸化式dp(n,m)=dp(n-m,m)+dp(n-1,m-1)が成り立つ（n>2,m>2,n-m=>m）。

## 実装1 「n個の互いに区別できない品物を、m個以下に分割する方法」
蟻本を参照して実装

```book.cpp
     1	#include <bits/stdc++.h>
     2	using namespace std;
     3	typedef long long ll;
     4	     
     5	const int MAX_N=100;
     6	const int MAX_M=100;
     7	
     8	int n,m;
     9	ll dp[MAX_M + 1][MAX_N + 1]; 
    10	
    11	int main(){
    12	    cin >> n >> m; 
    13	    cout << "n:" << n << " m:" << m << endl ;
    14	    dp[0][0] = 1; 
    15	    for ( int i = 1; i<= m ; i++){
    16	        for(int j = 0; j<= n; j++){
    17	            if( j - i  >= 0){
    18	                dp[i][j] = dp[i-1][j] + dp[i][j-i];
    19	            } else {
    20	                dp[i][j] = dp[i-1][j]; 
    21	            } 
    22	        }
    23	        cout << "i:" << i << " j:" << n << " " << dp[i][n] << endl ;
    24	    }
    25	}
```

## 実装2 「n個の互いに区別できない品物を、m個に分割する方法」
自分で作成した漸化式で実装

```myoden.cpp
     1	#include <bits/stdc++.h>
     2	     
     3	using namespace std;
     4	typedef long long ll;
     5	     
     6	const int MAX_N=100;
     7	const int MAX_M=100;
     8	
     9	int n,m;
    10	
    11	ll dp[MAX_M + 1][MAX_N + 1]; 
    12	
    13	int main(){
    14	    int ans=0; 
    15	    cin >> n >> m; 
    16	    cout << "n:" << n << " m:" << m << endl ;
    17	
    18	    for (int j = 1; j <= n; j++){
    19	        dp[1][j]=1;
    20	    }
    21	
    22	    for ( int i = 2; i<= m ; i++){
    23	        for(int j = 1; j<= n; j++){
    24	            if( j < i ){
    25	                dp[i][j] = 0;
    26	            } else if ( j- i >= 1){ 
    27	                dp[i][j] = dp[i-1][j-1] + dp[i][j-i];
    28	            } else {
    29	                dp[i][j] = dp[i-1][j-1] + dp[i][j-i];
    30	            } 
    31	            // cout << "i:" << i << " j:" << j << " " << dp[i][j] << endl ;
    32	        }
    33	    }
    34	    for(int i=1;i<=m;i++){
    35	        ans += dp[i][n];
    36	        cout << "i: " << i << " j: " << n << " " << dp[i][n] << " " << ans << endl ;
    37	    }
    38	}
```

## 実行例
蟻本と自作漸化式で結果が一致するのを確認

```Execution
myoden@ubuntu002:~/AntBook/P066$ cat input.2
6 6 
myoden@ubuntu002:~/AntBook/P066$ ./book < input.2
n:6 m:6
i:1 j:6 1
i:2 j:6 4
i:3 j:6 7
i:4 j:6 9
i:5 j:6 10
i:6 j:6 11
myoden@ubuntu002:~/AntBook/P066$ ./myoden < input.2
n:6 m:6
i: 1 j: 6 1 1
i: 2 j: 6 3 4
i: 3 j: 6 3 7
i: 4 j: 6 2 9
i: 5 j: 6 1 10
i: 6 j: 6 1 11
myoden@ubuntu002:~/AntBook/P066$ 
```

確認のため組み合わせを書き出してみた。
N=6

| M  |分割数Mの組み合わせ数 | 分割数M以下の組み合わせ数 | 組み合わせ|
|:---:|:------------------:|:-------------------:|:---------------------|
| 1 |  1 |  1 | ｛6｝ |
| 2 |  3 |  4 | ｛1,5｝｛2,4｝｛3,3｝|
| 3 |  3 |  7 | ｛1,1,4｝｛1,2,3｝｛2,2,2｝ |
| 4 |  2 |  9 | ｛1,1,1,3｝ ｛1,1,2,2｝|
| 5 |  1 |  10 | ｛1,1,1,1,2｝ |
| 6 |  1 |  11 | ｛1,1,1,1,1,1｝ |