いろいろ数え上げる

数え上げ
#Binom(a,b)=\frac{a!}{b!(a-b)!}

  • 順列_N P_k = \frac{N!}{(N-k)!}
permN<-function(N=10,k=3){
 return(exp(lgamma(N+1)-lgamma((N-k)+1)))
}
  • 組み合わせ_N C_k=Binom(N,k)=\frac{N!}{(N-k)!k!}=\frac{_N P_k}{k!}
combN<-function(N=10,k=3){
 return( exp(lgamma(N+1)-lgamma((N-k)+1)-lgamma(k+1)) )
}
  • 重複順列 N^k
repPermN<-function(N=10,k=3){
 return(N^k)
}
  • 重複組み合わせ _N H_k = _{N+k-1} C_k =\sum_{i=0}^k _N C_{k-i} _{k-i} H_i
repCombN<-function(N=10,k=3){
 return(combN(N+k-1,k))
}
  • 分割と分割数
    • N個の要素を持つ分割の数はベル数B(N+1)=\sum_{i=0}^N Binom(N,i)B(i);B(0)=1
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)
}

S(N,k)=\frac{1}{k!}\sum_{i=0}^k (-1)^i Binom(k,i) (k-i)^N

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
}
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
}