Uma maneira bem força bruta de resolver está abaixo. Note que em vez de calcular o número de possibilidades estamos devolvendo uma lista com cada uma das possibilidades, para contar as possibilidades é só contar os elementos da lista
import itertools
def adiciona_permutacoes (lista):
listao = []
for i in range(len(lista)):
for e in itertools.permutations(lista[i], len(lista[i])):
aux = ''
for j in range(len(e)):
aux = aux + str(e[j])
listao.append(aux)
return listao
def number_of_ways(n,lista=[]):
lista1 =['A']
lista2 = ['AA', 'B']
lista3 = ['AAA', 'BA', 'C', 'AB']
if n==1: return lista1
if n==2: return lista2
if n==3: return lista3
if n>3:
for i in range(1,n-1):
if i<=n-1:
for a in range(i):
for b in range(n-i):
aux = number_of_ways(i)[a]+number_of_ways(n-i)[b]
lista.append(aux)
lista = list(set(lista)-set(number_of_ways(n-1)))
return lista
if __name__=='__main__':
# para n=6
lista_com_permutações = list(set(adiciona_permutacoes(number_of_ways(6))))
#para a contagem com n=6
contagem = len(list(set(adiciona_permutacoes(number_of_ways(6)))))
print(lista_com_permutações)
print(contagem)
O resultado para alguns n selecionados segue abaixo
n=4
['AC', 'AAAA', 'ABA', 'AAB', 'BAA', 'CA', 'BB']
n=5
['CB', 'ABB', 'BBA', 'BC', 'BAB', 'AAAAA', 'BAAA', 'AABA', 'AAAB', 'ABAA']