PUMaC 2013 · 组合（B 组） · 第 4 题

PUMaC 2013 — Combinatorics (Division B) — Problem 4

[ 4 ] Mereduth has many red boxes and many blue boxes. Coloon has placed five green boxes in a row on the ground, and Mereduth wants to arrange some number of her boxes on top of his row. Assume that each box must be placed so that it straddles two lower boxes. Including the one with no boxes, how many arrangements can Mereduth make?

解析

[ 4 ] Mereduth has many red boxes and many blue boxes. Coloon has placed five green boxes in a row on the ground, and Mereduth wants to arrange some number of her boxes on top of his row. Assume that each box must be placed so that it straddles two lower boxes. Including the one with no boxes, how many arrangements can Mereduth make? Solution Let K be the number of arrangements we can make on n boxes. On top of the n n green boxes, Mereduth has some string of boxes with no gaps, possibly of length zero. If this is i of length i , we find that the number of further arrangements that can be made is 2 K K . i n − i − 1 2 Then we have K = 1, K = 1, K = 2 K K + K K = 3, K = 4 K K + 2 K + K K = 0 1 2 1 0 0 1 3 2 0 0 2 1 4(3) + 2 + 3 = 17, K = 8 K K + 4 K K + 2 K K + K K = 9(17) + 6(3) = 171, and 4 3 0 2 1 1 2 0 3 2 K = 17 × 171 + 10 × 17 + 4 × 3 = 2907 + 160 + 36 = 3113 5 So there are 3113 rearrangements.