A356843 -id:A356843 - cp's OEIS frontend

A107428 Number of gap-free compositions of n.

1, 2, 4, 6, 11, 21, 39, 71, 141, 276, 542, 1070, 2110, 4189, 8351, 16618, 33134, 66129, 131937, 263483, 526453, 1051984, 2102582, 4203177, 8403116, 16800894, 33593742, 67174863, 134328816, 268624026, 537192064, 1074288649, 2148414285, 4296543181, 8592585289

Offset: 1

N. J. A. Sloane, May 26 2005

nonn

A gap-free composition contains all the parts between its smallest and largest part. a(5)=11 because we have: 5, 3+2, 2+3, 2+2+1, 2+1+2, 1+2+2, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 1+1+1+1+1. - Geoffrey Critzer, Apr 13 2014

			From _Gus Wiseman_, Oct 04 2022: (Start)
The a(0) = 1 through a(5) = 11 gap-free compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (22)    (23)
                 (21)   (112)   (32)
                 (111)  (121)   (122)
                        (211)   (212)
                        (1111)  (221)
                                (1112)
                                (1121)
                                (1211)
                                (2111)
                                (11111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Alois P. Heinz, Plot of (a(n)-2^(n-2))/2^(n-2) for n = 42..1000
P. Hitczenko and A. Knopfmacher, Gap-free compositions and gap-free samples of geometric random variables, Discrete Math., 294 (2005), 225-239.

The unordered version (partitions) is A034296, ranked by A073491.
The initial case is A107429, unordered A000009, ranked by A333217.
The unordered complement is counted by A239955, ranked by A073492.
These compositions are ranked by A356841.
The complement is counted by A356846, ranked by A356842
A356230 ranks gapless factorization lengths, firsts A356603.
A356233 counts factorizations into gapless numbers.
Cf. A055932, A073493, A137921, A251729, A356224, A356843, A356845.

b:= proc(n, i, t) option remember; `if`(n=0, t!,
      `if`(i<1 or n add(b(n, i, 0), i=1..n):
seq(a(n), n=1..40);  # Alois P. Heinz, Apr 14 2014

Table[Length[Select[Level[Map[Permutations,IntegerPartitions[n]],{2}],Length[Union[#]]==Max[#]-Min[#]+1&]],{n,1,20}] (* Geoffrey Critzer, Apr 13 2014 *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, t!, If[i < 1 || n < i, 0, Sum[b[n - i*j, i - 1, t + j]/j!, {j, 1, n/i}]]]; a[n_] := Sum[b[n, i, 0], {i, 1, n}]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Aug 30 2016, after Alois P. Heinz *)

a(n) ~ 2^(n-2). - Alois P. Heinz, Dec 07 2014

G.f.: Sum_{j>0} Sum_{k>=j} C({j..k},x) where C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/(1 - Sum_{i in {s}} (x^i)) is the g.f. for compositions such that the set of parts equals {s} with C({},x) = 1. - John Tyler Rascoe, Jun 01 2024

More terms from Vladeta Jovovic, May 26 2005

A356841 Numbers k such that the k-th composition in standard order covers an interval of positive integers (gapless).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 15, 16, 18, 20, 21, 22, 23, 26, 27, 29, 30, 31, 32, 36, 37, 38, 41, 42, 43, 44, 45, 46, 47, 50, 52, 53, 54, 55, 58, 59, 61, 62, 63, 64, 68, 72, 74, 75, 77, 78, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 101

Offset: 1

Gus Wiseman, Aug 31 2022

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.

			The terms and their corresponding standard compositions begin:
   0: ()
   1: (1)
   2: (2)
   3: (1,1)
   4: (3)
   5: (2,1)
   6: (1,2)
   7: (1,1,1)
   8: (4)
  10: (2,2)
  11: (2,1,1)
  13: (1,2,1)
  14: (1,1,2)
  15: (1,1,1,1)
  16: (5)
  18: (3,2)
  20: (2,3)
  21: (2,2,1)

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

See link for sequences related to standard compositions.
An unordered version is A073491, complement A073492.
These compositions are counted by A107428.
The complement is A356842.
The non-initial case is A356843, unordered A356845.
A356230 ranks gapless factorization lengths, firsts A356603.
A356233 counts factorizations into gapless numbers.
A356844 ranks compositions with at least one 1.
Cf. A053251, A055932, A073493, A132747, A137921, A286470, A356224/A356225.

nogapQ[m_]:=m=={}||Union[m]==Range[Min[m],Max[m]];
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],nogapQ[stc[#]]&]

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 67, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Sep 02 2022

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.

			The terms, binary expansions, and standard compositions:
   1:       1  (1)
   3:      11  (1,1)
   5:     101  (2,1)
   6:     110  (1,2)
   7:     111  (1,1,1)
   9:    1001  (3,1)
  11:    1011  (2,1,1)
  12:    1100  (1,3)
  13:    1101  (1,2,1)
  14:    1110  (1,1,2)
  15:    1111  (1,1,1,1)
  17:   10001  (4,1)
  19:   10011  (3,1,1)
  21:   10101  (2,2,1)
  22:   10110  (2,1,2)
  23:   10111  (2,1,1,1)
  24:   11000  (1,4)
  25:   11001  (1,3,1)
  26:   11010  (1,2,2)
  27:   11011  (1,2,1,1)
  28:   11100  (1,1,3)
  29:   11101  (1,1,2,1)
  30:   11110  (1,1,1,2)
  31:   11111  (1,1,1,1,1)

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

See link for sequences related to standard compositions.
The case beginning with 1 is A004760, complement A004754.
The complement is A022340.
These compositions are counted by A099036, complement A212804.
The case covering an initial interval is A333217.
The gapless but non-initial version is A356843, unordered A356845.
Cf. A004780, A005408, A055932, A073492, A073493, A132747.

Select[Range[0,100],OddQ[#]||MatchQ[IntegerDigits[#,2],{_,1,1,_}]&]

Union of A005408 and A004780.

A356845 Odd numbers with gapless prime indices.

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 35, 37, 41, 43, 45, 47, 49, 53, 59, 61, 67, 71, 73, 75, 77, 79, 81, 83, 89, 97, 101, 103, 105, 107, 109, 113, 121, 125, 127, 131, 135, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 175, 179, 181, 191

Offset: 1

Gus Wiseman, Sep 03 2022

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

A sequence is gapless if it covers an interval of positive integers.

			The terms together with their prime indices begin:
    1: {}
    3: {2}
    5: {3}
    7: {4}
    9: {2,2}
   11: {5}
   13: {6}
   15: {2,3}
   17: {7}
   19: {8}
   23: {9}
   25: {3,3}
   27: {2,2,2}
   29: {10}
   31: {11}
   35: {3,4}
   37: {12}
   41: {13}
   43: {14}

Consists of the odd terms of A073491.
These partitions are counted by A264396.
The strict case is A294674, counted by A136107.
The version for compositions is A356843, counted by A251729.
A001221 counts distinct prime factors, sum A001414.
A056239 adds up prime indices, row sums of A112798, lengths A001222.
A356069 counts gapless divisors, initial A356224 (complement A356225).
A356230 ranks gapless factorization lengths, firsts A356603.
A356233 counts factorizations into gapless numbers.
Cf. A003963, A034296, A055932, A073493, A107428, A287170, A289508, A325160, A356231, A356234, A356841.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
nogapQ[m_]:=Or[m=={},Union[m]==Range[Min[m],Max[m]]];
Select[Range[1,100,2],nogapQ[primeMS[#]]&]

A356842 Numbers k such that the k-th composition in standard order does not cover an interval of positive integers (not gapless).

Original entry on oeis.org

9, 12, 17, 19, 24, 25, 28, 33, 34, 35, 39, 40, 48, 49, 51, 56, 57, 60, 65, 66, 67, 69, 70, 71, 73, 76, 79, 80, 81, 88, 96, 97, 98, 99, 100, 103, 104, 112, 113, 115, 120, 121, 124, 129, 130, 131, 132, 133, 134, 135, 137, 138, 139, 140, 141, 142, 143, 144, 145

Offset: 1

Gus Wiseman, Sep 01 2022

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.

			The terms and their corresponding standard compositions begin:
   9: (3,1)
  12: (1,3)
  17: (4,1)
  19: (3,1,1)
  24: (1,4)
  25: (1,3,1)
  28: (1,1,3)
  33: (5,1)
  34: (4,2)
  35: (4,1,1)
  39: (3,1,1,1)
  40: (2,4)
  48: (1,5)
  49: (1,4,1)
  51: (1,3,1,1)
  56: (1,1,4)
  57: (1,1,3,1)
  60: (1,1,1,3)

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

See link for sequences related to standard compositions.
An unordered version is A073492, complement A073491.
These compositions are counted by the complement of A107428.
The complement is A356841.
The gapless but non-initial version is A356843, unordered A356845.
A356230 ranks gapless factorization lengths, firsts A356603.
A356233 counts factorizations into gapless numbers.
A356844 ranks compositions with at least one 1.
Cf. A053251, A055932, A073493, A132747, A137921, A286470, A333217, A356224/A356225.

nogapQ[m_]:=m=={}||Union[m]==Range[Min[m],Max[m]];
stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!nogapQ[stc[#]]&]

A356956 Numbers k such that the k-th composition in standard order is a gapless interval (in increasing order).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 16, 20, 32, 52, 64, 72, 128, 256, 272, 328, 512, 840, 1024, 1056, 2048, 2320, 4096, 4160, 8192, 10512, 16384, 16512, 17440, 26896, 32768, 65536, 65792, 131072, 135232, 148512, 262144, 262656, 524288, 672800, 1048576, 1049600, 1065088, 1721376

Offset: 1

Gus Wiseman, Sep 24 2022

nonn

An interval such as {3,4,5} is a set of positive integers with all differences of adjacent elements equal to 1.

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 terms and corresponding intervals begin:
        0: ()
        1: (1)
        2: (2)
        4: (3)
        6: (1,2)
        8: (4)
       16: (5)
       20: (2,3)
       32: (6)
       52: (1,2,3)
       64: (7)
       72: (3,4)
      128: (8)
      256: (9)
      272: (4,5)
      328: (2,3,4)
      512: (10)
      840: (1,2,3,4)

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

See link for sequences related to standard compositions.
These compositions are counted by A001227.
An unordered version is A073485, non-strict A073491 (complement A073492).
The initial version is A164894, non-strict A356843 (unordered A356845).
The non-strict version is A356841, initial A333217, counted by A107428.
A066311 lists gapless numbers.
A356230 ranks gapless factorization lengths, firsts A356603.
A356233 counts factorizations into gapless numbers.
A356844 ranks compositions with at least one 1.
Cf. A053251, A055932, A073493, A132747, A137921, A286470, A356224, A356842.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
chQ[y_]:=Length[y]<=1||Union[Differences[y]]=={1};
Select[Range[0,1000],chQ[stc[#]]&]

cp's OEIS Frontend

A107428 Number of gap-free compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A356841 Numbers k such that the k-th composition in standard order covers an interval of positive integers (gapless).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A356845 Odd numbers with gapless prime indices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A356842 Numbers k such that the k-th composition in standard order does not cover an interval of positive integers (not gapless).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A356956 Numbers k such that the k-th composition in standard order is a gapless interval (in increasing order).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica