A272919 -id:A272919 - cp's OEIS frontend

A373948 Run-compression encoded as a transformation of compositions in standard order.

0, 1, 2, 1, 4, 5, 6, 1, 8, 9, 2, 5, 12, 13, 6, 1, 16, 17, 18, 9, 20, 5, 22, 5, 24, 25, 6, 13, 12, 13, 6, 1, 32, 33, 34, 17, 4, 37, 38, 9, 40, 41, 2, 5, 44, 45, 22, 5, 48, 49, 50, 25, 52, 13, 54, 13, 24, 25, 6, 13, 12, 13, 6, 1, 64, 65, 66, 33, 68, 69, 70, 17, 72

Offset: 0

Gus Wiseman, Jun 24 2024

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 the (run-) compression of a sequence to be the anti-run obtained by reducing each run of repeated parts to a single part. Alternatively, compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has compression (1,2,1).
For the present sequence, the a(n)-th composition in standard order is obtained by compressing the n-th composition in standard order.

			The standard compositions and their compressions begin:
   0: ()        -->  0: ()
   1: (1)       -->  1: (1)
   2: (2)       -->  2: (2)
   3: (1,1)     -->  1: (1)
   4: (3)       -->  4: (3)
   5: (2,1)     -->  5: (2,1)
   6: (1,2)     -->  6: (1,2)
   7: (1,1,1)   -->  1: (1)
   8: (4)       -->  8: (4)
   9: (3,1)     -->  9: (3,1)
  10: (2,2)     -->  2: (2)
  11: (2,1,1)   -->  5: (2,1)
  12: (1,3)     --> 12: (1,3)
  13: (1,2,1)   --> 13: (1,2,1)
  14: (1,1,2)   -->  6: (1,2)
  15: (1,1,1,1) -->  1: (1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Positions of 1's are A000225.
The image is A333489, counted by A003242.
Sum of standard composition for a(n) is given by A373953, length A124767.
A037201 gives compression of first differences of primes, halved A373947.
A066099 lists the parts of all compositions in standard order.
A114901 counts compositions with no isolated parts.
A116861 counts partitions by compressed sum, by length A116608.
A240085 counts compositions with no unique parts.
A333755 counts compositions by compressed length.
A373949 counts compositions by compressed sum, opposite A373951.
Cf. A106356, A124762, A238130, A238279, A272919, A333381, A333382, A333627, A373952, A373954.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[First/@Split[stc[n]]],{n,0,30}]

A029837(a(n)) = A373953(n).

A000120(a(n)) = A124767(n).

A048896 a(n) = 2^(A000120(n+1) - 1), n >= 0.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 4, 1, 2, 2, 4, 2, 4, 4, 8, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4

Offset: 0

Wolfdieter Lang

a(n) = 2^A048881 = 2^{maximal power of 2 dividing the n-th Catalan number (A000108)}. [Comment corrected by N. J. A. Sloane, Apr 30 2018]
Row sums of triangle A128937. - Philippe Deléham, May 02 2007
a(n) = sum of (n+1)-th row terms of triangle A167364. - Gary W. Adamson, Nov 01 2009
a(n), n >= 1: Numerators of Maclaurin series for 1 - ((sin x)/x)^2, A117972(n), n >= 2: Denominators of Maclaurin series for 1 - ((sin x)/x)^2, the correlation function in Montgomery's pair correlation conjecture. - Daniel Forgues, Oct 16 2011
For n > 0: a(n) = A007954(A007931(n)). - Reinhard Zumkeller, Oct 26 2012
a(n) = A261363(2*(n+1), n+1). - Reinhard Zumkeller, Aug 16 2015
From Gus Wiseman, Oct 30 2022: (Start)
Also the number of coarsenings of the (n+1)-th composition in standard order. 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. See link for sequences related to standard compositions. For example, the a(10) = 4 coarsenings of (2,1,1) are: (2,1,1), (2,2), (3,1), (4).
Also the number of times n+1 appears in A357134. For example, 11 appears at positions 11, 20, 33, and 1024, so a(10) = 4.
(End)

			From _Omar E. Pol_, Jul 21 2009: (Start)
If written as a triangle:
  1;
  1,2;
  1,2,2,4;
  1,2,2,4,2,4,4,8;
  1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16;
  1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32;
  ...,
the first half-rows converge to Gould's sequence A001316.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, Some Facts and Conjectures about Mandelbrot Polynomials, Maple Transactions (2021) Vol. 1, No. 1 Article 1.
Neil J. Calkin, Eunice Y. S. Chan, Robert M. Corless, David J. Jeffrey, and Piers W. Lawrence, A Fractal Eigenvector, arXiv:2104.01116 [math.DS], 2021.
Emeric Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
OEIS Wiki, Montgomery's pair correlation conjecture
Gus Wiseman, Statistics, classes, and transformations of standard compositions

This is Guy Steele's sequence GS(3, 5) (see A135416).
Equals first right hand column of triangle A160468.
Equals A160469(n+1)/A002425(n+1).
Cf. A000079, A001316, A117972, A160476, A167364, A220466, A261363.
Standard compositions are listed by A066099.
The opposite version (counting refinements) is A080100.
The version for Heinz numbers of partitions is A317141.
Cf. A000120, A001511, A029931, A048793, A058891, A070939, A272919, A357134.

a048896 n = a048896_list !! n
a048896_list = f [1] where f (x:xs) = x : f (xs ++ [x,2*x])
-- Reinhard Zumkeller, Mar 07 2011

import Data.List (transpose)
a048896 = a000079 . a000120
a048896_list = 1 : concat (transpose
   [zipWith (-) (map (* 2) a048896_list) a048896_list,
    map (* 2) a048896_list])
-- Reinhard Zumkeller, Jun 16 2013

[Numerator(2^n / Factorial(n+1)): n in [0..100]]; // Vincenzo Librandi, Apr 12 2014

a := n -> 2^(add(i,i=convert(n+1,base,2))-1): seq(a(n), n=0..97); # Peter Luschny, May 01 2009

NestList[Flatten[#1 /. a_Integer -> {a, 2 a}] &, {1}, 4] // Flatten (* Robert G. Wilson v, Aug 01 2012 *)
Table[Numerator[2^n / (n + 1)!], {n, 0, 200}] (* Vincenzo Librandi, Apr 12 2014 *)
Denominator[Table[BernoulliB[2*n] / (Zeta[2*n]/Pi^(2*n)), {n, 1, 100}]] (* Terry D. Grant, May 29 2017 *)
Table[Denominator[((2 n)!/2^(2 n + 1)) (-1)^n], {n, 1, 100}]/4 (* Terry D. Grant, May 29 2017 *)
2^IntegerExponent[CatalanNumber[Range[0,100]],2] (* Harvey P. Dale, Apr 30 2018 *)

a(n)=if(n<1,1,if(n%2,a(n/2-1/2),2*a(n-1)))

a(n) = 1 << (hammingweight(n+1)-1); \\ Kevin Ryde, Feb 19 2022

a(n) = 2^A048881(n).
a(n) = 2^k if 2^k divides A000108(n) but 2^(k+1) does not divide A000108(n).
It appears that a(n) = Sum_{k=0..n} binomial(2*(n+1), k) mod 2. - Christopher Lenard (c.lenard(AT)bendigo.latrobe.edu.au), Aug 20 2001
a(0) = 1; a(2*n) = 2*a(2*n-1); a(2*n+1) = a(n).
a(n) = (1/2) * A001316(n+1). - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 26 2004
It appears that a(n) = Sum_{k=0..2n} floor(binomial(2n+2, k+1)/2)(-1)^k = 2^n - Sum_{k=0..n+1} floor(binomial(n+1, k)/2). - Paul Barry, Dec 24 2004
a(n) = Sum_{k=0..n} (T(n,k) mod 2) where T = A039598, A053121, A052179, A124575, A126075, A126093. - Philippe Deléham, May 02 2007
a(n) = numerator(b(n)), where sin(x)^2/x = Sum_{n>0} b(n)*(-1)^n x^(2*n-1). - Vladimir Kruchinin, Feb 06 2013
a((2*n+1)*2^p-1) = A001316(n), p >= 0 and n >= 0. - Johannes W. Meijer, Feb 12 2013
a(n) = numerator(2^n / (n+1)!). - Vincenzo Librandi, Apr 12 2014
a(2n) = (2n+1)!/(n!n!)/A001803(n). - Richard Turk, Aug 23 2017
a(2n-1) = (2n-1)!/(n!(n-1)!)/A001790(n). - Richard Turk, Aug 23 2017

New definition from N. J. A. Sloane, Mar 01 2008

A124769 Number of strictly decreasing runs for compositions in standard order.

Original entry on oeis.org

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

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

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. a(n) is the number of maximal strictly decreasing runs in this composition. Alternatively, a(n) is one plus the number of weak ascents in the same composition. For example, the strictly decreasing runs of the 1234567th composition are ((3,2,1),(2),(2,1),(2),(5,1),(1),(1)), so a(1234567) = 7. The 6 weak ascents together with the strict descents are: 3 > 2 > 1 <= 2 <= 2 > 1 <= 2 <= 5 > 1 <= 1 <= 1. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; the strictly increasing runs are 2,1; 1; so a(11) = 2.
The table starts:
  0
  1
  1 2
  1 1 2 3
  1 1 2 2 2 2 3 4
  1 1 1 2 2 2 2 3 2 2 3 3 3 3 4 5
  1 1 1 2 2 1 2 3 2 2 3 3 2 2 3 4 2 2 2 3 3 3 3 4 3 3 4 4 4 4 5 6

Cf. A066099, A124764, A011782 (row lengths).
Compositions of n with k weak ascents are A333213.
Positions of ones are A333256.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Partial sums from the right are A048793 (triangle).
- Sum is A070939.
- Weakly decreasing compositions are A114994.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769 (this sequence).
- Reversed initial intervals A164894.
- Weakly increasing compositions are A225620.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Permutations are A333218.
- Heinz number is A333219.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
- Anti-runs are A333489.
Cf. A124760, A124761, A124763, A233249, A238343.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Split[stc[n],Greater]],{n,0,100}] (* Gus Wiseman, Apr 08 2020 *)

a(0) = 0, a(n) = A124764(n) + 1 for n > 0.

A344618 Reverse-alternating sums of standard compositions (A066099). Alternating sums of the compositions ranked by A228351.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jun 03 2021

Up to sign, same as A124754.
The reverse-alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(k-i) y_i.
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.

			The sequence of nonnegative integers together with the corresponding standard compositions and their reverse-alternating sums begins:
  0:     () ->  0    15: (1111) ->  0    30:  (1112) ->  1
  1:    (1) ->  1    16:    (5) ->  5    31: (11111) ->  1
  2:    (2) ->  2    17:   (41) -> -3    32:     (6) ->  6
  3:   (11) ->  0    18:   (32) -> -1    33:    (51) -> -4
  4:    (3) ->  3    19:  (311) ->  3    34:    (42) -> -2
  5:   (21) -> -1    20:   (23) ->  1    35:   (411) ->  4
  6:   (12) ->  1    21:  (221) ->  1    36:    (33) ->  0
  7:  (111) ->  1    22:  (212) ->  3    37:   (321) ->  2
  8:    (4) ->  4    23: (2111) -> -1    38:   (312) ->  4
  9:   (31) -> -2    24:   (14) ->  3    39:  (3111) -> -2
  10:  (22) ->  0    25:  (131) -> -1    40:    (24) ->  2
  11: (211) ->  2    26:  (122) ->  1    41:   (231) ->  0
  12:  (13) ->  2    27: (1211) ->  1    42:   (222) ->  2
  13: (121) ->  0    28:  (113) ->  3    43:  (2211) ->  0
  14: (112) ->  2    29: (1121) -> -1    44:   (213) ->  4
Triangle begins (row lengths A011782):
  0
  1
  2  0
  3 -1  1  1
  4 -2  0  2  2  0  2  0
  5 -3 -1  3  1  1  3 -1  3 -1  1  1  3 -1  1  1

Up to sign, same as the reverse version A124754.
The version for Heinz numbers of partitions is A344616.
Positions of zeros are A344619.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 is the alternating sum of the prime indices of n (reverse: A344616).
A116406 counts compositions with alternating sum >= 0.
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
All of the following pertain to compositions in standard order:
- The length is A000120.
- Converting to reversed ranking gives A059893.
- The rows are A066099.
- The sum is A070939.
- The runs are counted by A124767.
- The reversed version is A228351.
- Strict compositions are ranked by A233564.
- Constant compositions are ranked by A272919.
- The Heinz number is A333219.
- Anti-run compositions are ranked by A333489.
Cf. A000070, A000097, A003242, A028260, A119899, A239830, A344605, A344607, A344608, A344650, A344739.

sats[y_]:=Sum[(-1)^(i-Length[y])*y[[i]],{i,Length[y]}];
stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]]
Table[sats[stc[n]],{n,0,100}]

A351014 Number of distinct runs in the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Feb 07 2022

nonn

The n-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 n, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The number 3310 has binary expansion 110011101110 and standard composition (1,3,1,1,2,1,1,2), with runs (1), (3), (1,1), (2), (1,1), (2), of which 4 are distinct, so a(3310) = 4.

Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

Counting not necessarily distinct runs gives A124767.
Using binary expansions instead of standard compositions gives A297770.
Positions of first appearances are A351015.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A085207 represents concatenation of standard compositions, reverse A085208.
A333489 ranks anti-runs, complement A348612.
A345167 ranks alternating compositions, counted by A025047.
A351204 counts partitions where every permutation has all distinct runs.
Counting words with all distinct runs:
- A351013 = compositions, for run-lengths A329739, ranked by A351290.
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020, ranked by A175413.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Selected statistics of standard compositions:
- Length is A000120.
- Sum is A070939.
- Heinz number is A333219.
- Number of distinct parts is A334028.
Selected classes of standard compositions:
- Partitions are A114994, strict A333256.
- Multisets are A225620, strict A333255.
- Strict compositions are A233564.
- Constant compositions are A272919.
Cf. A098859, A106356, A116608, A238279, A242882, A318928, A325545, A328592, A329745, A350952, A351201.

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

A344619 The a(n)-th composition in standard order (A066099) has alternating sum 0.

Original entry on oeis.org

0, 3, 10, 13, 15, 36, 41, 43, 46, 50, 53, 55, 58, 61, 63, 136, 145, 147, 150, 156, 162, 165, 167, 170, 173, 175, 180, 185, 187, 190, 196, 201, 203, 206, 210, 213, 215, 218, 221, 223, 228, 233, 235, 238, 242, 245, 247, 250, 253, 255, 528, 545, 547, 550, 556, 568

Offset: 1

Gus Wiseman, Jun 03 2021

nonn

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

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.

			The sequence of terms together with the corresponding compositions begins:
    0: ()
    3: (1,1)
   10: (2,2)
   13: (1,2,1)
   15: (1,1,1,1)
   36: (3,3)
   41: (2,3,1)
   43: (2,2,1,1)
   46: (2,1,1,2)
   50: (1,3,2)
   53: (1,2,2,1)
   55: (1,2,1,1,1)
   58: (1,1,2,2)
   61: (1,1,1,2,1)
   63: (1,1,1,1,1,1)
  136: (4,4)
  145: (3,4,1)
  147: (3,3,1,1)
  150: (3,2,1,2)
  156: (3,1,1,3)

The version for Heinz numbers of partitions is A000290, counted by A000041.
These are the positions of zeros in A344618.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A116406 counts compositions with alternating sum >= 0.
A124754 gives the alternating sum of standard compositions.
A316524 is the alternating sum of the prime indices of n.
A344604 counts wiggly compositions with twins.
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
A344616 gives the alternating sum of reversed prime indices.
All of the following pertain to compositions in standard order:
- The length is A000120.
- Converting to reversed ranking gives A059893.
- The rows are A066099.
- The sum is A070939.
- The runs are counted by A124767.
- The reversed version is A228351.
- Strict compositions are ranked by A233564.
- Constant compositions are ranked by A272919.
- The Heinz number is A333219.
- Anti-run compositions are ranked by A333489.
Cf. A000070, A000097, A003242, A006330, A028260, A119899, A239830, A344605, A344607, A344650, A344739.

ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]]
Select[Range[0,100],ats[stc[#]]==0&]

A345168 Numbers k such that the k-th composition in standard order is not alternating.

Original entry on oeis.org

3, 7, 10, 11, 14, 15, 19, 21, 23, 26, 27, 28, 29, 30, 31, 35, 36, 37, 39, 42, 43, 46, 47, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 69, 71, 73, 74, 75, 78, 79, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 99, 100, 101, 103, 104, 105, 106, 107, 110

Offset: 1

Gus Wiseman, Jun 15 2021

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.

A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

			The sequence of terms together with their binary indices begins:
     3: (1,1)          35: (4,1,1)        59: (1,1,2,1,1)
     7: (1,1,1)        36: (3,3)          60: (1,1,1,3)
    10: (2,2)          37: (3,2,1)        61: (1,1,1,2,1)
    11: (2,1,1)        39: (3,1,1,1)      62: (1,1,1,1,2)
    14: (1,1,2)        42: (2,2,2)        63: (1,1,1,1,1,1)
    15: (1,1,1,1)      43: (2,2,1,1)      67: (5,1,1)
    19: (3,1,1)        46: (2,1,1,2)      69: (4,2,1)
    21: (2,2,1)        47: (2,1,1,1,1)    71: (4,1,1,1)
    23: (2,1,1,1)      51: (1,3,1,1)      73: (3,3,1)
    26: (1,2,2)        52: (1,2,3)        74: (3,2,2)
    27: (1,2,1,1)      53: (1,2,2,1)      75: (3,2,1,1)
    28: (1,1,3)        55: (1,2,1,1,1)    78: (3,1,1,2)
    29: (1,1,2,1)      56: (1,1,4)        79: (3,1,1,1,1)
    30: (1,1,1,2)      57: (1,1,3,1)      83: (2,3,1,1)
    31: (1,1,1,1,1)    58: (1,1,2,2)      84: (2,2,3)

Wikipedia, Alternating permutation

The complement is A345167.
These compositions are counted by A345192.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A025047 counts alternating or wiggly compositions, directed A025048, A025049.
A344604 counts alternating compositions with twins.
A345194 counts alternating patterns (with twins: A344605).
A345164 counts alternating permutations of prime indices (with twins: A344606).
A345165 counts partitions without a alternating permutation, ranked by A345171.
A345170 counts partitions with a alternating permutation, ranked by A345172.
A348610 counts alternating ordered factorizations, complement A348613.
Statistics of standard compositions:
- Length is A000120.
- Constant runs are A124767.
- Heinz number is A333219.
- Number of maximal anti-runs is A333381.
- Runs-resistance is A333628.
- Number of distinct parts is A334028.
Classes of standard compositions:
- Weakly decreasing compositions (partitions) are A114994.
- Weakly increasing compositions (multisets) are A225620.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Anti-run compositions are A333489.
- Non-anti-run compositions are A348612.
Cf. A001222, A005649, A008965, A059893, A106356, A238279, A344615, A345162, A345163, A345166, A345169, A348377, A348380.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]==Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Select[Range[0,100],Not@*wigQ@*stc]

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

A373953 Sum of run-compression of the n-th integer composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jun 25 2024

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 the (run-) compression of a sequence to be the anti-run obtained by reducing each run of repeated parts to a single part. Alternatively, compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has compression (1,2,1).

			The standard compositions and their compressions and compression sums begin:
   0: ()        --> ()      --> 0
   1: (1)       --> (1)     --> 1
   2: (2)       --> (2)     --> 2
   3: (1,1)     --> (1)     --> 1
   4: (3)       --> (3)     --> 3
   5: (2,1)     --> (2,1)   --> 3
   6: (1,2)     --> (1,2)   --> 3
   7: (1,1,1)   --> (1)     --> 1
   8: (4)       --> (4)     --> 4
   9: (3,1)     --> (3,1)   --> 4
  10: (2,2)     --> (2)     --> 2
  11: (2,1,1)   --> (2,1)   --> 3
  12: (1,3)     --> (1,3)   --> 4
  13: (1,2,1)   --> (1,2,1) --> 4
  14: (1,1,2)   --> (1,2)   --> 3
  15: (1,1,1,1) --> (1)     --> 1

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Positions of 1's are A000225.
Counting partitions by this statistic gives A116861, by length A116608.
For length instead of sum we have A124767, counted by A238279 and A333755.
Compositions counted by this statistic are A373949, opposite A373951.
A037201 gives compression of first differences of primes, halved A373947.
A066099 lists the parts of all compositions in standard order.
A114901 counts compositions with no isolated parts.
A240085 counts compositions with no unique parts.
A333489 ranks anti-runs, counted by A003242.
Cf. A106356, A124762, A238130, A238343, A272919, A285981, A333381, A333382, A333627, A373952, A373954.

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

a(n) = A029837(A373948(n)).

cp's OEIS Frontend

A373948 Run-compression encoded as a transformation of compositions in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A048896 a(n) = 2^(A000120(n+1) - 1), n >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A124769 Number of strictly decreasing runs for compositions in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A344618 Reverse-alternating sums of standard compositions (A066099). Alternating sums of the compositions ranked by A228351.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A351014 Number of distinct runs in the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A344619 The a(n)-th composition in standard order (A066099) has alternating sum 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A345168 Numbers k such that the k-th composition in standard order is not alternating.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views