Another more general counting proof?

Question

Suppose A and B are disjoint finite sets with #(A) = n and #(B) = k with k# n. Give a formula
for the number of ways to form an ordered n + k - tuple so that no element of B is adjacent to
another element of B and no elements appear twice. Prove that your formula is correct.

Answer 1

Hrm.

Well, first off, k must be less than or equal to n+1, or you'd be forced to have an element of B next to another element of B.

First put down all the n elements of a, leaving spaces ( _ ) for elements of B.

_A_A_A_A....A_

There are (n+1) possible locations for an element of B.

So you have (n+1)Ck ways to fill those slots with an element of B.

There are n! ways to choose the A slots, and k! ways to choose the values of B, so I'd say the answer would be:

n!k!(n+1)!/[(n+1-k)!k!] or
n!(n+1)!/(n+1-k)!

What do you think?

Applying it to the other version of this question you asked:

5!(6!)/(6-3)! = 5 x 4 x 6 x 5 x 4 x 3 x 2 = 14,400

So it seems to work.

Answer 2

(n>=k). First choose the permutations of the set A. Then, for each permutation of the n elements, pick the "spaces" between the elements to put the k elements from B. Note there is a "space" at the beginning and the end. Now in the k spaces, choose a permutation of set B. this is:
nPn * (n+1)Ck * kPk