Permutation - how to order 6 elements out of 13 with 3 conditions

Elements = [
A, A, 
A, A,
B, B, B,
W, W, W, W, W, W ]

Slots: _ _ _ _ _ _

Conditions:

There must always be at least one 'W' in one of the 6 slots
A's must always come in pairs (AA)
B's must always come in threes (BBB)

Example: AAWBBB

I know about the n! / (n-r)! formula. But I am unsure of what to do, in order to implement the grouping of AA and BBB, and the condition of having at least one W.

I am pretty sure that the result is 22 different permutations, after enumerating with pen/paper - but I can't explain the math behind.

Can anyone clarify if these are permutations or combinations, I am still confused about that.

Edit: I've now written down the 22 permutations, so you can see the result:

W W W W W W
A A W W W W
W A A W W W
W W A A W W
W W W A A W
W W W W A A
A A A A W W
A A W A A W
A A W W A A
W A A A A W
W A A W A A
W W A A A A
B B B W W W
W B B B W W
W W B B B W
W W W B B B
B B B A A W
B B B W A A
W B B B A A
A A B B B W
A A W B B B
W A A B B B

You can write a recursion by thinking what the first letter will be. Let's denote

$$c(n, a, b, w) = \text{number of words of length n when can use a A's, b B's and w W's and following the given rules}$$

We have of course $c(n, a, b, w) = 0$ if any of the parameters is negative. And $c(0, a, b, w) = 1$ when $a,b,w \geq 0$. Then the recursion: The first letter can be either $w$ in which case you use up one W and the rest of the word is a word of length $n-1$ following the rules with one less W do use. If the first letter is an A the you must have another A following it and then the rest $n-2$ letters form a word with 2 fewer A's to use. Similarly you might have BBB in the beginning and then an $n-3$-word. All together

$$c(n, a,b,w) = c(n-1, a,b,w-1) + c(n-2, a-2,b,w) + c(n-3, a,b-3, w)$$

These are a bit cumbersome to tabulate because of the 4 parameters but it's ease to code up and indeed you get $c(6,4,3,6) = 22$.

For the nomenclature, I would just call these words with the letters $\{A, B, W\}$ They are more like permutations because the order matters but there can be repeated things and not every thing needs to be there so they are like, I guess you could call them partial permutations of a multiset.

Another way to calculate is with generating functions. We have three types of objects: W, AA and BBB. But because these have different lengths, we must weight them as $z, z^2$ and $z^3$. I found this question where formula is given (but each element is a single element, no blocks AA, BBB like here). I tried to implement it with SageMath but it doesn't work :(

#This is the recursion formula
def c(n, a, b, w):
    if any(t<0 for t in (n,a,b,w)): return 0
    if n==0: return 1
    return c(n-1,a,b,w-1) + c(n-2,a-2,b,w) + c(n-3,a,b-3,w)

print(c(6,4,3,6))


#Let's try with generating function
def multiCulti(n, a,b,w):
    R.<z> = PolynomialRing(QQ, 1)
    p = product(sum(z^(t*j)/factorial(j) for j in range(s+1)) for t,s in zip((1,2,3), (w, a//2, b//3)))
    return factorial(n)*p.coefficient({z: n})

print(multiCulti(6, 4,3,6))

Can someone spot the error or doesn't the weighting of block lenghts work like that?

EDIT: I think I now understand why it doesn't work. You should divide by the ways you can reorder among the blocks. But this can't be done like in alltogether in the end since you don't know how many there are of each sort. The $n$ thinks you have $6$ objects but in reality you might have fewer if there are AA's or BBB's. So that $n!$ is wrong! But if we introduce two other variables $z_A$ and $z_B$ to count how many AA's and BBB's appear...

Permutation - how to order 6 elements out of 13 with 3 conditions

Related

Recent Posts