いろいろ数え上げる

数え上げ
#

• 順列

permN<-function(N=10,k=3){
 return(exp(lgamma(N+1)-lgamma((N-k)+1)))
}

• 組み合わせ

combN<-function(N=10,k=3){
 return( exp(lgamma(N+1)-lgamma((N-k)+1)-lgamma(k+1)) )
}

• 重複順列

repPermN<-function(N=10,k=3){
 return(N^k)
}

• 重複組み合わせ　

repCombN<-function(N=10,k=3){
 return(combN(N+k-1,k))
}

• 分割と分割数
  • N個の要素を持つ分割の数はベル数

bellN<-function(N=10){
 bs<-rep(0,N+1)
 bs[1]<-1
 for(i in 2:(N+1)){
  for(j in 0:(i-2)){
   bs[i]<-bs[i]+choose(i-2,j)*bs[j+1]
  }
 }
 return(bs)
}

• N個の要素をk分割する場合の数は第２スターリング数

Stirling2N <- function(N=10,k=3)
{
    if (0 > k || k > N) stop("'k' must be in 0..N !")
    x <- 0:k
    sig <- rep(c(1,-1)*(-1)^k, length= k+1)# 1 for k=0; -1 1 (k=1)
    ga <- gamma(x+1)
    round(sum( sig * x^N /(ga * rev(ga))))
}

• N個の要素の非交差な分割の総数はカタラン数：木の形の数も。

CatalanN<-function(N=10){
 return(exp(lgamma(2*N+1)-lgamma(N+2)-lgamma(N+1)))
}

• 分岐木のトポロジー数

numTreeTopology<-function(n=3){
 tmp<-rep(0,n)
 if(n==1){
  tmp[1]<-1
 }else if(n==2){
  tmp[1]<-1
  tmp[2]<-1
 }else{
  tmp<-rep(0,n)
  tmp[1]<-1
  tmp[2]<-1
  for(i in 3:n){
   for(j in 1:(i-1)){
    tmp[i]<-tmp[i]+choose(i,j)*tmp[j]*tmp[i-j]/2
   }
  }
  
 }
 tmp
}

• Acyclic directed graphの数
• 数列データベース "id":"A003024"

NADG<-function(N=5){
 ret<-rep(0,N)
 for(i in 1:N){
  if(i==1){
   ret[i]<-1
  }else{
   for(j in 1:i-1){
    ret[i]<-ret[i]+(-1)^(j-1)*choose(i,j)*2^(j*(i-j))*ret[i-j]
   }
   ret[i]<-ret[i]+(-1)^(i-1)*choose(i,i)*2^(i*(i-i))
  }
 }
 ret
}