Dear Thotsaporn, (and Tipaluck and Doron),

I looked at your preprint on double deficiencies and wanted to share two findings
about the open problem for Av(123).

First, there is a polynomial-time dynamic program for

  f_123(n,x) = sum_{pi in Av_n(123)} x^{DD(pi)}.

Given pi in Av_n(123), complement its values by setting
sigma(i)=n+1-pi(i). Then sigma avoids 321. Encode sigma by the two zero-one
words

  A_i = [sigma(i)>i],
  B_j = [j is an excedance value of sigma].

If alpha_i and beta_i are their prefix sums and r is the number of
excedances, the valid codes are exactly those satisfying

  alpha_n=beta_n=r,                 beta_i <= alpha_{i-1}  (1<=i<=n).

Indeed, if e_1<...<e_r and v_1<...<v_r are the excedance positions and
values, this condition is equivalent to e_s<v_s. Matching the two lists in
increasing order, and doing the same for their complements, recovers sigma.

For q=n+1-k, the double-deficiency condition translates to

  sigma(k)>q  and  sigma^{-1}(q)>k.

These are determined solely by A_k, B_q, alpha_k, and beta_q. Explicitly,
sigma(k)>q is equivalent to beta_q<alpha_k when A_k=1, and to
q-beta_q<k-alpha_k when A_k=0. Similarly, sigma^{-1}(q)>k is equivalent to
alpha_k<beta_q when B_q=1, and to k-alpha_k<q-beta_q when B_q=0.

This suggests processing the symmetric positions k and n+1-k together. For
each fixed r, a state records the four numbers of A- and B-ones already placed
at the left and right ends, together with the polynomial weight accumulated so
far. Each step chooses the next four bits, checks the two local forms of the
prefix condition, and multiplies by x for each newly determined double
deficiency. The middle step retains precisely those states having r ones in
both words. Summing over r gives f_123(n,x). The resulting algorithm uses
polynomially many states; a crude bound for computing all coefficients is
O(n^7) integer additions and O(n^5) stored coefficients.

Second, real-rootedness holds for the resulting polynomials through n=13 but
fails at n=14. The first counterexample is

  f_123(14,x) = 1028224 + 1215532 x + 385068 x^2
                + 44308 x^3 + 1308 x^4.
 Its approximate zeros are

  -22.5994238025,  -1.3122151595,
  -4.9814893875 ± 1.3010768352 i.

Best regards,
Per Alexandersson