За­ме­тим, что буква Й может встре­чать­ся в слове не более од­но­го раза или не встре­чать­ся со­всем. Рас­смот­рим два слу­чая.

Пусть буква Й стоит на вто­ром месте. Тогда, по­сколь­ку на со­сед­них по­зи­ци­ях не может сто­ять буква Е, ко­ли­че­ство воз­мож­ных слов равно 4 · 1 · 4 · 5 · 5 · 5. Также буква Й может сто­ять на тре­тьем, четвёртом и пятом месте. Зна­чит, всего слов, в ко­то­рых ис­поль­зу­ет­ся буква Й, 4 · 1 · 4 · 5 · 5 · 5 · 4  =  8000.

Если буква Й не ис­поль­зу­ет­ся, ко­ли­че­ство воз­мож­ных слов равно 5 · 5 · 5 · 5 · 5 · 5  =  15625.

Таким об­ра­зом, всего воз­мож­ных слов 8000 + 15625  =  23625.

Ответ: 23625.

При­ведём дру­гое ре­ше­ние на языке Python.

При­ведём ре­ше­ние Сер­гея Донец на языке PascalABC.NET.

begin
'А, Н, Д, Р, Е, Й'.Remove(', ')
.Cartesian(6)
.Where(s->s.CountOf('Й')<=1) // не более од­но­го раза
.Where(s->not s.ismatch('ЙЕ|ЕЙ'))//не может сто­ять рядом с бук­вой Е
.Where(s->s[1]<>'Й') // не может сто­ять на пер­вом месте
.Where(s->s[^1]<>'Й') // не может сто­ять на по­след­нем месте
.Count.Print; // 23625
end.