Number of k-permutations that have odd number of an element

Question

I want to find a recurrence relation $h_k$ for the number of k-permutations of $\{\infty a,\infty b, \infty c, \infty d \}$ that have an odd number of a's.

I let $h_0=0$ because there is no odd number of $a$'s

Then $h_1=1$, for there is only one $a$

Also, this means that $h_2=6$ ($ab,ac,ad,ba,,ca,da$)

I am also pretty sure that $h_3=28 ([abb,abc,abd,acb,adb,acc,acd,adc,add]$ multiplied with 3 because the replacements of $a$, we have $27$, and then $aaa$ )

I am not able to figure out a formula for $h_n$ using the earlier terms.

Answer 1

Hint: Let $A_n$ be the number of $n-$permutations with an odd number of $a$. Let $B_n$ be the number of $n-$permuations with an even number of $ba$.

Hint: Establish some recurrence equations with a combinatorial argument:

Roll over if you want to see what these are

$A_n = 3A_{n-1} + B_{n-1}$, $B_n = A_{n-1} + 3 B_{n-1}$

Hint: Hence show that $A_{n+1} = 6A_n - 8A_{n-1}$. Solve it as a linear recurrence. with $A_0 = 0, A_1 = 1$. Note that this verifies $A_2 = 6, A_3 = 28$ like you calculated.

Hence, conclude that $A_n = 2^{2n-1} - 2^{n-1}$.