同じ数字が隣り合わない並べ方

1,2,3,・・・,nの数字が書かれたカードが２枚ずつ、計2n枚ある。
この2n枚のカードを同じ数字が隣り合わないように横１列に並べる。
並べ方は何通りあるか。

n=2なら、2通り
n=3なら、30通り
n=4なら、864通り
ですが、一般解はどんな式になるでしょうか。

質問者からの補足コメント

• >はーい、質問、大小などの「別の縛り」は無いんですか？組み合わせだけでいいんですね、
  
  別の縛りはありません。
  組み合わせというより、順列ですね。
  
  n=2は、1212、2121の2通り
  n=3は、先頭2桁が12のとき、121323、123123、123132、123213、123231の5通りで、
  　先頭2桁が13、21、23、31、32も同様だから、5×6で30通り
  n=4も同じようにして数えれば、72×12=864通りとなっています。

  No.1の回答に寄せられた補足コメントです。 補足日時：2015/09/18 16:47

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2015/09/19 23:38

並べ方全体の集合を U, 「番号 k が隣接する」ような並べ方の集合を A(k) とすると, 求める数値は

|U - ∪A(k)|
だよね. これをバラすと, 「少なくとも k個の番号が隣接する」並べ方を数えて包除原理でゴリゴリ押せばいいってことになる.

最終的には
Σ(k: 0→n) (-1)^k (n choose k) (2n-k)!/2^(n-k)
かな?

この回答へのお礼

>Σ(k: 0→n) (-1)^k (n choose k) (2n-k)!/2^(n-k)

n≦8で合っていることをパソコンで検証できました。
これが正解なんでしょうね。

要は、
並べ方全体の数から、
1組が隣接する場合（1が隣接する場合、2が隣接する場合、3が隣接する場合・・・・）の数を引いて、
重複して引いているものがあるから、2組が隣接する場合（1,2が隣接する場合、1,3が隣接する場合、1,4が隣接する場合・・・・）の数を足して、
さらに、重複して足しているものがあるから、3組が隣接する場合の数を引いて・・・
ということを繰り返しているんでしょうか。

なんとなく分かりそうな気がしてきました。
ありがとうございました。

お礼日時：2015/09/20 11:26

No.2 回答者： stomachman 回答日時： 2015/09/19 17:16

「番号1からnのカードが2枚ずつ並んでいて、同じ番号が隣り合ってる場所がk箇所ある状態」をB(n,k) と書く事にし、その場合の数をφ(n,k)とする。

ご質問はφ(n,0)をお尋ねである。

　番号1からn-1のカードが2枚ずつ並んでいるとき、「両端と隙間」(2n-1)箇所のどこかに2枚のn番のカードを置いてB(n,k)にするには、2枚のn番のカードを：
(1) B(n-1,k+2)のとき、同じ番号が隣り合ってる場所(k+2)箇所から相異なる2箇所を選んで置く。(k+2)(k+1)/2通りある。
(2) B(n-1,k+1)のとき、同じ番号が隣り合ってる場所(k+1)箇所から1箇所と、同じ番号が隣り合っていない場所(2n-1-(k+1))箇所から1箇所を選んで置く。(k+1)(2n-2-k)通りある。
(3) B(n-1,k-1)のとき、同じ番号が隣り合っていない場所(2n-1-(k-1))箇所から1箇所選び、そこに2つまとめて置く。(2n-k)通りある。
(4) B(n-1,k)のとき、
　(4a) 同じ番号が隣り合っている場所k箇所から1箇所選び、そこに2つまとめて置く。k通りある。　あるいは、
　(4b) 同じ番号が隣り合っていない場所(2n-1-k)箇所から相異なる2箇所を選んで置く。(2n-k-1)(2n-k-2)/2通りある。
　これらは重複がない（と思うんだけど、大丈夫かな？）ので、
　　φ(n,k) = ((k+2)(k+1)/2)φ(n-1,k+2) + (k+1)(2n-2-k)φ(n-1,k+1)+(2n-k)φ(n-1,k-1)+ (k + (2n-1-k)(2n-1-k-1)/2)φ(n-1,k)
　境界条件は明らかに
　　0≦k≦n でないとき、φ(n,k)=0
　　φ(1,0)=0
　　φ(1,1)=1
ま、とりあえず、漸化式にはなった。
　これを眺めただけじゃ、φ(n,0)の一般項が簡単に表せる気は全然しないなー。「かなり易しい」というANo.1の計算方法との関係は興味のあるところ。

この回答へのお礼

回答ありがとうございます。

漸化式ができたようなので、具体的な数値計算はできますね。
でも２変数の漸化式を解くのはちょっと無理かなとも思います。

私が考えていたのは、φ(n,n)、φ(n,n-1)、φ(n,n-2)などの式を求めて、その式の傾向をつかめないかということでした。
φ(n,n)は、2枚1組でn組の順列になるので、
φ(n,n) = n!
φ(n,n-1)は、隣り合った(n-1)組に残り1組を隣り合わないように挿入すればいいので、
φ(n,n-1) = nC(n-1) * (n-1)! * nC2 = n(n-1)n!/2
φ(n,n-2)も、隣り合った(n-2)組に残り2組を隣り合わないように挿入することを考えれば、なんとか計算できますが、φ(n,n-3)から先はかなり難しく手がでません。

お礼日時：2015/09/19 22:39

No.1 回答者： doc_somday 回答日時： 2015/09/18 16:29

はーい、質問、大小などの「別の縛り」は無いんですか？組み合わせだけでいいんですね、かなり易しいよ、順列組み合わせの簡単な応用問題