Number of expressions of a given length

Question

Define the expressions as follows:

1. x is an expression.
2. If S is an expression, then (S) is also an expression;
3. If S1 and S2 are expressions, then S1 + S2 and S1 - S2 are expressions.

In input to the program, a single integer N (0≤N≤10^6) is received.

The program should print the number of possible expressions of a given length N.

For example, if the input receives 3, then the answer will be 3. And if the input receives 5, the answer will be 11.

Because, possible expressions of length 3:

(x)
x + x
x − x

And possible expressions of length 5:

((x))
(x) + x
(x) − x
(x + x)
(x − x)
x + (x)
x + x + x
x + x − x
x − (x)
x − x + x
x − x − x

I immediately noticed that the answer to even numbers would be 0. I think this is obvious.

Further I thought that this task was somehow related to the Catalan Number, but I still didn't find the dependence.

But I managed to find another dependency. It can be noted that dropping the brackets, we get that for each subsequent N all previous combinations of expressions are saved and new ones are added with an additional x. And it is also known that the number of expressions with the amount of x equal to T (without brackets) can be expressed by the formula 2^(T-1)

Based on this, I can draw up an approximate formula for solving the problem.

C(n) = 1 + 2^1 * K(2) + 2^2 * K(3) + 2^3 * K(4) + ... + 2^(T-1) 

I add 1, since always from one X you can get any expression of odd length using brackets. K in this formula is the number of combinations of brackets for a specific amount of x.

My problem is that I do not understand how to calculate K. Perhaps my algorithm is fundamentally wrong. Tell me please how you would solve a similar problem.

Since the displayed answer can be very large, it is necessary to output its remainder by dividing by the number 998244353

Answer 1

Let's try to weed out duplicates. Reformulate the grammar as follows:

1. x is a term
2. if E is an expression, (E) is a term
3. if E is an expression and T is a term, then T, E + T and E - T are expressions

It is easy to see that this grammar, unlike the original one, is unambiguous, but generates the same language. So there are no duplicates, and counting expressions is a straightforward recurrence.

• T_2*N = E_2*N = 0
• T₁ = 1 (rule 1)
• T_N+2 = E_N (rule 2)
• E_N = T_N + 2 * Σ_i=1..N-1(E_i * T_N-i-1) (rule 3)

Here's a straightforward implementation in Haskell.

import Data.Function.Memoize

countExpressions = e where
  e = memoize e'
  t = memoize t'

  t' :: Integer -> Integer
  t' n | n `mod` 2 == 0 = 0
       | n < 0          = 0
       | n == 1         = 1
       | otherwise      = e (n-2)

  e' :: Integer -> Integer
  e' n | n `mod` 2 == 0 = 0
       | n < 0          = 0
       | n == 1         = 1
       | otherwise      = t n + 2 * sum [ e i * t (n - i - 1) | i <- [1 .. n - 1] ]

*Main> take 100 [countExpressions n | n <- [1, 3 ..]]
[1,3,11,45,197,903,4279,20793,103049,518859,2646723,
13648869,71039373,372693519,1968801519,10463578353,55909013009,
300159426963,1618362158587,8759309660445,47574827600981,
259215937709463,1416461675464871,7760733824437545,42624971294485657,
234643073935918683,1294379445480318899,7154203054548921813,
39614015909996567325,219721391307807180831,1220631504623087926239,
6791142807106951594977,37836272668898230450209,211079263903460624841507,
1179022517498408548259307,6593381114984955663097869,
36912754633401605027088357,206872001855792377621111719,
1160541512681304496111863447,6516761034998757444607546137,
36626471726431599611696929449,206030721360035302454144967147,
1159912468318756966857440738979,6535196976312757458815954316741,
36848290359517384607151953278125,207915629812563503607757047978543,
1173964326073477816650882885177039,6632973754276801154684587715682513,
37500380783381913572612470593205809,212141771616845919130216540310379699,
1200796887336896148680723089518807003,
6800738671816200263883634106524384509,
38536889636442988510011627147957814133,
218485512042977398145305151653730733495,
1239326915845038050044360149141574744711,
7033292023264506862542551780260402287369,
39933155439917081614646297332853271801017,
226831767346925097843230333561691461750139,
1289029341311590594848983468869684443027347,
7328315284296986666986553099014741661954997,
41679447049393908306774657262565158728242749,
237143127685214808971121513395962842396893247,
1349784790811601952460270522351087362756439999,
7685617405888261934325439002849455215101480897,
43777234761479188569377997745373040369554808897,
249441399213201079760727239070884175096545449539,
1421788206273104170110597037291669679992655467467,
8106682481051245183051939164122432823777586444269,
46236952712739482726241957070796828885901144461061,
263796547500012389075991045568478200188787343127495,
1505494303546197448208798850521962465093470377432183,
8594401341045449836250073064166142787834022984924409,
49076682267607981891161581953043415914677886508708553,
280320266446131301677230031742295788501985310605678859,
1601586332840596173311408272450448001297578264810562179,
9152920896880212340077310715209390340761766765900836773,
52321432265448368603809358946760597004004263790867845069,
299162582471779686872474383492250176467899853019558029903,
1710960325747108851680526424824365839338406280753937600175,
9787572764797186502167383984306506069134859350421021098161,
56002826581256335137366888742181921098590280122851123414609,
320510558759645457373482143086535408815419978699283345323987,
1834720209915984979211273129044265378031512818645170415937979,
10504858345289618200943791787271541774952040986916342871392477,
60159086088823368309348450772511600622372897865337635945036437,
344588540948989195561108928001926915059555461632382005041456599,
1974181027670175070340010401333370259806904412143779108649862247,
11312476685452009450676967335863524401162955580619091905703510249,
64835237450752353190998763893639202715714763660580322438622510297,
371659610579497108042931462476134744077324043897111572108114056347,
2130878613169021415579487979760948662959655889894999293018136186739,
12219387028791806639024463110386114935461203436576500756744370983317,
70083509012564592934477059788362207030336587460845882812005058539869,
402028052098946215004751367738059742841646261572310549346466902214751,
2306584783353479132966538114032939468097834663308764733103440240745375,
13235901484167449474014223822407182467968500139052835055976323393184673,
75963891886881354365534841554496218362086400892829171915974126752888929,
436042729407530476306389058812416143685813823322787812176476132370649443,
2503327555668230201236190541273518077371935886971631673204479039360235947,
14373805576752430133267125003729440694156791780558721814948310153720170445]

It takes a few milliseconds to compute this.