A319421 -id:A319421 - cp's OEIS frontend

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

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

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

A329860 Triangle read by rows where T(n,k) is the number of binary words of length n with cuts-resistance k.

Original entry on oeis.org

1, 0, 2, 0, 2, 2, 0, 2, 4, 2, 0, 2, 8, 4, 2, 0, 2, 12, 12, 4, 2, 0, 2, 20, 22, 14, 4, 2, 0, 2, 28, 48, 28, 16, 4, 2, 0, 2, 44, 84, 70, 32, 18, 4, 2, 0, 2, 60, 162, 136, 90, 36, 20, 4, 2, 0, 2, 92, 276, 298, 178, 110, 40, 22, 4, 2, 0, 2, 124, 500, 564, 432, 220, 132, 44, 24, 4, 2

Offset: 0

Gus Wiseman, Nov 23 2019

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.

			Triangle begins:
   1
   0   2
   0   2   2
   0   2   4   2
   0   2   8   4   2
   0   2  12  12   4   2
   0   2  20  22  14   4   2
   0   2  28  48  28  16   4   2
   0   2  44  84  70  32  18   4   2
   0   2  60 162 136  90  36  20   4   2
   0   2  92 276 298 178 110  40  22   4   2
   0   2 124 500 564 432 220 132  44  24   4   2
Row n = 4 counts the following words:
  0101  0010  0001  0000
  1010  0011  0111  1111
        0100  1000
        0110  1110
        1001
        1011
        1100
        1101

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

Column k = 2 appears to be 2 * A027383.
The version for runs-resistance is A319411 or A329767.
The cuts-resistance of the binary expansion of n is A319416(n).
The version for compositions is A329861.
Cf. A000975, A164707, A261983, A318928, A319420, A319421, A329738, A329865.

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

For positive indices, T(n,k) = 2 * A319421(n,k).

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}]

A189391 The minimum possible value for the apex of a triangle of numbers whose base consists of a permutation of the numbers 0 to n, and each number in a higher row is the sum of the two numbers directly below it.

Original entry on oeis.org

0, 1, 3, 8, 19, 44, 98, 216, 467, 1004, 2134, 4520, 9502, 19928, 41572, 86576, 179587, 372044, 768398, 1585416, 3263210, 6711176, 13775068, 28255568, 57863214, 118430584, 242061468, 494523536, 1009105372, 2058327344, 4194213448

Offset: 0

Nathaniel Johnston, Apr 20 2011

This is the Riordan transform of A000217 (triangular numbers) with the Riordan matrix (of the Bell type) A053121 (inverse of the Chebyshev S Bell matrix). See the resulting formulae below. - Wolfdieter Lang, Feb 18 2017.

Conjecture: a(n) is also half the sum of the "cuts-resistance" (see A319416, A319420, A319421) of all binary vectors of length n (see Lenormand, page 4). - N. J. A. Sloane, Sep 20 2018

			For n = 4 consider the triangle:
....19
...8  11
..5  3  8
.4  1 2  6
3  1 0 2  4
This triangle has 19 at its apex and no other such triangle with the numbers 0 - 4 on its base has a smaller apex value, so a(4) = 19.

Nathaniel Johnston, Table of n, a(n) for n = 0..1000
F. Disanto and S. Rinaldi, Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60. - From _N. J. A. Sloane_, May 04 2012
Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.
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_, Sep 20 2018

Cf. A066411, A099325, A189390, A189162, A000217, A053121, A281862.

Cf. also A319416, A319420, A319421.

m:=30; R:=PowerSeriesRing(Rationals(), m); [0] cat Coefficients(R!((2*x+Sqrt(1-4*x^2)-1)/(2*(2*x-1)^2))); // G. C. Greubel, Aug 24 2018

a:=proc(n)return add((2*n-4*k-1)*binomial(n,k),k=0..floor((n-1)/2)): end:
seq(a(n),n=0..50);

CoefficientList[Series[(2*x+Sqrt[1-4*x^2]-1) / (2*(2*x-1)^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 16 2014 *)

A189391(n)=sum(i=0,(n-1)\2,(2*n-4*i-1)*binomial(n,i))  \\ M. F. Hasler, Jan 24 2012

If n even, a(n) = (n+1/2)*binomial(n,n/2) - 2^(n-1); if n odd, a(n) = ((n+1)/2)*binomial(n+1,(n+1)/2) - 2^(n-1). - N. J. A. Sloane, Nov 01 2018
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-4*k-1)*binomial(n,k).
G.f.: (2*x+sqrt(1-4*x^2)-1) / (2*(2*x-1)^2). - Alois P. Heinz, Feb 09 2012
a(n) ~ 2^n * (sqrt(2n/Pi)- 1/2). - Vaclav Kotesovec, Mar 16 2014 (formula simplified by Lewis Chen, May 25 2017)
D-finite with recurrence n*a(n) + (n-5)*a(n-1) + 2*(-5*n+6)*a(n-2) + 4*(-n+8)*a(n-3) + 24*(n-3)*a(n-4) = 0. - R. J. Mathar, Jan 04 2017
From Wolfdieter Lang, Feb 18 2017:(Start)
a(n) = Sum_{m=0..n} A053121(n, m)*A000217(m), n >= 0.
G.f.: c(x^2)*Tri(x*c(x^2)), with c and Tri the g.f. of A000108 and A000217, respectively. See the explicit form of the g.f. given above by Alois P. Heinz.
(End)
2*a(n) = A152548(n)-2^n. - R. J. Mathar, Jun 17 2021

A329865 Numbers whose binary expansion has the same runs-resistance as cuts-resistance.

Original entry on oeis.org

0, 8, 12, 14, 17, 24, 27, 28, 35, 36, 39, 47, 49, 51, 54, 57, 61, 70, 73, 78, 80, 99, 122, 130, 156, 175, 184, 189, 190, 198, 204, 207, 208, 215, 216, 226, 228, 235, 243, 244, 245, 261, 271, 283, 295, 304, 313, 321, 322, 336, 352, 367, 375, 378, 379, 380, 386

Offset: 1

Gus Wiseman, Nov 23 2019

nonn

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.

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:
    0:
    8:      1000
   12:      1100
   14:      1110
   17:     10001
   24:     11000
   27:     11011
   28:     11100
   35:    100011
   36:    100100
   39:    100111
   47:    101111
   49:    110001
   51:    110011
   54:    110110
   57:    111001
   61:    111101
   70:   1000110
   73:   1001001
   78:   1001110
   80:   1010000
For example, 36 has runs-resistance 3 because we have (100100) -> (1212) -> (1111) -> (4), while the cuts-resistance is also 3 because we have (100100) -> (00) -> (0) -> ().
Similarly, 57 has runs-resistance 3 because we have (111001) -> (321) -> (111) -> (3), while the cuts-resistance is also 3 because we have (111001) -> (110) -> (1) -> ().

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

Positions of 0's in A329867.
The version for runs-resistance equal to cuts-resistance minus 1 is A329866.
Compositions with runs-resistance equal to cuts-resistance are A329864.
Runs-resistance of binary expansion is A318928.
Cuts-resistance of binary expansion is A319416.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Binary words counted by runs-resistance are A319411 and A329767.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A107907, A164707, A319420, A329738, A329868.

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

A319420 Irregular triangle read by rows: row n lists the cuts-resistances of the 2^n binary vectors of length n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 2, 1, 2, 2, 1, 2, 3, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 5, 4, 3, 3, 3, 2, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 2, 2, 3, 3, 3, 4, 5

Offset: 0

N. J. A. Sloane, Sep 22 2018

The cuts-resistance of a vector is defined in A319416. The 2^n vectors of length n are taken in lexicographic order.
Note that here the vectors can begin with either 0 or 1, whereas in A319416 only vectors beginning with 1 are considered (since there we are considering binary representations of numbers).
Conjecture: The row sums, halved, appear to match A189391.

			Triangle begins:
0,
1,1,
2,1,1,2,
3,2,1,2,2,1,2,3,
4,3,2,2,2,1,2,3,3,2,1,2,2,2,3,4,
5,4,3,3,3,2,2,3,3,2,1,2,2,2,3,4,4,3,2,2,2,1,2,3,3,2,2,2,3,3,3,4,5,
...

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. See table on page 4.

Keeping the first digit gives A319416.
Positions of 1's are the terms > 1 of A061547 and A086893, all minus 1.
The version for runs-resistance is A329870.
Compositions counted by cuts-resistance are A329861.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A027383, A189391, A318921, A318928, A319411, A329767, A329862, A329865.

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

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&]

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

Original entry on oeis.org

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

Gus Wiseman, Nov 23 2019

nonn

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(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)

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

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.

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

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

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

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

A329864 Number of compositions of n with the same runs-resistance as cuts-resistance.

Original entry on oeis.org

1, 0, 0, 0, 0, 2, 5, 10, 17, 27, 68, 107, 217, 420, 884, 1761, 3679, 7469, 15437, 31396, 64369

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 taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.
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(5) = 2 through a(8) = 17 compositions:
  (1112)  (1113)   (1114)    (1115)
  (2111)  (1122)   (1222)    (1133)
          (2211)   (2221)    (3311)
          (3111)   (4111)    (5111)
          (11211)  (11122)   (11222)
                   (11311)   (11411)
                   (21112)   (12221)
                   (22111)   (21113)
                   (111121)  (22211)
                   (121111)  (31112)
                             (111131)
                             (111221)
                             (112112)
                             (112211)
                             (122111)
                             (131111)
                             (211211)
For example, the runs-resistance of (111221) is 3 because we have: (111221) -> (321) -> (111) -> (3), while the cuts-resistance is also 3 because we have: (111221) -> (112) -> (1) -> (), so (111221) is counted under a(8).

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

The version for binary expansion is A329865.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Compositions with runs-resistance = cuts-resistance minus 1 are A329869.
Cf. A003242, A098504, A114901, A242882, A318928, A319411, A319416, A319420, A319421, A329867, A329868.

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

cp's OEIS Frontend

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

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

A329860 Triangle read by rows where T(n,k) is the number of binary words of length n with cuts-resistance k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A189391 The minimum possible value for the apex of a triangle of numbers whose base consists of a permutation of the numbers 0 to n, and each number in a higher row is the sum of the two numbers directly below it.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A329865 Numbers whose binary expansion has the same runs-resistance as cuts-resistance.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A319420 Irregular triangle read by rows: row n lists the cuts-resistances of the 2^n binary vectors of length n.

Views

Author

Keywords

Comments

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