A333217 -id:A333217 - cp's OEIS frontend

A052709 Expansion of g.f. (1-sqrt(1-4x-4x^2))/(2*(1+x)).

0, 1, 1, 3, 9, 31, 113, 431, 1697, 6847, 28161, 117631, 497665, 2128127, 9183489, 39940863, 174897665, 770452479, 3411959809, 15181264895, 67833868289, 304256253951, 1369404661761, 6182858317823, 27995941060609, 127100310290431, 578433619525633, 2638370120138751

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

A simple context-free grammar.
Number of lattice paths from (0,0) to (2n-2,0) that stay (weakly) in the first quadrant and such that each step is either U=(1,1), D=(1,-1), or L=(3,1). Equivalently, underdiagonal lattice paths from (0,0) to (n-1,n-1) and such that each step is either (1,0), (0,1), or (2,1). E.g., a(4)=9 because in addition to the five Dyck paths from (0,0) to (6,0) [UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD] we have LDUD, LUDD, ULDD and UDLD. - Emeric Deutsch, Dec 21 2003
Hankel transform of a(n+1) is A006125(n+1). - Paul Barry, Apr 01 2007
Also, a(n+1) is the number of walks from (0,0) to (n,0) using steps (1,1), (1,-1) and (0,-1). See the U(n,k) array in A071943, where A052709(n+1) = U(n,0). - N. J. A. Sloane, Mar 29 2013
Diagonal sums of triangle in A085880. - Philippe Deléham, Nov 15 2013
From Gus Wiseman, Jun 17 2021: (Start)
Conjecture: For n > 0, also the number of sequences of length n - 1 covering an initial interval of positive integers and avoiding three terms (..., x, ..., y, ..., z, ...) such that x <= y <= z. The version avoiding the strict pattern (1,2,3) is A226316. Sequences covering an initial interval are counted by A000670. The a(1) = 1 through a(4) = 9 sequences are:
  ()  (1)  (1,1)  (1,2,1)
           (1,2)  (1,3,2)
           (2,1)  (2,1,1)
                  (2,1,2)
                  (2,1,3)
                  (2,2,1)
                  (2,3,1)
                  (3,1,2)
                  (3,2,1)
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..499
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Ascending runs in permutations and valued Dyck paths, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 445-463.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.
Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, and Michael D. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, arXiv:1602.03550 [math.CO], 2016.
Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
James East and Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.
L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math., 271 (2003), 29-50.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 664
J. P. S. Kung and A. de Mier, Catalan lattice paths with rook, bishop and spider steps, Journal of Combinatorial Theory, Series A 120 (2013) 379-389. - _N. J. A. Sloane_, Dec 27 2012
D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.

Diagonal entries of A071943 and A071945.
Cf. A000108, A000670, A025227, A052709, A056986, A071943, A085880.
Cf. A102726, A117434, A158005, A226316, A333217, A335479.

[0] cat [(&+[Binomial(n,k+1)*Binomial(2*k,n-1): k in [0..n-1]])/n: n in [1..30]]; // G. C. Greubel, May 30 2022

spec := [S,{C=Prod(B,Z),S=Union(B,C,Z),B=Prod(S,S)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

InverseSeries[Series[(y-y^2)/(1+y^2), {y, 0, 24}], x] (* then A(x)= y(x) *) (* Len Smiley, Apr 12 2000 *)
CoefficientList[Series[(1 -Sqrt[1 -4x -4x^2])/(2(1+x)), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 12 2016 *)

a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x),n)

[sum(binomial(k, n-k-1)*catalan_number(k) for k in (0..n-1)) for n in (0..30)] # G. C. Greubel, May 30 2022

a(n) + a(n-1) = A025227(n).
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-2-2*k)!/(k!*(n-k)!*(n-1-2*k)!). - Emeric Deutsch, Nov 14 2001
D-finite with recurrence: n*a(n) = (3*n-6)*a(n-1) + (8*n-18)*a(n-2) + (4*n-12)*a(n-3), n>2. a(1)=a(2)=1.
a(n) = b(1)*a(n-1) + b(2)*a(n-2) + ... + b(n-1)*a(1) for n>1 where b(n)=A025227(n).
G.f.: A(x) = x/(1-(1+x)*A(x)). - Paul D. Hanna, Aug 16 2002
G.f.: A(x) = x/(1-z/(1-z/(1-z/(...)))) where z=x+x^2 (continued fraction). - Paul D. Hanna, Aug 16 2002; revised by Joerg Arndt, Mar 18 2011
a(n+1) = Sum_{k=0..n} Catalan(k)*binomial(k, n-k). - Paul Barry, Feb 22 2005
From Paul Barry, Mar 14 2006: (Start)
G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108.
Row sums of A117434. (End)
a(n+1) = (1/(2*Pi))*Integral_{x=2-2*sqrt(2)..2+2*sqrt(2)} x^n*(4+4x-x^2)/(2*(1+x)). - Paul Barry, Apr 01 2007
From Gary W. Adamson, Jul 22 2011: (Start)
For n>0, a(n) is the upper left term in M^(n-1), where M is an infinite square production matrix as follows:
  1, 1, 0, 0, 0, 0, ...
  2, 1, 1, 0, 0, 0, ...
  2, 2, 1, 1, 0, 0, ...
  2, 2, 2, 1, 1, 0, ...
  2, 2, 2, 2, 1, 1, ...
  ... (End)
G.f.: x*Q(0), where Q(k) = 1 + (4*k+1)*x*(1+x)/(k+1 - x*(1+x)*(2*k+2)*(4*k+3)/(2*x*(1+x)*(4*k+3) + (2*k+3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
a(n) ~ sqrt(2-sqrt(2))*2^(n-1/2)*(1+sqrt(2))^(n-1)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Jun 29 2013
a(n+1) = Sum_{k=0..floor(n/2)} A085880(n-k,k). - Philippe Deléham, Nov 15 2013

Better g.f. and recurrence from Michael Somos, Aug 03 2000

More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000

A333256 Numbers k such that the k-th composition in standard order is strictly decreasing.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 16, 17, 18, 32, 33, 34, 37, 64, 65, 66, 68, 69, 128, 129, 130, 132, 133, 137, 256, 257, 258, 260, 261, 264, 265, 274, 512, 513, 514, 516, 517, 520, 521, 529, 530, 549, 1024, 1025, 1026, 1028, 1029, 1032, 1033, 1040, 1041, 1042, 1058, 1061

Offset: 1

Gus Wiseman, Mar 20 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The sequence of positive terms together with the corresponding compositions begins:
     1: (1)         128: (8)         517: (7,2,1)
     2: (2)         129: (7,1)       520: (6,4)
     4: (3)         130: (6,2)       521: (6,3,1)
     5: (2,1)       132: (5,3)       529: (5,4,1)
     8: (4)         133: (5,2,1)     530: (5,3,2)
     9: (3,1)       137: (4,3,1)     549: (4,3,2,1)
    16: (5)         256: (9)        1024: (11)
    17: (4,1)       257: (8,1)      1025: (10,1)
    18: (3,2)       258: (7,2)      1026: (9,2)
    32: (6)         260: (6,3)      1028: (8,3)
    33: (5,1)       261: (6,2,1)    1029: (8,2,1)
    34: (4,2)       264: (5,4)      1032: (7,4)
    37: (3,2,1)     265: (5,3,1)    1033: (7,3,1)
    64: (7)         274: (4,3,2)    1040: (6,5)
    65: (6,1)       512: (10)       1041: (6,4,1)
    66: (5,2)       513: (9,1)      1042: (6,3,2)
    68: (4,3)       514: (8,2)      1058: (5,4,2)
    69: (4,2,1)     516: (7,3)      1061: (5,3,2,1)

Strictly increasing runs are counted by A124768.
The normal case is A246534.
The weakly decreasing version is A114994.
The weakly increasing version is A225620.
The unequal version is A233564.
The equal version is A272919.
The strictly increasing version is A333255.
Cf. A000120, A029931, A048793, A066099, A070939, A124769, A228351, A233249, A333217, A333256, A333380.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,1000],Greater@@stc[#]&]

A333255 Numbers k such that the k-th composition in standard order is strictly increasing.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 16, 20, 24, 32, 40, 48, 52, 64, 72, 80, 96, 104, 128, 144, 160, 192, 200, 208, 256, 272, 288, 320, 328, 384, 400, 416, 512, 544, 576, 640, 656, 768, 784, 800, 832, 840, 1024, 1056, 1088, 1152, 1280, 1296, 1312, 1536, 1568, 1600, 1664, 1680

Offset: 1

Gus Wiseman, Mar 20 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The sequence of positive terms together with the corresponding compositions begins:
     1: (1)         128: (8)         656: (2,3,5)
     2: (2)         144: (3,5)       768: (1,9)
     4: (3)         160: (2,6)       784: (1,4,5)
     6: (1,2)       192: (1,7)       800: (1,3,6)
     8: (4)         200: (1,3,4)     832: (1,2,7)
    12: (1,3)       208: (1,2,5)     840: (1,2,3,4)
    16: (5)         256: (9)        1024: (11)
    20: (2,3)       272: (4,5)      1056: (5,6)
    24: (1,4)       288: (3,6)      1088: (4,7)
    32: (6)         320: (2,7)      1152: (3,8)
    40: (2,4)       328: (2,3,4)    1280: (2,9)
    48: (1,5)       384: (1,8)      1296: (2,4,5)
    52: (1,2,3)     400: (1,3,5)    1312: (2,3,6)
    64: (7)         416: (1,2,6)    1536: (1,10)
    72: (3,4)       512: (10)       1568: (1,4,6)
    80: (2,5)       544: (4,6)      1600: (1,3,7)
    96: (1,6)       576: (3,7)      1664: (1,2,8)
   104: (1,2,4)     640: (2,8)      1680: (1,2,3,5)

Strictly increasing runs are counted by A124768.
The normal case is A164894.
The weakly decreasing version is A114994.
The weakly increasing version is A225620.
The unequal version is A233564.
The equal version is A272919.
The strictly decreasing version is A333256.
Cf. A000120, A029931, A048793, A066099, A070939, A124762, A228351, A333217, A333220, A333379.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,1000],Less@@stc[#]&]

A333227 Numbers k such that the k-th composition in standard order is pairwise coprime, where a singleton is not coprime unless it is (1).

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 17, 18, 19, 20, 23, 24, 25, 27, 28, 29, 30, 31, 33, 35, 37, 38, 39, 41, 44, 47, 48, 49, 50, 51, 52, 55, 56, 57, 59, 60, 61, 62, 63, 65, 66, 67, 68, 71, 72, 75, 77, 78, 79, 80, 83, 89, 92, 95, 96, 97, 99, 101, 102, 103, 105

Offset: 1

Gus Wiseman, Mar 27 2020

nonn

This is the definition used for CoprimeQ in Mathematica.

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The sequence together with the corresponding compositions begins:
   1: (1)          27: (1,2,1,1)      55: (1,2,1,1,1)
   3: (1,1)        28: (1,1,3)        56: (1,1,4)
   5: (2,1)        29: (1,1,2,1)      57: (1,1,3,1)
   6: (1,2)        30: (1,1,1,2)      59: (1,1,2,1,1)
   7: (1,1,1)      31: (1,1,1,1,1)    60: (1,1,1,3)
   9: (3,1)        33: (5,1)          61: (1,1,1,2,1)
  11: (2,1,1)      35: (4,1,1)        62: (1,1,1,1,2)
  12: (1,3)        37: (3,2,1)        63: (1,1,1,1,1,1)
  13: (1,2,1)      38: (3,1,2)        65: (6,1)
  14: (1,1,2)      39: (3,1,1,1)      66: (5,2)
  15: (1,1,1,1)    41: (2,3,1)        67: (5,1,1)
  17: (4,1)        44: (2,1,3)        68: (4,3)
  18: (3,2)        47: (2,1,1,1,1)    71: (4,1,1,1)
  19: (3,1,1)      48: (1,5)          72: (3,4)
  20: (2,3)        49: (1,4,1)        75: (3,2,1,1)
  23: (2,1,1,1)    50: (1,3,2)        77: (3,1,2,1)
  24: (1,4)        51: (1,3,1,1)      78: (3,1,1,2)
  25: (1,3,1)      52: (1,2,3)        79: (3,1,1,1,1)

A different ranking of the same compositions is A326675.
Ignoring repeated parts gives A333228.
Let q(k) be the k-th composition in standard order:
- The terms of q(k) are row k of A066099.
- The sum of q(k) is A070939(k).
- The product of q(k) is A124758(k).
- q(k) has A124767(k) runs and A333381(k) anti-runs.
- The GCD of q(k) is A326674(k).
- The Heinz number of q(k) is A333219(k).
- The LCM of q(k) is A333226(k).
Coprime or singleton sets are ranked by A087087.
Strict compositions are ranked by A233564.
Constant compositions are ranked by A272919.
Relatively prime compositions appear to be ranked by A291166.
Normal compositions are ranked by A333217.
Cf. A000120, A029931, A048793, A096111, A114994, A225620, A228351.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,120],CoprimeQ@@stc[#]&]

A333224 Number of distinct positive consecutive subsequence-sums of the k-th composition in standard order.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 3, 3, 1, 3, 2, 4, 3, 4, 4, 4, 1, 3, 3, 5, 3, 5, 4, 5, 3, 4, 5, 5, 5, 5, 5, 5, 1, 3, 3, 5, 2, 5, 5, 6, 3, 6, 3, 6, 5, 6, 5, 6, 3, 4, 6, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 1, 3, 3, 5, 3, 6, 6, 7, 3, 5, 5, 7, 4, 6, 6, 7, 3, 6, 4, 7, 5, 7, 6

Offset: 0

Gus Wiseman, Mar 18 2020

nonn

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The composition (4,3,1,2) has positive subsequence-sums 1, 2, 3, 4, 6, 7, 8, 10, so a(550) = 8.

Dominated by A124770.
Compositions where every subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222. The case of partitions is counted by A325768 and ranked by A325779.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and A325592 and ranked by A299702.
Strict knapsack partitions are counted by A275972 and ranked by A059519 and A301899.
Knapsack compositions are counted by A325676 and A325687 and ranked by A333223. The case of partitions is counted by A325769 and ranked by A325778, for which the number of distinct consecutive subsequences is given by A325770.
Allowing empty subsequences gives A333257.
Cf. A000120, A003022, A029931, A048793, A066099, A070939, A103295, A124767, A143823, A295235, A325680, A333217.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[ReplaceList[stc[n],{_,s__,_}:>Plus[s]]]],{n,0,100}]

a(n) = A333257(n) - 1.

A333257 Number of distinct consecutive subsequence-sums of the k-th composition in standard order.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 4, 4, 2, 4, 3, 5, 4, 5, 5, 5, 2, 4, 4, 6, 4, 6, 5, 6, 4, 5, 6, 6, 6, 6, 6, 6, 2, 4, 4, 6, 3, 6, 6, 7, 4, 7, 4, 7, 6, 7, 6, 7, 4, 5, 7, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 2, 4, 4, 6, 4, 7, 7, 8, 4, 6, 6, 8, 5, 7, 7, 8, 4, 7, 5, 8, 6, 8, 7

Offset: 0

Gus Wiseman, Mar 20 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The ninth composition in standard order is (3,1), which has consecutive subsequences (), (1), (3), (3,1), with sums 0, 1, 3, 4, so a(9) = 4.

Dominated by A124771.
Compositions where every subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222, while the case of partitions is counted by A325768 and ranked by A325779.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and ranked by A299702.
Knapsack compositions are counted by A325676 and A325687 and ranked by A333223.
The version for Heinz numbers of partitions is A325770.
Not allowing empty subsequences gives A333224.
Cf. A000120, A029931, A048793, A059519, A066099, A070939, A114994, A124765, A124767, A233564, A272919, A325778, A333217.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[ReplaceList[stc[n],{_,s___,_}:>Plus[s]]]],{n,0,100}]

a(n) = A333224(n) + 1.

A333766 Maximum part of the n-th composition in standard order. a(0) = 0.

Original entry on oeis.org

0, 1, 2, 1, 3, 2, 2, 1, 4, 3, 2, 2, 3, 2, 2, 1, 5, 4, 3, 3, 3, 2, 2, 2, 4, 3, 2, 2, 3, 2, 2, 1, 6, 5, 4, 4, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 2, 2, 5, 4, 3, 3, 3, 2, 2, 2, 4, 3, 2, 2, 3, 2, 2, 1, 7, 6, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 5, 4, 3, 3, 3, 2, 2

Offset: 0

Gus Wiseman, Apr 05 2020

nonn

One plus the longest run of 0's in the binary expansion of n.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The 100th composition in standard order is (1,3,3), so a(100) = 3.

Positions of ones are A000225.
Positions of terms <= 2 are A003754.
The version for prime indices is A061395.
Positions of terms > 1 are A062289.
Positions of first appearances are A131577.
The minimum part is given by A333768.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Compositions without 1's are A022340.
- Sum is A070939.
- Product is A124758.
- Runs are counted by A124767.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Runs-resistance is A333628.
- Weakly decreasing compositions are A114994.
- Weakly increasing compositions are A225620.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
Cf. A029931, A048793, A087117, A228351, A328594, A333217, A333218, A333219, A333632, A333767.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[If[n==0,0,Max@@stc[n]],{n,0,100}]

For n > 0, a(n) = A087117(n) + 1.

A335458 Number of normal patterns contiguously matched by the n-th composition in standard order (A066099).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 5, 3, 5, 5, 5, 2, 3, 3, 5, 3, 5, 5, 7, 3, 5, 5, 8, 5, 8, 7, 6, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 4, 7, 5, 7, 8, 9, 3, 5, 5, 8, 4, 8, 7, 11, 5, 8, 7, 11, 7, 11, 9, 7, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 5, 7, 5, 7, 8, 9, 3, 5, 5, 8, 5, 7

Offset: 0

Gus Wiseman, Jun 21 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(180) = 7 patterns are: (), (1), (1,2), (2,1), (1,2,3), (2,1,2), (2,1,2,3).

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The non-contiguous version is A335454.
Summing over indices with binary length n gives A335457(n).
The nonempty version is A335474.
Patterns are counted by A000670 and ranked by A333217.
The n-th composition has A124771(n) distinct consecutive subsequences.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A333257(n) distinct subsequence-sums.
The n-th composition has A334299(n) distinct subsequences.
Minimal avoided patterns are counted by A335465.
Cf. A108917, A124767, A124770, A181796, A269134, A333218, A333222, A333628, A334030, A335456.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Union[mstype/@ReplaceList[stc[n],{_,s___,_}:>{s}]]],{n,0,30}]

a(n) = A335474(n) + 1.

A344605 Number of alternating patterns of length n, including pairs (x,x).

Original entry on oeis.org

1, 1, 3, 6, 22, 102, 562, 3618, 26586, 219798, 2018686, 20393790, 224750298, 2683250082, 34498833434, 475237879950, 6983085189454, 109021986683046, 1802213242949602, 31447143854808378, 577609702827987882, 11139837273501641502, 225075546284489412854

Offset: 0

Gus Wiseman, May 27 2021

nonn

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. A sequence is alternating (cf. A025047) including pairs (x,x) if there are no adjacent triples (..., x, y, z, ...) where x <= y <= z or x >= y >= z. These sequences avoid the weak consecutive patterns (1,2,3) and (3,2,1).
An alternating pattern of length > 2 is necessarily an anti-run (A005649).
The version without pairs (x,x) is identical to this sequence except a(2) = 2 instead of 3.

			The a(0) = 1 through a(4) = 22 patterns:
  ()  (1)  (1,1)  (1,2,1)  (1,2,1,2)
           (1,2)  (1,3,2)  (1,2,1,3)
           (2,1)  (2,1,2)  (1,3,1,2)
                  (2,1,3)  (1,3,2,3)
                  (2,3,1)  (1,3,2,4)
                  (3,1,2)  (1,4,2,3)
                           (2,1,2,1)
                           (2,1,3,1)
                           (2,1,3,2)
                           (2,1,4,3)
                           (2,3,1,2)
                           (2,3,1,3)
                           (2,3,1,4)
                           (2,4,1,3)
                           (3,1,2,1)
                           (3,1,3,2)
                           (3,1,4,2)
                           (3,2,3,1)
                           (3,2,4,1)
                           (3,4,1,2)
                           (4,1,3,2)
                           (4,2,3,1)

Martin Ehrenstein, Table of n, a(n) for n = 0..25

The version for permutations is A001250.
The version for compositions is A344604.
The version for permutations of prime indices is A344606.
A000670 counts patterns (ranked by A333217).
A003242 counts anti-run compositions.
A005649 counts anti-run patterns.
A019536 counts necklace patterns.
A025047 counts alternating or wiggly compositions, complement A345192.
A226316 counts patterns avoiding (1,2,3) (weakly: A052709).
A335515 counts patterns matching (1,2,3).
Cf. A000041, A006330, A049774, A102726, A103919, A124754, A128761, A335456, A335457, A335517, A344612, A344614, A344615, A348377.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z||x>=y>=z]&]],{n,0,6}]

a(10) and beyond from Martin Ehrenstein, Jun 10 2021

A333628 Runs-resistance of the n-th composition in standard order. Number of steps taking run-lengths to reduce the n-th composition in standard order to a singleton.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Mar 31 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

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

			Starting with 13789 and repeatedly applying A333627 gives: 13789 -> 859 -> 110 -> 29 -> 11 -> 6 -> 3 -> 2, corresponding to the compositions: (1,2,2,1,1,2,1,1,2,1) -> (1,2,2,1,2,1,1) -> (1,2,1,1,2) -> (1,1,2,1) -> (2,1,1) -> (1,2) -> (1,1) -> (2), so a(13789) = 7.

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

Number of times applying A333627 to reach a power of 2, starting with n.
Positions of first appearances are A333629.
All of the following pertain to compositions in standard order (A066099):
- The length is A000120.
- The partial sums from the right are A048793.
- The sum is A070939.
- Adjacent equal pairs are counted by A124762.
- Equal runs are counted by A124767.
- Strict compositions are ranked by A233564.
- The partial sums from the left are A272020.
- Constant compositions are ranked by A272919.
- Normal compositions are ranked by A333217.
- Heinz number is A333219.
- Anti-runs are counted by A333381.
- Adjacent unequal pairs are counted by A333382.
- First appearances for specified run-lengths are A333630.
Cf. A029931, A098504, A114994, A225620, A228351, A238279, A242882, A318928, A329744, A329747, A333489.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;
Table[runsres[stc[n]],{n,100}]

cp's OEIS Frontend

A052709 Expansion of g.f. (1-sqrt(1-4*x-4*x^2))/(2*(1+x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A333256 Numbers k such that the k-th composition in standard order is strictly decreasing.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A333255 Numbers k such that the k-th composition in standard order is strictly increasing.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A333227 Numbers k such that the k-th composition in standard order is pairwise coprime, where a singleton is not coprime unless it is (1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A333224 Number of distinct positive consecutive subsequence-sums of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A333257 Number of distinct consecutive subsequence-sums of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A333766 Maximum part of the n-th composition in standard order. a(0) = 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A335458 Number of normal patterns contiguously matched by the n-th composition in standard order (A066099).

Views

Author

Keywords

Comments

Examples

Links

A052709 Expansion of g.f. (1-sqrt(1-4x-4x^2))/(2*(1+x)).