n文字の文字列を部分文字列に分ける場合のすべての分け方

研究

The On-Line Encyclopedia of Integer Sequences!：A008863 Sum C(n,k), k=0..10.

よくお目にかかるのに毎回計算してしまうのでメモ。

たとえば、１文字の文字列を部分文字列に分ける場合のすべての分け方は以下の通り

  • 1:{1}

当たり前。2文字の場合

  • 12: {12}, {1,2}

3文字

  • 123: {123}, {12,3}, {1,23}, {1,2,3}

4文字

  • 1234: {1234}, {1,234}, {123,4}, {12,34}, {1,2,34}, {12,3,4}, {1,23,4}, {1,2,3,4}

すなわち、n文字の文字列を部分文字列に分ける場合のすべての分け方は、区切り記号をおける場所の数をkとし、実際に区切り記号をいくついれるかをiとすると

  • Sum Combination(k,i) i=0,..., k
  • k = n-1より、Sum Combination(n-1,i) i=0,..., n-1

びっくりするのが、これを検索したら2のn乗の数列と同じだったこと。何か面白い。