A329863 Number of compositions of n with cuts-resistance 2.

0, 0, 1, 0, 3, 6, 9, 22, 47, 88, 179, 354, 691, 1344, 2617, 5042, 9709, 18632, 35639, 68010, 129556, 246202, 467188, 885036, 1674211, 3163094, 5969022, 11251676, 21189382, 39867970, 74950464, 140798302, 264313039, 495861874, 929709687, 1742193854, 3263069271, 6108762316

Offset

0,5

Comments

A composition of n is a finite sequence of positive integers summing to n.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

Links

Table of n, a(n) for n=0..37.

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Formula

G.f.: -1 + (1 + Ca(x) * Sum_{m>0} x^(2*m) * (Ca(x)-1)/(1 + x^m * (2 + x^m * (1+Ca(x)))))/(1 - Ca(x) * Sum_{m>0} x^(2*m)/(1 + x^m * (2 + x^m * (1+Ca(x)))) where Ca(x) is the g.f. for A003242. - John Tyler Rascoe, Feb 20 2025

Example

The a(2) = 1 through a(7) = 22 compositions (empty column not shown):
  (1,1)  (2,2)    (1,1,3)    (3,3)      (1,1,5)
         (1,1,2)  (1,2,2)    (1,1,4)    (1,3,3)
         (2,1,1)  (2,2,1)    (4,1,1)    (2,2,3)
                  (3,1,1)    (1,1,2,2)  (3,2,2)
                  (1,1,2,1)  (1,1,3,1)  (3,3,1)
                  (1,2,1,1)  (1,2,2,1)  (5,1,1)
                             (1,3,1,1)  (1,1,2,3)
                             (2,1,1,2)  (1,1,3,2)
                             (2,2,1,1)  (1,1,4,1)
                                        (1,4,1,1)
                                        (2,1,1,3)
                                        (2,1,2,2)
                                        (2,2,1,2)
                                        (2,3,1,1)
                                        (3,1,1,2)
                                        (3,2,1,1)
                                        (1,1,2,1,2)
                                        (1,1,2,2,1)
                                        (1,2,1,1,2)
                                        (1,2,2,1,1)
                                        (2,1,1,2,1)
                                        (2,1,2,1,1)

Mathematica

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&, q, Length[#]>0&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], degdep[#]==2&]], {n, 0, 10}]

Prog

(PARI)
Ca(N) = {1/(1-sum(k=1, N, x^k/(1+x^k)))}
A_x(N) = {my(x='x+O('x^N)); concat([0, 0], Vec(-1+(1+sum(m=1, N, Ca(N)*x^(2*m)*(Ca(N)-1)/(1+x^m*(2+x^m*(1+Ca(N))))))/(1-sum(m=1, N, Ca(N)*x^(2*m)/(1+x^m*(2+x^m*(1+Ca(N))))))))}
A_x(38) \\ John Tyler Rascoe, Feb 20 2025

Crossrefs

Column k = 2 of A329861.

Compositions with cuts-resistance 1 are A003242.

Compositions with runs-resistance 2 are A329745.

Numbers whose binary expansion has cuts-resistance 2 are A329862.

Binary words with cuts-resistance 2 are conjectured to be A027383.

Cuts-resistance of binary expansion is A319416.

Binary words counted by cuts-resistance are A319421 and A329860.

Cf. A000975, A003242, A032020, A114901, A240085, A261983, A319420, A329738, A329744, A329864.

Sequence in context: A215666 A050889 A327140 * A026095 A061929 A358403

Adjacent sequences: A329860 A329861 A329862 * A329864 A329865 A329866

Keyword

nonn,changed

Author

Gus Wiseman, Nov 23 2019

Extensions

a(21) onwards from John Tyler Rascoe, Feb 20 2025

Status

approved