Formula for [k]^n(p) where p a pattern of length 4

1. The pattern 1112:
|[2]^n(1112)|=1+n+binomial(n,2)+binomial(n,3),

|[3]^n(1112)|=1+2*n+4*binomial(n,2)+8*binomial(n,3)+13*binomial(n,4)+16*binomial(n,5)+10*binomial(n,6),

|[4]^n(1112)|=1+3*n+9*binomial(n,2)+27*binomial(n,3)+75*binomial(n,4)+185*binomial(n,5)+381*binomial(n,6)
+601*binomial(n,7)+616*binomial(n,8)+280*binomial(n,9),

|[5]^n(1112)|=1+4*n+16*binomial(n,2)+64*binomial(n,3)+246*binomial(n,4)+884*binomial(n,5)+2886*binomial(n,6)
+8278*binomial(n,7)+19977*binomial(n,8)+38128*binomial(n,9)+52156*binomial(n,10)
+43120*binomial(n,11)+15400*binomial(n,12).

2. The pattern 1121:
|[2]^n(1121)|=1+n+binomial(n,2)+binomial(n,3),

|[3]^n(1121)|=1+2*n+4*binomial(n,2)+8*binomial(n,3)+13*binomial(n,4)+16*binomial(n,5)+10*binomial(n,6),

|[4]^n(1121)|=1+3*n+9*binomial(n,2)+27*binomial(n,3)+75*binomial(n,4)+185*binomial(n,5)+381*binomial(n,6)
+601*binomial(n,7)+616*binomial(n,8)+280*binomial(n,9),

|[5]^n(1121)|=1+4*n+16*binomial(n,2)+64*binomial(n,3)+246*binomial(n,4)+884*binomial(n,5)+2886*binomial(n,6)
+8278*binomial(n,7)+19977*binomial(n,8)+38128*binomial(n,9)+52156*binomial(n,10)
+43120*binomial(n,11)+15400*binomial(n,12).

3. The pattern 1122:
|[2]^n(1122)|=1+n+binomial(n,2)+binomial(n,3),

|[3]^n(1122)|=1+2*n+4*binomial(n,2)+8*binomial(n,3)+13*binomial(n,4)+14*binomial(n,5)+10*binomial(n,6),

|[4]^n(1122)|=1+3*n+9*binomial(n,2)+27*binomial(n,3)+75*binomial(n,4)+177*binomial(n,5)+339*binomial(n,6)
+505*binomial(n,7)+504*binomial(n,8)+280*binomial(n,9),

|[5]^n(1122)|=1+4*n+16*binomial(n,2)+64*binomial(n,3)+246*binomial(n,4)+864*binomial(n,5)+2676*binomial(n,6)
+7144*binomial(n,7)+15961*binomial(n,8)+28444*binomial(n,9)+38116*binomial(n,10)
+33880*binomial(n,11)+15400*binomial(n,12),

4. The pattern 1212:
|[2]^n(1212)|=1+n+binomial(n,2)+binomial(n,3),

|[3]^n(1212)|=1+2*n+4*binomial(n,2)+8*binomial(n,3)+13*binomial(n,4)+14*binomial(n,5)+7*binomial(n,6)
+binomial(n,7),

|[4]^n(1212)|=1+3*n+9*binomial(n,2)+27*binomial(n,3)+75*binomial(n,4)+177*binomial(n,5)
+327*binomial(n,6)+425*binomial(n,7)+355*binomial(n,8)+179*binomial(n,9)
+50*binomial(n,10)+6*binomial(n,11),

5. The pattern 1221:
|[2]^n(1221)|=1+n+binomial(n,2)+binomial(n,3),

|[3]^n(1221)|=1+2*n+4*binomial(n,2)+8*binomial(n,3)+13*binomial(n,4)+14*binomial(n,5)+8*binomial(n,6),

|[4]^n(1221)|=1+3*n+9*binomial(n,2)+27*binomial(n,3)+75*binomial(n,4)+177*binomial(n,5)+331*binomial(n,6)
+449*binomial(n,7)+382*binomial(n,8)+152*binomial(n,9),

6. The pattern 1123:
|[3]^n(1123)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1123)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+7*2^(n-6)*binomial(n,6),

|[5]^n(1123)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+259*2^(n-6)*binomial(n,6)+321*2^(n-7)*binomial(n,7)
+258*2^(n-8)*binomial(n,8)+106*2^(n-9)*binomial(n,9),

|[6]^n(1123)|=2^n+4*2^(n-1)*n+16*2^(n-2)*binomial(n,2)+64*2^(n-3)*binomial(n,3)+236*2^(n-4)*binomial(n,4)
+764*2^(n-5)*binomial(n,5)+2111*2^(n-6)*binomial(n,6)+4834*2^(n-7)*binomial(n,7)
+8866*2^(n-8)*binomial(n,8)+12456*2^(n-9)*binomial(n,9)+12577*2^(n-10)*binomial(n,10)
+8130*2^(n-11)*binomial(n,11)+2575*2^(n-12)*binomial(n,12),

7. The pattern 1132:
|[3]^n(1132)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1132)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+7*2^(n-6)*binomial(n,6),

|[5]^n(1132)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+259*2^(n-6)*binomial(n,6)+321*2^(n-7)*binomial(n,7)
+258*2^(n-8)*binomial(n,8)+106*2^(n-9)*binomial(n,9),

|[6]^n(1132)|=2^n+4*2^(n-1)*n+16*2^(n-2)*binomial(n,2)+64*2^(n-3)*binomial(n,3)+236*2^(n-4)*binomial(n,4)
+764*2^(n-5)*binomial(n,5)+2111*2^(n-6)*binomial(n,6)+4834*2^(n-7)*binomial(n,7)
+8866*2^(n-8)*binomial(n,8)+12456*2^(n-9)*binomial(n,9)+12577*2^(n-10)*binomial(n,10)
+8130*2^(n-11)*binomial(n,11)+2575*2^(n-12)*binomial(n,12),

8. The pattern 1213:
|[3]^n(1213)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1213)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+6*2^(n-6)*binomial(n,6)+2^(n-7)*binomial(n,7),

|[5]^n(1213)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+253*2^(n-6)*binomial(n,6)+301*2^(n-7)*binomial(n,7)
+242*2^(n-8)*binomial(n,8)+124*2^(n-9)*binomial(n,9)+37*2^(n-10)*binomial(n,10)
+5*2^(n-11)*binomial(n,11),

9. The pattern 1223:
|[3]^n(1223)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1223)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+6*2^(n-6)*binomial(n,6),

|[5]^n(1223)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+253*2^(n-6)*binomial(n,6)+295*2^(n-7)*binomial(n,7)
+213*2^(n-8)*binomial(n,8)+71*2^(n-9)*binomial(n,9),

|[6]^n(1223)|=2^n+4*2^(n-1)*n+16*2^(n-2)*binomial(n,2)+64*2^(n-3)*binomial(n,3)+236*2^(n-4)*binomial(n,4)
+764*2^(n-5)*binomial(n,5)+2090*2^(n-6)*binomial(n,6)+4652*2^(n-7)*binomial(n,7)
+8084*2^(n-8)*binomial(n,8)+10424*2^(n-9)*binomial(n,9)+9288*2^(n-10)*binomial(n,10)
+5064*2^(n-11)*binomial(n,11)+1266*2^(n-12)*binomial(n,12),

10. The pattern 1231:
|[3]^n(1231)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1231)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+6*2^(n-6)*binomial(n,6),

|[5]^n(1231)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+254*2^(n-6)*binomial(n,6)+297*2^(n-7)*binomial(n,7)
+215*2^(n-8)*binomial(n,8)+71*2^(n-9)*binomial(n,9),

11. The pattern 1232:
|[3]^n(1232)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1232)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+6*2^(n-6)*binomial(n,6),

|[5]^n(1232)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+253*2^(n-6)*binomial(n,6)+295*2^(n-7)*binomial(n,7)
+213*2^(n-8)*binomial(n,8)+71*2^(n-9)*binomial(n,9)

12. The pattern 1312:
|[3]^n(1312)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1312)|=1+3*2^(n-1)*n+3*2^(n-2)*binomial(n,2)+9*2^(n-3)*binomial(n,3)+11*2^(n-4)*binomial(n,4)
+13*2^(n-5)*binomial(n,5)+3*2^(n-6)*binomial(n,6),

|[5]^n(1312)|=12-11*2^n+15*2^(n-1)*n-3*2^(n-2)*binomial(n,2)+39*2^(n-3)*binomial(n,3)+59*2^(n-4)*binomial(n,4)
+165*2^(n-5)*binomial(n,5)+231*2^(n-6)*binomial(n,6)+257*2^(n-7)*binomial(n,7)
+96*2^(n-8)*binomial(n,8)+12*2^(n-9)*binomial(n,9),

13. The pattern 1322:
|[3]^n(1312)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1312)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)
+12*2^(n-4)*binomial(n,4)+12*2^(n-5)*binomial(n,5)+6*2^(n-6)*binomial(n,6),

|[5]^n(1312)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+253*2^(n-6)*binomial(n,6)+295*2^(n-7)*binomial(n,7)
+213*2^(n-8)*binomial(n,8)+71*2^(n-9)*binomial(n,9),

14. The pattern 1332:
|[3]^n(1332)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(1332)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+6*2^(n-6)*binomial(n,6),

|[5]^n(1332)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+253*2^(n-6)*binomial(n,6)+295*2^(n-7)*binomial(n,7)
+213*2^(n-8)*binomial(n,8)+71*2^(n-9)*binomial(n,9),

15. The pattern 2132:
|[3]^n(2132)|=2^n+2^(n-1)*n+2^(n-2)*binomial(n,2)+2^(n-3)*binomial(n,3),

|[4]^n(2132)|=2^n+2*2^(n-1)*n+4*2^(n-2)*binomial(n,2)+8*2^(n-3)*binomial(n,3)+12*2^(n-4)*binomial(n,4)
+12*2^(n-5)*binomial(n,5)+6*2^(n-6)*binomial(n,6),

|[5]^n(2132)|=2^n+3*2^(n-1)*n+9*2^(n-2)*binomial(n,2)+27*2^(n-3)*binomial(n,3)+71*2^(n-4)*binomial(n,4)
+153*2^(n-5)*binomial(n,5)+253*2^(n-6)*binomial(n,6)+295*2^(n-7)*binomial(n,7)
+213*2^(n-8)*binomial(n,8)+71*2^(n-9)*binomial(n,9)

16. The pattern p where p=1234,1243,1432,2143:
|[4]^n(p)|=3^n+3^(n-1)*n+3^(n-2)*binomial(n,2)+3^(n-3)*binomial(n,3),

|[5]^n(p)|=3^n+2*3^(n-1)*n+4*3^(n-2)*binomial(n,2)+8*3^(n-3)*binomial(n,3)+11*3^(n-4)*binomial(n,4)
+10*3^(n-5)*binomial(n,5)+5*3^(n-6)*binomial(n,6),

|[6]^n(p)|=3^n+3*3^(n-1)*n+9*3^(n-2)*binomial(n,2)+27*3^(n-3)*binomial(n,3)+66*3^(n-4)*binomial(n,4)
+126*3^(n-5)*binomial(n,5)+183*3^(n-6)*binomial(n,6)+189*3^(n-7)*binomial(n,7)
+126*3^(n-8)*binomial(n,8)+42*3^(n-9)*binomial(n,9),

|[7]^n(p)|=3^n+4*3^(n-1)*n+16*3^(n-2)*binomial(n,2)+64*3^(n-3)*binomial(n,3)+221*3^(n-4)*binomial(n,4)
+632*3^(n-5)*binomial(n,5)+1478*3^(n-6)*binomial(n,6)+2772*3^(n-7)*binomial(n,7)
+4074*3^(n-8)*binomial(n,8)+4536*3^(n-9)*binomial(n,9)+3612*3^(n-10)*binomial(n,10)
+1848*3^(n-11)*binomial(n,11)+462*3^(n-12)*binomial(n,12)

|[8]^n(p)|=3^n+5*3^(n-1)*n+25*3^(n-2)*binomial(n,2)+125*3^(n-3)*binomial(n,3)+555*3^(n-4)*binomial(n,4)
+2103*3^(n-5)*binomial(n,5)+6735*3^(n-6)*binomial(n,6)+18075*3^(n-7)*binomial(n,7)
+40290*3^(n-8)*binomial(n,8)+73770*3^(n-9)*binomial(n,9)+109206*3^(n-10)*binomial(n,10)
+127710*3^(n-11)*binomial(n,11)+113850*3^(n-12)*binomial(n,12)+72930*3^(n-13)*binomial(n,13)
+30030*3^(n-14)*binomial(n,14)+6006*3^(n-15)*binomial(n,15)

|[9]^n(p)|=3^n+6*3^(n-1)*n+36*3^(n-2)*binomial(n,2)+216*3^(n-3)*binomial(n,3)+1170*3^(n-4)*binomial(n,4)
+5508*3^(n-5)*binomial(n,5)+22338*3^(n-6)*binomial(n,6)+77688*3^(n-7)*binomial(n,7)
+230823*3^(n-8)*binomial(n,8)+583410*3^(n-9)*binomial(n,9)+1247076*3^(n-10)*binomial(n,10)
+2235816*3^(n-11)*binomial(n,11)+3322836*3^(n-12)*binomial(n,12)+4025736*3^(n-13)*binomial(n,13)
+3880305*3^(n-14)*binomial(n,14)+2867436*3^(n-15)*binomial(n,15)+1528956*3^(n-16)*binomial(n,16)
+525096*3^(n-17)*binomial(n,17)+87516*3^(n-18)*binomial(n,18),

|[10]^n(p)|=3^n+7*3^(n-1)*n+49*3^(n-2)*binomial(n,2)+343*3^(n-3)*binomial(n,3)+2191*3^(n-4)*binomial(n,4)
+12313*3^(n-5)*binomial(n,5)+60361*3^(n-6)*binomial(n,6)+257407*3^(n-7)*binomial(n,7)
+953554*3^(n-8)*binomial(n,8)+3064558*3^(n-9)*binomial(n,9)+8527666*3^(n-10)*binomial(n,10)
+20482462*3^(n-11)*binomial(n,11)+42268534*3^(n-12)*binomial(n,12)+74452378*3^(n-13)*binomial(n,13)
+110916091*3^(n-14)*binomial(n,14)+137998861*3^(n-15)*binomial(n,15)+140882742*3^(n-16)*binomial(n,16)
+115068954*3^(n-17)*binomial(n,17)+72390318*3^(n-18)*binomial(n,18)+32978946*3^(n-19)*binomial(n,19)
+9699690*3^(n-20)*binomial(n,20)+1385670*3^(n-21)*binomial(n,21),

17. The pattern 1324:
|[4]^n(1324)|=3^n+3^(n-1)*n+3^(n-2)*binomial(n,2)+3^(n-3)*binomial(n,3),

|[5]^n(1324)|=3^n+2*3^(n-1)*n+4*3^(n-2)*binomial(n,2)+8*3^(n-3)*binomial(n,3)+11*3^(n-4)*binomial(n,4)
+10*3^(n-5)*binomial(n,5)+5*3^(n-6)*binomial(n,6)+3^(n-7)*binomial(n,7),

|[6]^n(1324)|=3^n+3*3^(n-1)*n+9*3^(n-2)*binomial(n,2)+27*3^(n-3)*binomial(n,3)+66*3^(n-4)*binomial(n,4)
+126*3^(n-5)*binomial(n,5)+183*3^(n-6)*binomial(n,6)+197*3^(n-7)*binomial(n,7)
+152*3^(n-8)*binomial(n,8)+80*3^(n-9)*binomial(n,9)+26*3^(n-10)*binomial(n,10)
+4*3^(n-11)*binomial(n,11)

|[7]^n(1324)|=3^n+4*3^(n-1)*n+16*3^(n-2)*binomial(n,2)+64*3^(n-3)*binomial(n,3)+221*3^(n-4)*binomial(n,4)
+632*3^(n-5)*binomial(n,5)+1478*3^(n-6)*binomial(n,6)+2808*3^(n-7)*binomial(n,7)
+4308*3^(n-8)*binomial(n,8)+5295*3^(n-9)*binomial(n,9)+5152*3^(n-10)*binomial(n,10)
+3895*3^(n-11)*binomial(n,11)+2219*3^(n-12)*binomial(n,12)+904*3^(n-13)*binomial(n,13)
+239*3^(n-14)*binomial(n,14)+33*3^(n-15)*binomial(n,15)+3^(n-16)*binomial(n,16)

18. The pattern 1342:
|[4]^n(1342)|=3^n+3^(n-1)*n+3^(n-2)*binomial(n,2)+3^(n-3)*binomial(n,3),

|[5]^n(1342)|=3^n+2*3^(n-1)*n+4*3^(n-2)*binomial(n,2)+8*3^(n-3)*binomial(n,3)+11*3^(n-4)*binomial(n,4)
+10*3^(n-5)*binomial(n,5)+4*3^(n-6)*binomial(n,6),

|[6]^n(1342)|=3^n+3*3^(n-1)*n+9*3^(n-2)*binomial(n,2)+27*3^(n-3)*binomial(n,3)+66*3^(n-4)*binomial(n,4)
+126*3^(n-5)*binomial(n,5)+176*3^(n-6)*binomial(n,6)+168*3^(n-7)*binomial(n,7)
+96*3^(n-8)*binomial(n,8)+24*3^(n-9)*binomial(n,9),

19. The pattern 1423:
|[4]^n(1423)|=3^n+3^(n-1)*n+3^(n-2)*binomial(n,2)+3^(n-3)*binomial(n,3),

|[5]^n(1423)|=2^n+3*3^(n-1)*n+3*3^(n-2)*binomial(n,2)+9*3^(n-3)*binomial(n,3)+10*3^(n-4)*binomial(n,4)
+11*3^(n-5)*binomial(n,5)+3*3^(n-6)*binomial(n,6)

|[6]^n(1423)|=13*2^n+2^(n-1)*n-12*3^n+15*3^(n-1)*n-2*3^(n-2)*binomial(n,2)+37*3^(n-3)*binomial(n,3)
+57*3^(n-4)*binomial(n,4)+134*3^(n-5)*binomial(n,5)+169*3^(n-6)*binomial(n,6)
+167*3^(n-7)*binomial(n,7)+76*3^(n-8)*binomial(n,8)+12*3^(n-9)*binomial(n,9)

20. The pattern 2413:
|[4]^n(2413)|=3^n+3^(n-1)*n+3^(n-2)*binomial(n,2)+3^(n-3)*binomial(n,3),

|[5]^n(2413)|=10*2^n+4*2^(n-1)*n+2^(n-2)*binomial(n,2)-9*3^n+8*3^(n-1)*n+3^(n-2)*binomial(n,2)
+9*3^(n-3)*binomial(n,3)+11*3^(n-4)*binomial(n,4)+10*3^(n-5)*binomial(n,5)
+2*3^(n-6)*binomial(n,6)

|[6]^n(2413)|=96*2^n+28*2^(n-1)*n+5*2^(n-2)*binomial(n,2)-95*3^n+71*3^(n-1)*n-36*3^(n-2)*binomial(n,2)
+54*3^(n-3)*binomial(n,3)+52*3^(n-4)*binomial(n,4)+132*3^(n-5)*binomial(n,5)
+167*3^(n-6)*binomial(n,6)+137*3^(n-7)*binomial(n,7)+44*3^(n-8)*binomial(n,8)
+4*3^(n-9)*binomial(n,9)

To present this table: the program in Maple runs ~7397sec, and the program in C++ runs ~280sec