１２人を４人ずつの３グループA、B、Cに分けておく。（グループ毎に帽子の色を統一して
おく。）

　１２人から任意のｋ人を選び横一列にしたとき、同じ色の帽子が隣に並ばない並び方は何
通り？

　ｋ＝３、４、５　での値はなにか？

　これを一般に算出できる式や母関数みたいなのはできないものなんだろうか？
（ｋ＞5で苦労するので）


　DD++さんが考察されました。（平成２８年９月２６日付け）

k=1のとき、帽子の並び順は3通り
(1,0,0)の帽子の並び順は3×1=3通りで、人の並びは4×3=12通り

k=2のとき、帽子の並び順は6通り
(1,1,0)の帽子の並び順は3×2=6通りで、人の並びは4×4×6=96通り

k=3のとき、帽子の並び順は12通り
(1,1,1)の帽子の並び順は1×6=6通りで、人の並びは4×4×4×6=384通り
(2,1,0)の帽子の並び順は6×1=6通りで、人の並びは12×4×6=288通り
合わせて672通り

k=4のとき、帽子の並び順は24通り
(2,1,1)の帽子の並び順は3×6=18通りで、人の並びは12×4×4×18=3456通り
(2,2,0)の帽子の並び順は3×2=6通りで、人の並びは12×12×6=864通り
合わせて4320通り

k=5のとき、帽子の並び順は48通り
(2,2,1)の帽子の並び順は3×12=36通りで、人の並びは12×12×4×36=20736通り
(3,1,1)の帽子の並び順は3×2=6通りで、人の並びは24×4×4×6=2304通り
(3,2,0)の帽子の並び順は6×1=6通りで、人の並びは24×12×6=1728通り
合わせて24768通り

k=6のとき、帽子の並び順は96通り
(2,2,2)の帽子の並び順は1×30=30通りで、人の並びは12×12×12×30=51840通り
(3,2,1)の帽子の並び順は6×10=60通りで、人の並びは24×12×4×60=69120通り
(3,3,0)の帽子の並び順は3×2=6通りで、人の並びは24×24×6=3456通り
合わせて124416通り

k=7のとき、帽子の並び順は192通り
(3,2,2)の帽子の並び順は3×38=114通りで、人の並びは24×12×12×114=393984通り
(3,3,1)の帽子の並び順は3×18=54通りで、人の並びは24×24×4×54=124416通り
(4,2,1)の帽子の並び順は6×3=18通りで、人の並びは24×12×4×18=20736通り
(4,3,0)の帽子の並び順は6×1=6通りで、人の並びは24×24×6=3456通り
合わせて542592通り

……あってるのかな？母関数を作るのは難しそうな気がしますねえ。


　ａｔさんが考察されました。（平成２８年９月２６日付け）

　人を区別する方針で回答します。求める場合の数を a(k) とすると、a(k)の母関数は次式で
与えられます。

Σ_k=0〜∞ a(k)z^k

=∫₀^∞(e^-x(1+Σ_p=1〜4Σ_j=0〜p-1(-1)^j*binomial(4,p)*p!*binomial(p-1,j)*x^p-j/(p-j)!z^p)³)

　 Maxima での計算結果から、例えば、a(7)=542592、a(8)=1980288 などが読み取れます。

　一般には次のようになります。

　n*m人を、n 人ずつの m 個の グループに分けておく。（グループ毎に帽子の色を統一して
おく。）

　このn*m人から任意のk人を選び横一列にしたとき、同じ色の帽子が隣に並ばない並び方

が全部でa(k)通りあるとすると、a(k)の母関数は次式で与えられる。

Σ_k=0〜∞ a(k)z^k

=∫₀^∞(e^-x(1+Σ_p=1〜nΣ_j=0〜p-1(-1)^j*binomial(n,p)*p!*binomial(p-1,j)*x^p-j/(p-j)!z^p)^m)


　ＧＡＩさんからのコメントです。（平成２８年９月２７日付け）

　DD++さん、atさん　ありがとうございます。樹形図的に調べて、k=7 まで出していたんです
が、DD++さんのとk=7だけ違っていたので調べ直したら、自分の調査不足を発見し（樹形図
が余りに枝分かれしている。）、DD++さんの分析を確認したら正しいことがわかりました。

　atさんは母関数で一気に解決することが出来ると幾度かの投稿の様子を見ていて思って
いたんですが、今度も鮮やかな式（思ってもいない式）を構成されました。

　これを私はPARIで確かめたんですが、∞ の計算がMaximaみたいにinfのコマンドがないの
で、10^8で近似させてみたら

15095811.34998753331260152652*z^12 + 19906558.94756758729807395898*z^11 +
13146623.58519792175993917451*z^10 + 5847552.015766794072731820142*z^9 +
1980288.005093222307890290965*z^8 + 542591.9999684705414558039428*z^7 +
124415.9999853039266181118922*z^6 + 24768.00000000332671409990008*z^5 +
4320.000000011939836120305724*z^4 + 672.0000000000005427881490176*z^3 +
95.99999999999759693365670607*z^2 + 12.00000000000000116708675951*z +
1.000000000000000054329126803

となり、z^9位までは読み取れそうです。さらに一般の母関数まで構成されていて驚きました。
これを作り出すとき、atさんの頭の中はどの様な思考回路が働いているのですか？もし何か
しらのあらすじを説明してもらえればありがたいです。


　ａｔさんからのコメントです。（平成２８年９月２７日付け）

　PARIでやる場合には、

sum(r=0,12,r!*polcoeff((1+sum(p=1,4,sum(j=0,p-1,(-1)^j*binomial(4,p)*p!*binomial(p-1,j)*x^(p-j)/(p-j)!*z^p)))^3,r,x))

と打ち込めばうまくいきます。

＜あらすじの説明＞

　私は包除原理を使って解くことを考えました。今回のように、いくつかの文字を、同じ文字
が隣接しないように並べる並べ方の総数を計算する場合、包除原理はとても有効な手段で
す。

　包除原理を使って問題を解く場合、同じ文字同士が隣接する状況を考えて、その隣接した
２つ(もしくはそれ以上)の文字はひとつの文字とみなして計算します。

　例えば、18個の文字　A A A A A A B B B B B B C C C C C C　があって、これら18個の
文字を横一列に並べるとき、同じ文字同士が隣接しないように並べる並べ方は全部で何通
りあるか？　という問題を解いてみます。

　文字A同士の隣接が発生する可能性のある箇所は5箇所です。この5箇所のうち、どれか
1箇所で隣接が発生すれば、文字Aたちは 6-1=5個の文字として計算することができます。

　また、この5箇所のうち、どれか2箇所で隣接が発生すれば、文字Aたちは 6-2=4個の文
字として計算することができます。

　一般には、この5箇所のうち、どれかk箇所で隣接が発生すれば、文字Aたちは 6-k個の文
字として計算することができます。

　よって、文字Aに関する数え上げ多項式は、Σ[k=0,5]binomial(5,k)*(-1)^k*(x^(6-k))/(6-k)!
となります。

　文字B、文字Cに対しても全く同じ状況です。

　よって、これら18個の文字に関する数え上げ多項式は、

　(Σ[k=0,5]binomial(5,k)*(-1)^k*(x^(6-k))/(6-k)!)^3

ということになります。

　よって、求める場合の数は、

　　Σ[p=0,18](p!)*([x^p](Σ[k=0,5]binomial(5,k)*(-1)^k*(x^(6-k))/(6-k)!)^3)

という計算式で計算できます。この計算をPARIで実行してみると、

sum(p=0,18,p!*polcoeff((sum(k=0,5,binomial(5,k)*(-1)^k*(x^(6-k))/(6-k)!))^3,p,x))=48852

となります。この計算は積分を用いて、

∫[x=0,∞](e^(-x))*(Σ[k=0,5]binomial(5,k)*(-1)^k*(x^(6-k))/(6-k)!)^3)dx=48852

とすることもできます。（→　参考）


　ＧＡＩさんからのコメントです。（平成２８年９月２９日付け）

　{A,A,A,A,B,B,B,B,C,C,C,C}のグループ分け後の配列に対し、母関数の対応の仕方を教えて
もらったので、一般に i の要素が i 個含まれる{1,2,2,3,3,3,4,4,4,4,･･･････,n,n,n,････,n}を全て並
べたとき、隣が同じ数字が並ばない並び方が何通り（J(n)）作れるか？について挑戦してみま
した。

J(n)=sum(p=0,n*(n+1)/2,p!*polcoeff(prod(j=0,n-1,sum(k=0,j,(-1)^k*binomial(j,k)*x^(j+1-k)/(j+1-k)!)),p,x))

と組んで走らせると、

J(1)=1
J(2)=1
J(3)=10
J(4)=1074
J(5)=1637124
J(6)=45156692400
J(7)=27230193578558160
J(8)=420296434943941609215120
J(9)=190200071567439616748736269178720
J(10)=2843464512159537301384360263178682136716160
････････････････････････････････・

　そこで、この数列を例の整数列大辞典で検索しますと、「A190945」が現れました。


　ａｔさんからのコメントです。（平成２８年９月２９日付け）

　上記の計算式は、2012年の9月に私がOEISに登録申請をした計算式と同様のものです。
今回、GAIさんは、この計算式を自力で導き出されたのですね。これで私もこのサイト(私的
数学塾・出会いの泉)に来た甲斐がありました。


　Seiichi　Manyamaさんからのコメントです。（平成２８年９月３０日付け）

　「A190945」に類する問題は、「math.stackexchange.com」に結構載っており、似た解法で
いけます。考え方とコードについては、過去ブログで書いたことがあるので参考になれば幸
いです。