2013-03-17

だんだん増やす

格子立方格子多次元整数列単体 R combinat

１次元で、原点から、座標を１ずつ増やして(0)->(1)->(2)...とノードをつないで作られるグラフは鎖。このノードの数は1,2,3...
２次元で、原点から、x1,x2軸方向に一つずつ増やして

((0,0))->((1,0),(0,1))->((2,0),(1,1),(0,2))

とノードをつないで作られるグラフは２次元正方格子

３次元では

((0,0,0))->((1,0,0),(0,1,0),(0,0,1))->((2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1))...

これは３次元立方格子
任意次元(k次元)にして、第i段ステップのノードの数を考えよう
k次元の第i番目のノードの集合は、k-1次元の第1,2,...,i番目のすべてのノードの集合になっているから
$S^k(n) = \sum_{i=1}^n S^{k-1}(i)$ という関係にある
正単体を順次大きくしている、という仕組みにもなっている

my.kousi <- function(k,n){
	if(k == 1){
		return(1)
	}else{
		ret <- 0
		for(i in 1:n){
			ret <- ret + my.kousi(k-1,i)
		}
		return(ret)
	}
}
k <- 4
n <- 5

my.kousi(4,100)

実際は $S^k(n) = \frac{\prod_{i=0}^{n-1} (k+n-2 -i)}{(k-1)!}$ と書けて

my.kousi.2 <- function(k,n){
	if(k==1){
		return(1)
	}
	n2 <- n+k-2
	a <- n2:(n2-k+2)
	b <- 1:(k-1)
	exp(sum(log(a))-sum(log(b)))
}

Rのcombinatパッケージのnsimplex()関数でも

library(combinat)
k<-3
n<-10
my.kousi.2(k,n)
nsimplex(k,n-1)

nをk群に分ける分け方を列挙するには

library(combinat)
xsimplex(k,n)

> k<-4
> n<-5
> xsimplex(k,n)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,]    5    4    4    4    3    3    3    3    3     3     2     2     2     2
[2,]    0    1    0    0    2    1    1    0    0     0     3     2     2     1
[3,]    0    0    1    0    0    1    0    2    1     0     0     1     0     2
[4,]    0    0    0    1    0    0    1    0    1     2     0     0     1     0
     [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26]
[1,]     2     2     2     2     2     2     1     1     1     1     1     1
[2,]     1     1     0     0     0     0     4     3     3     2     2     2
[3,]     1     0     3     2     1     0     0     1     0     2     1     0
[4,]     1     2     0     1     2     3     0     0     1     0     1     2
     [,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38]
[1,]     1     1     1     1     1     1     1     1     1     0     0     0
[2,]     1     1     1     1     0     0     0     0     0     5     4     4
[3,]     3     2     1     0     4     3     2     1     0     0     1     0
[4,]     0     1     2     3     0     1     2     3     4     0     0     1
     [,39] [,40] [,41] [,42] [,43] [,44] [,45] [,46] [,47] [,48] [,49] [,50]
[1,]     0     0     0     0     0     0     0     0     0     0     0     0
[2,]     3     3     3     2     2     2     2     1     1     1     1     1
[3,]     2     1     0     3     2     1     0     4     3     2     1     0
[4,]     0     1     2     0     1     2     3     0     1     2     3     4
     [,51] [,52] [,53] [,54] [,55] [,56]
[1,]     0     0     0     0     0     0
[2,]     0     0     0     0     0     0
[3,]     5     4     3     2     1     0
[4,]     0     1     2     3     4     5

実際、k次元で１辺nのを１辺n+1に上げるときには、１辺nのそれのある一つの軸の値を１増やしたものと、k-1次元で１辺n+1のものに1次元分付け加え(ただしその付け加え次元の値はすべて０)たものとを継ぎ合わせたものになる
確かめてみる

xsimplex(4,6) -> k4n6 
xsimplex(4,5) -> k4n5 
xsimplex(3,6) -> k3n6
k4n5.2 <- k4n5
k4n5.2[1,] <- k4n5.2[1,]+1
k3n6.2 <- rbind(rep(0,length(k3n6[1,])),k3n6)
k4n6.2 <- cbind(k4n5.2,k3n6.2)
k4n6-k4n6.2 # 一致している

k=4をk=2のを２個かけあわせたものとすると

> k2n100 <- nsimplex(2,0:100)
> k2n100.2 <- k2n100[101:1]
> sum(k2n100*k2n100.2)
[1] 176851
> nsimplex(4,100)
[1] 176851

整数列A110555