A329863 -id:A329863 - cp's OEIS frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

1, 1, 1, 3, 4, 7, 14, 23, 39, 71, 124, 214, 378, 661, 1152, 2024, 3542, 6189, 10843, 18978, 33202, 58130, 101742, 178045, 311648, 545470, 954658, 1670919, 2924536, 5118559, 8958772, 15680073, 27443763, 48033284, 84069952, 147142465, 257534928, 450748483, 788918212

Offset: 0

E. Rodney Canfield

			From _Joerg Arndt_, Oct 27 2012:  (Start)
The 23 such compositions of n=7 are
[ 1]  1 2 1 2 1
[ 2]  1 2 1 3
[ 3]  1 2 3 1
[ 4]  1 2 4
[ 5]  1 3 1 2
[ 6]  1 3 2 1
[ 7]  1 4 2
[ 8]  1 5 1
[ 9]  1 6
[10]  2 1 3 1
[11]  2 1 4
[12]  2 3 2
[13]  2 4 1
[14]  2 5
[15]  3 1 2 1
[16]  3 1 3
[17]  3 4
[18]  4 1 2
[19]  4 2 1
[20]  4 3
[21]  5 2
[22]  6 1
[23]  7
(End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 191.

Alois P. Heinz, Table of n, a(n) for n = 0..4100 (first 501 terms from Christian G. Bower)
L. Carlitz, Restricted Compositions, Fibonacci Quarterly, 14 (1976) 254-264.
Sylvie Corteel, Paweł Hitczenko, Generalizations of Carlitz Compositions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.8.8
Steven R. Finch, Errata and Addenda to Mathematical Constants, arXiv:2001.00578 [math.HO], 2020-2022, p. 42 and 117.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 201
F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.
E. Munarini, M. Poneti, S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Chapter 8.

Cf. A106351, A114900, A114902.
Cf. A096568, A011782, A106356. - Franklin T. Adams-Watters, May 27 2010
Row sums of A232396, A241701.
Cf. A241902.
Column k=1 of A261960.
Cf. A048272.
Compositions with adjacent parts coprime are A167606.
The complement is counted by A261983.
Cf. A000740, A005251, A032020, A114901, A178470, A261041, A274174, A329738, A329863.

a003242 n = a003242_list !! n
a003242_list = 1 : f [1] where
   f xs = y : f (y : xs) where
          y = sum $ zipWith (*) xs a048272_list
-- Reinhard Zumkeller, Nov 04 2015

b:= proc(n, i) option remember; `if`(n=0, 1,
      add(`if`(j=i, 0, b(n-j, `if`(j<=n-j, j, 0))), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 27 2014

A048272[n_] := Total[If[OddQ[#], 1, -1]& /@ Divisors[n]]; a[n_] := a[n] = Sum[A048272[k]*a[n-k], {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 38}](* Jean-François Alcover, Nov 25 2011, after Vladeta Jovovic *)
nmax = 50; CoefficientList[Series[1/(1 - Sum[x^k/(1 + x^k), {k, 1, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jul 07 2020 *)
Table[Count[Flatten[Permutations/@IntegerPartitions[n],1],?(FreeQ[Differences[#],0]&)],{n,0,20}] (* The program generates the first 21 terms of the sequence. *) (* _Harvey P. Dale, Nov 23 2024 *)

N = 66;  x = 'x + O('x^N);  p=2;
gf = 1/(1-sum(k=1,N, x^k/(1-x^k)-p*x^(k*p)/(1-x^(k*p))));
Vec(gf)  /* Joerg Arndt, Apr 28 2013 */

a(n) = Sum_{k=1..n} A048272(k)*a(n-k), n>1, a(0)=1. - Vladeta Jovovic, Feb 05 2002
G.f.: 1/(1 - Sum_{k>0} x^k/(1+x^k)).
a(n) ~ c r^n where c is approximately 0.456387 and r is approximately 1.750243. (Formula from Knopfmacher and Prodinger reference.) - Franklin T. Adams-Watters, May 27 2010. With better precision: r = 1.7502412917183090312497386246398158787782058181381590561316586... (see A241902), c = 0.4563634740588133495321001859298593318027266156100046548066205... - Vaclav Kotesovec, Apr 30 2014
G.f. is the special case p=2 of 1/(1 - Sum_{k>0} (z^k/(1-z^k) - p*z^(k*p)/(1-z^(k*p)))), see A129922. - Joerg Arndt, Apr 28 2013
G.f.: 1/(1 - x * (d/dx) log(Product_{k>=1} (1 + x^k)^(1/k))). - Ilya Gutkovskiy, Oct 18 2018
Moebius transform of A329738. - Gus Wiseman, Nov 27 2019
For n>=2, a(n) = A128695(n) - A091616(n). - Vaclav Kotesovec, Jul 07 2020

More terms from David W. Wilson

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, 1534, 2046, 3070, 4094, 6142, 8190, 12286, 16382, 24574, 32766, 49150, 65534, 98302, 131070, 196606, 262142, 393214, 524286, 786430, 1048574, 1572862, 2097150, 3145726, 4194302, 6291454

Offset: 0

R. K. Guy

Number of balanced strings of length n: let d(S) = #(1's) - #(0's), # == count in S, then S is balanced if every substring T of S has -2 <= d(T) <= 2.
Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded. - Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999
Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.) - Jeffrey Shallit, Sep 02 2002
a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
Partial sums of A016116. - Hieronymus Fischer, Sep 15 2007
Equals row sums of triangle A152201. - Gary W. Adamson, Nov 29 2008
From John P. McSorley, Sep 28 2010: (Start)
a(n) = DPE(n+1) is the total number of k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of k-double-palindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.
The 6 double-palindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one double-palindrome.
(End)
From Herbert Eberle, Oct 02 2015: (Start)
For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.
In order a red-black tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.
Consider:
mrbt5                R
                    / \
                   /   \
                  /     \
                 /       B
                /       / \
mrbt4          B       /   B
              / \     B   E E
             /   B   E E
mrbt3       R   E E
           / \
          /   B
mrbt2    B   E E
        / E
mrbt1  R
      E E
(Red nodes shown as R, blacks as B, externals as E.)
Red-black trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.
Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.
(End)
Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121. - Herbert Kociemba, Apr 29 2017
a(n-2) is the number of achiral n-bead necklaces or bracelets using exactly two colors.  For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB. - Robert A. Russell, Sep 26 2018
Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - Yuchun Ji, Nov 16 2018
Also the number of binary words of length n with cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019
Also the number of up-down paths with n steps such that the height difference between the highest and lowest points is at most 2. - Jeremy Dover, Jun 17 2020
Also the number of non-singleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i. - Gus Wiseman, Feb 19 2022

			After 3 folds one sees 4 fold lines.
Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
Binary: 1, 10, 100, 110, 1010, 1110, 10110, 11110, 101110, 111110, 1011110, 1111110, 10111110, 11111110, 101111110, 111111110, 1011111110, 1111111110, 10111111110, ... - _Jason Kimberley_, Nov 02 2011
Example: Partial sums of powers of 2 repeated 2 times:
a(3) = 1+1+2 = 4;
a(4) = 1+1+2+2 = 6;
a(5) = 1+1+2+2+4 = 10.
_Yuchun Ji_, Nov 16 2018

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [John P. McSorley, Sep 28 2010]

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, Under misprinted head B3, Amer Math. Monthly, 104(1997) 753-754.
Laurent Noé, Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group, in Rapide Bilan 2012-2013, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013.
Eric Weisstein's World of Mathematics, Cage Graph
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A132666, A152201.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), this sequence (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A000066 (actual order of a (3,g)-cage).
Bisections are A033484 (even) and A000918 (odd).
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A062011, A329862, A329863.
The complementary compositions are counted by A274230(n-1) + 1, with bisections A060867 (even) and A134057 (odd).
Cf. A000346, A000984, A001405, A001700, A011782 (compositions).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
-- Reinhard Zumkeller, Jun 17 2015

[2^Floor((n+2)/2)+2^Floor((n+1)/2)-2: n in [0..50]]; // Vincenzo Librandi, Aug 16 2011

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n], n=1..41); # Zerinvary Lajos, Mar 16 2008

a[n_?EvenQ] := 3*2^(n/2)-2; a[n_?OddQ] := 2^(2+(n-1)/2)-2; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 21 2011, after Quim Castellsaguer *)
LinearRecurrence[{1, 2, -2}, {1, 2, 4}, 41] (* Robert G. Wilson v, Oct 06 2014 *)
Table[Length[Select[Tuples[{0,1},n],And[Max@@Length/@Split[#]<=2,!MatchQ[Length/@Split[#],{_,2,ins:1..,2,_}/;OddQ[Plus[ins]]]]&]],{n,0,15}] (* Gus Wiseman, Nov 28 2019 *)

a(n)=2^(n\2+1)+2^((n+1)\2)-2 \\ Charles R Greathouse IV, Oct 21 2011

def a(n): return 2**((n+2)//2) + 2**((n+1)//2) - 2
print([a(n) for n in range(43)]) # Michael S. Branicky, Feb 19 2022

a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
a(2n) = 3*2^n - 2 = A033484(n);
a(2n-1) = 2^(n+1) - 2 = A000918(n+1).
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = Sum_{k=0..n} 2^min(k, n-k).
a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2) - 2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es)
a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (3-2*sqrt(2))*(-1)^n)/2 - 2. - Paul Barry, Apr 23 2004
a(n) = A132340(A052955(n)). - Reinhard Zumkeller, Aug 20 2007
a(n) = A052955(n+1) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n+1)) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n-1)+1) for n > 0. - Hieronymus Fischer, Sep 15 2007
A132666(a(n)) = a(n-1) + 1 for n > 0. - Hieronymus Fischer, Sep 15 2007
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = 2*( (a(n-2)+1) mod (a(n-1)+1) ), n > 1. - Pierre Charland, Dec 12 2010
a(n) = A136252(n-1) + 1, for n > 0. - Jason Kimberley, Nov 01 2011
G.f.: (1+x*R(0))/(1-x), where R(k) = 1 + 2*x/( 1 - x/(x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013
a(n) = 2^((2*n + 3*(1-(-1)^n))/4)*3^((1+(-1)^n)/2) - 2. - Luce ETIENNE, Sep 01 2014
a(n) = a(n-1) + 2^floor((n-1)/2) for n>0, a(0)=1. - Yuchun Ji, Nov 23 2018
E.g.f.: 3*cosh(sqrt(2)*x) - 2*cosh(x) + 2*sqrt(2)*sinh(sqrt(2)*x) - 2*sinh(x). - Stefano Spezia, Apr 06 2022

More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000

Replaced definition with a simpler one. - N. J. A. Sloane, Jul 09 2022

A114901 Number of compositions of n such that each part is adjacent to an equal part.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 3, 10, 10, 21, 22, 49, 51, 105, 126, 233, 292, 529, 678, 1181, 1585, 2654, 3654, 6016, 8416, 13606, 19395, 30840, 44517, 70087, 102070, 159304, 233941, 362429, 535520, 825358, 1225117, 1880220, 2801749, 4285086, 6404354, 9769782, 14634907

Offset: 0

Christian G. Bower, Jan 05 2006

nonn

			The 5 compositions of 6 are 3+3, 2+2+2, 2+2+1+1, 1+1+2+2, 1+1+1+1+1+1.
From _Gus Wiseman_, Nov 25 2019: (Start)
The a(2) = 1 through a(9) = 10 compositions:
  (11)  (111)  (22)    (11111)  (33)      (11122)    (44)        (333)
               (1111)           (222)     (22111)    (1133)      (11133)
                                (1122)    (1111111)  (2222)      (33111)
                                (2211)               (3311)      (111222)
                                (111111)             (11222)     (222111)
                                                     (22211)     (1111122)
                                                     (111122)    (1112211)
                                                     (112211)    (1122111)
                                                     (221111)    (2211111)
                                                     (11111111)  (111111111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..4000
N. J. A. Sloane, Transforms

The case of partitions is A007690.
Compositions with no adjacent parts equal are A003242.
Compositions with all multiplicities > 1 are A240085.
Compositions with minimum multiplicity 1 are A244164.
Compositions with at least two adjacent parts equal are A261983.
Cf. A178470, A238130, A274174, A329863.

g:= proc(n, i) option remember; add(b(n-i*j, i), j=2..n/i) end:
b:= proc(n, l) option remember; `if`(n=0, 1,
      add(`if`(i=l, 0, g(n,i)), i=1..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 29 2019

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Min@@Length/@Split[#]>1&]],{n,0,10}] (* Gus Wiseman, Nov 25 2019 *)
g[n_, i_] := g[n, i] = Sum[b[n - i*j, i], {j, 2, n/i}] ;
b[n_, l_] := b[n, l] = If[n==0, 1, Sum[If[i==l, 0, g[n, i]], {i, 1, n/2}]];
a[n_] := b[n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, May 23 2021, after Alois P. Heinz *)

A_x(N,k) = { my(x='x+O('x^N), g=1/(1-sum(i=1,N,sum(j=k+1,N, x^(i*j))/(1+ sum(j=k+1,N, x^(i*j)))))); Vec(g)}
A_x(50,1) \\ John Tyler Rascoe, May 17 2024

INVERT(iMOEBIUS(iINVERT(A000012 shifted right 2 places)))

G.f.: A(x,1) is the k = 1 case of A(x,k) = 1/(1 - Sum_{i>0} ( (Sum_{j>k} x^(i*j))/(1 + Sum_{j>k} x^(i*j)) )) where A(x,k) is the g.f. for compositions of n with all run-lengths > k. - John Tyler Rascoe, May 16 2024

A319416 Cuts-resistance of n: number of applications of Lernormand's "raboter" map needed to transform the binary expansion of n to the empty string.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 2, 3, 3, 3, 4, 5, 5, 4, 3, 3, 3, 2, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 2, 3, 4, 3, 3, 3, 4, 4, 4, 5, 6, 6, 5, 4, 4, 4, 3, 3, 3, 4, 3, 2, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 1, 2

Offset: 0

N. J. A. Sloane, Sep 21 2018

Here we are using Lenormand's "raboter" map in a stricter sense than in A318921 and A319419. If S is a binary string with successive runs of lengths b,c,d,e,..., the "raboter" map sends S to the binary string with successive runs of lengths b-1,c-1,d-1,e-1,... Runs of length 0 are omitted (they are indicated by dots in the examples below).
To get a(n), start with S equal to the binary expansion of n beginning with the most significant bit, and keep applying the map until we reach the empty string.
After the first step, the string may start with a string of 0's: this is acceptable because we are working with strings, not binary expansions of numbers.
For example, 34 = 100010 -> .00.. = 00 -> 0. = 0 -> . (the empty string), taking 3 steps, so a(34) = 3.
Note: this is not the same as the number of applications of the map k -> A318921(k) needed to reduce the binary expansion of n to zero (because A318921 does not distinguish between 0 and the empty string).
This is also not the same as the number of applications of the map k -> A319419(k) needed to reduce the binary expansion of n to -1 (because A319419 does not distinguish between a string of 0's and a single 0).
The value k appears for the first time when n = 2^k - 1.

			n: repeatedly applying the map / number of steps = a(n)
0: 0 -> . / 1
1: 1 -> . / 1
2: 10 -> . / 1
3: 11 -> 1 -> . / 2
4: 100 -> 0 -> . / 2
5: 101 -> . / 1
6: 110 -> 1 -> . / 2
7: 111 -> 11 -> 1 -> . / 3
8: 1000 -> 00 -> 0 -> . / 3
9: 1001 -> 0 -> . / 2
10: 1010 -> . / 1
11: 1011 -> 1 -> . / 2
12: 1100 -> 10 -> . / 2
...

Rémy Sigrist, Table of n, a(n) for n = 0..16384
Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.
N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)

Positions of 1's are A000975.
Positions of 2's are A329862.
The version for runs-resistance is A318928.
The version for compositions is A329861.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A318921, A319411, A319419, A319420, A329744, A329767, A329863, A329865.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[degdep[IntegerDigits[n,2]],{n,0,50}] (* Gus Wiseman, Nov 25 2019 *)

a(n) = my (b=binary(n), w=#b); for (k=1, oo, my (ww=0); for (i=2, w, if (b[i-1]==b[i], b[ww++]=b[i])); if (ww==0, return (k), w=ww)) \\ Rémy Sigrist, Sep 23 2018

More terms from Rémy Sigrist, Sep 23 2018

A329861 Triangle read by rows where T(n,k) is the number of compositions of n with cuts-resistance k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 4, 3, 0, 1, 0, 7, 6, 2, 0, 1, 0, 14, 9, 6, 2, 0, 1, 0, 23, 22, 10, 6, 2, 0, 1, 0, 39, 47, 22, 10, 7, 2, 0, 1, 0, 71, 88, 52, 24, 10, 8, 2, 0, 1, 0, 124, 179, 101, 59, 26, 11, 9, 2, 0, 1, 0, 214, 354, 220, 112, 71, 28, 12, 10, 2, 0, 1

Offset: 0

Gus Wiseman, Nov 23 2019

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 as the number of applications required to reach an empty word.

			Triangle begins:
  1
  0  1
  0  1  1
  0  3  0  1
  0  4  3  0  1
  0  7  6  2  0  1
  0 14  9  6  2  0  1
  0 23 22 10  6  2  0  1
  0 39 47 22 10  7  2  0  1
  0 71 88 52 24 10  8  2  0  1
Row n = 6 counts the following compositions (empty columns not shown):
  (6)     (33)    (222)    (11112)  (111111)
  (15)    (114)   (1113)   (21111)
  (24)    (411)   (3111)
  (42)    (1122)  (11121)
  (51)    (1131)  (11211)
  (123)   (1221)  (12111)
  (132)   (1311)
  (141)   (2112)
  (213)   (2211)
  (231)
  (312)
  (321)
  (1212)
  (2121)

Row sums are A000079.
Column k = 1 is A003242 (for n > 0).
Column k = 2 is A329863.
Row sums without the k = 1 column are A261983.
The version for runs-resistance is A329744.
The version for binary vectors is A329860.
The cuts-resistance of the binary expansion of n is A319416.
Cf. A175342, A240085, A319411, A319420, A319421, A329738, A329862, A329865.

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

A329862 Positive integers whose binary expansion has cuts-resistance 2.

Original entry on oeis.org

3, 4, 6, 9, 11, 12, 13, 18, 19, 20, 22, 25, 26, 37, 38, 41, 43, 44, 45, 50, 51, 52, 53, 74, 75, 76, 77, 82, 83, 84, 86, 89, 90, 101, 102, 105, 106, 149, 150, 153, 154, 165, 166, 169, 171, 172, 173, 178, 179, 180, 181, 202, 203, 204, 205, 210, 211, 212, 213

Offset: 1

Gus Wiseman, Nov 23 2019

nonn

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.

			The sequence of terms together with their binary expansions begins:
   3:      11
   4:     100
   6:     110
   9:    1001
  11:    1011
  12:    1100
  13:    1101
  18:   10010
  19:   10011
  20:   10100
  22:   10110
  25:   11001
  26:   11010
  37:  100101
  38:  100110
  41:  101001
  43:  101011
  44:  101100
  45:  101101
  50:  110010

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

Positions of 2's in A319416.
Numbers whose binary expansion has cuts-resistance 1 are A000975.
Binary words with cuts-resistance 2 are conjectured to be A027383.
Compositions with cuts-resistance 2 are A329863.
Cuts-resistance of binary expansion without first digit is A319420.
Binary words counted by cuts-resistance are A319421 and A329860.
Compositions counted by cuts-resistance are A329861.
Cf. A107907, A114901, A164707, A318928, A319411, A329745, A329865, A329866.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Select[Range[100],degdep[IntegerDigits[#,2]]==2&]

A330028 Number of compositions of n with cuts-resistance <= 2.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 23, 45, 86, 159, 303, 568, 1069, 2005, 3769, 7066, 13251, 24821, 46482, 86988, 162758

Offset: 0

Gus Wiseman, Nov 27 2019

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.

			The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)    (3)    (4)      (5)
           (1,1)  (1,2)  (1,3)    (1,4)
                  (2,1)  (2,2)    (2,3)
                         (3,1)    (3,2)
                         (1,1,2)  (4,1)
                         (1,2,1)  (1,1,3)
                         (2,1,1)  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,2,1)
                                  (1,2,1,1)

Sum of first three columns of A329861.
Compositions with cuts-resistance 1 are A003242.
Compositions with cuts-resistance 2 are A329863.
Compositions with runs-resistance 2 are A329745.
Numbers whose binary expansion has cuts-resistance 2 are A329862.
Binary words with cuts-resistance 2 are A027383.
Cuts-resistance of binary expansion is A319416.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A003242, A032020, A114901, A240085, A261983, A319420, A329738, A329744, A329864.

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

A330029 Numbers whose binary expansion has cuts-resistance <= 2.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 18, 19, 20, 21, 22, 25, 26, 37, 38, 41, 42, 43, 44, 45, 50, 51, 52, 53, 74, 75, 76, 77, 82, 83, 84, 85, 86, 89, 90, 101, 102, 105, 106, 149, 150, 153, 154, 165, 166, 169, 170, 171, 172, 173, 178, 179, 180, 181, 202, 203

Offset: 1

Gus Wiseman, Nov 27 2019

nonn

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.
Also numbers whose binary expansion is a balanced word (see A027383 for definition).
Also numbers whose binary expansion has all run-lengths 1 or 2 and whose sequence of run-lengths has no odd-length run of 1's sandwiched between two 2's.

			The sequence of terms together with their binary expansions begins:
    0:
    1:        1
    2:       10
    3:       11
    4:      100
    5:      101
    6:      110
    9:     1001
   10:     1010
   11:     1011
   12:     1100
   13:     1101
   18:    10010
   19:    10011
   20:    10100
   21:    10101
   22:    10110
   25:    11001
   26:    11010
   37:   100101
   38:   100110

Union of A000975 and A329862.
Balanced binary words are counted by A027383.
Compositions with cuts-resistance <= 2 are A330028.
Cuts-resistance of binary expansion is A319416.
Cf. A027383, A098504, A107907, A164707, A329860, A329861, A329863, A329865.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Select[Range[0,100],degdep[IntegerDigits[#,2]]<=2&]

cp's OEIS Frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A027383 a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A114901 Number of compositions of n such that each part is adjacent to an equal part.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A319416 Cuts-resistance of n: number of applications of Lernormand's "raboter" map needed to transform the binary expansion of n to the empty string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A329861 Triangle read by rows where T(n,k) is the number of compositions of n with cuts-resistance k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329862 Positive integers whose binary expansion has cuts-resistance 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A330028 Number of compositions of n with cuts-resistance <= 2.

Views

Author

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.