2006-07-13

何通り

集合離散数学 Java ベル数

要素数n個の集合がある。その部分集合は $2^n$ あることは、昨日の記事の通り。今、さらに、要素数k個の部分集合を２、３、…、k群に分割することを考える。
要素数２の場合には、２群に分ける場合のみがあって、それは{(1),(2)}の１通り
要素数３の場合には、２群に分ける場合は、{(1),(2,3)},{(1,2),(3)},{(1,3),(2)}の３通り。３群に分ける場合は、{(1),(2),(3)}のみがあって、１通り。合わせて４通り。
要素数４の場合には、２群に分ける場合は、{(1,2,3),(4)},{(1,3,4),(2)},{(1,3),(2,4)},{(1,4),(2,3)},{(1),(2,3,4)},{(1,2,4),(3)},{(1,2),(3,4)}の７通り。３群に分ける場合は、{(1,3),(2),(4)},{(1),(2,3),(4)},{(1,2),(3),(4)},{(1,4),(2),(3)},{(1),(2,4),(3)},(1),(2),(3,4)}の６通り。４群に分ける場合は、{(1),(2),(3),(4)}の１通り。合わせて、１４通り。
この関係は、漸化式になっていることがわかる。
- 今、nをk=１、２、３、…n群に分ける分け方をそれぞれ、A(n,k)とする。
- n=1のときは、k=1について定義できて、A(n,k)=A(1,1)=1通りである。
- n->n+1にあっては、第n+1番目の要素を新規の組として、f分割されている分けパターンに追加({(x1,x2,...),(y1,y2,..)...(n+1)})することで、f+1分割の新たな分けパターンが生じる。この数は、A(n,f)である。また、f分割されている分けパターンのいずれかの組に入れ込む(x1,x2,...),(y1,y2,..,n+1)...})ことで、要素数n+1のf分割の分けパターンが生じる。この数はA(n,f)xfである。
- $C(n) = ￥sum_{k=2}^{n} (A(n,k))$ . $A(n,k) = A(n-1,k) ￥times k +A (n-1,k-1);A(1,0)=0,A(1,1)=1$
また、 $A(n,n-1)=2^{n-1}-1$
この漸化関係の説明図は掲載図および、その拡大版はこちら
この規則から求められた、部分集合への分割パターン数は次の通り

No.elements　No.combinations

0 0

1 0

2 1

3 4

4 14

5 51

6 202

7 876

8 4139

9 21146

10 115974

多分大丈夫なソースはこちら。これを基に、ベル数を計算するjava アプリケーションについては、こちら



public class MultipleSetCombination {
	public static void main(String[] args) {

		//int k=2;

		int k= Integer.parseInt(args[0]);

		for(int i=0;i<=k;i++){

			MultipleSetCombination mps = new MultipleSetCombination(i);

			MultipleSetCombination.PrintMultipleSetCombination(mps,"\t","\n");

		}

		

	}

	

	int numElem;

	int[][] division;//No. patterns to divide m elements into n groups

	int totalNumComb;

	

	

	public MultipleSetCombination(int x){

		numElem=x;

		division = new int[x+1][0];

		for(int i=0;i<x+1;i++){

			division[i]=new int[x+1];

			//System.out.println("division[i] len " + division[i].length);

			if(i==0){

				for(int j=0;j<division[i].length;j++){

					division[i][j]=0;

				}

			}else if(i==1){

				for(int j=0;j<division[i].length;j++){

					division[i][j]=0;

				}

				division[i][1]=1;

			}else{

				for(int j=0;j<division[i].length;j++){

					

					division[i][j]=0;
							if(j==0){

								division[i][j]=0;

							}else{

								//division[i][j]+=Combination.NComb2(x,k)*division[i-1][i-1-k];

								division[i][j]+=division[i-1][j]*j;//持ち上がり分、ただし、追加要素をどの分割群に入れるかを*(j-1)で表す

								division[i][j]+=division[i-1][j-1];//追加用をを単一群として加えたときの持ち上がり分

							

							}
				}

				//division[i-1] = null;

			}

			totalNumComb=0;

			for(int j=2;j<division[i].length;j++){

				totalNumComb += division[i][j];

			}

		}

	}

	public static void PrintMultipleSetCombination(MultipleSetCombination m, String sep1,String sep2){

		String ret = MultipleSetCombination.StringMultipleSetCombination(m,sep1,sep2);

		System.out.println(ret);

	}

	public static String StringMultipleSetCombination(MultipleSetCombination m,String sep1,String sep2){

		String ret="";

		String a = "