with(combinat):

Help:=proc()
if args = NULL then
	print(`Count123Avoiders(n,r), Count123PlusAvoiders(k,n,r)`):
elif args = 'Count123Avoiders' then
	print(`Count123Avoiders(n,r) gives the number of words on the alphabet [n]^r which avoid 123.`):
	print(`For example: Count123Avoiders(10,4);`):
elif args = 'Count123PlusAvoiders' then
	print(`Count123PlusAvoiders(k,n,r) gives the number of words on the alphabet [n]^r which avoid both 123 and 1k(k-1)...2.`):
	print(`For example: Count123PlusAvoiders(7,10,3);`):
fi:
end:

Count123Avoiders:=proc(n,r)
Count123Avoiders1(r,n,0,0):
end:
 
Count123Avoiders1:=proc(r,a,b,c) local i:
option remember:
if (a=0 and b=0) then
 return(1):
fi:
if a < 0 or b<0 or c < 0 then 
 return(0):
fi:
add(Count123Avoiders1(r,i-1,r-1,r*(a-i)+c+b),i=1..a)+Count123Avoiders1(r,a,b-1,c)+Count123Avoiders1(r,a,b,c-1):
end:


#Count123PlusAvoiders(k,n,r) counts the number of words on the alphabet {1^r,2^r,...,a^r} that avoid both 123 and 1k(k-1)..32
Count123PlusAvoiders:=proc(k,n,r)
Count123PlusAvoiders1(k,r,n,0,[0$(k-2)]):
end:

#Count123PlusAvoiders1(k,r,a,b,L) counts the number of words on the alphabet {1^r,2^r,...a^r,(a+1)^b,(a+1+i)^L[i]} that avoid both 123 and 1k(k-1)..32 Note that L should have length k-2
Count123PlusAvoiders1:=proc(k,r,a,b,L) local i, lower_lim,extras,max_nonzero,output,Lp:
option remember:
#print(a,b,L):
if nops(L) <> k-2 then
 print(`L should have k-2 elements`):
 print(L):
 return(FAIL):
fi:
if (a=0 and b=0) then
 return(1):
fi:
if (a < 0 or b < 0) then
 return(0):
fi:
for i from 1 to nops(L) do
 if L[i] < 0 then
  return(0):
 fi:
od:
max_nonzero:=0:
for i from 1 to nops(L) do
 if L[i] > 0 then
  max_nonzero:=i:
 fi:
od:
extras:=[op(Nonzero([b,op(L)]))]:
output:=add(Count123PlusAvoiders1(k,r,i-1,r-1,[r$(a-i),op(extras),0$(i-a+k-2-nops(extras))]),i=a-k+nops(extras)+2..a):
output:=output+Count123PlusAvoiders1(k,r,a,b-1,L):
if max_nonzero >0 then
 Lp:=L:
 Lp[max_nonzero]:=Lp[max_nonzero]-1:
 output:=output+Count123PlusAvoiders1(k,r,a,b,Lp):
fi:
output:
end:

Nonzero:=proc(L) local i,output:
output:=[]:
for i from 1 to nops(L) do
 if L[i] <> 0 then
  output:=[op(output), L[i]]:
 fi:
od:
output:
end: