a(n) is the number of shallow permutations of length n that avoid 123.

Terms

a(0) =1a(1) =1a(2) =2a(3) =5a(4) =13a(5) =35a(6) =90a(7) =225a(8) =525a(9) =1181a(10) =2526a(11) =5289a(12) =10729a(13) =21583a(14) =42566a(15) =83909a(16) =163225a(17) =318713a(18) =616122a(19) =1198029a(20) =2309829a(21) =4483643a(22) =8635314a(23) =16750761a(24) =32247973a(25) =62538517a(26) =120378518a(27) =233428337a(28) =449294497a(29) =871206887