A356846 -id:A356846 - 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

A356843 Numbers k such that the k-th composition in standard order covers an interval of positive integers (gapless) but contains no 1's.

Original entry on oeis.org

2, 4, 8, 10, 16, 18, 20, 32, 36, 42, 64, 68, 72, 74, 82, 84, 128, 136, 146, 148, 164, 170, 256, 264, 272, 274, 276, 290, 292, 296, 298, 324, 328, 330, 338, 340, 512, 528, 548, 580, 584, 586, 594, 596, 658, 660, 676, 682, 1024, 1040, 1056, 1092, 1096, 1098

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 together with their corresponding standard compositions begin:
    2: (2)
    4: (3)
    8: (4)
   10: (2,2)
   16: (5)
   18: (3,2)
   20: (2,3)
   32: (6)
   36: (3,3)
   42: (2,2,2)
   64: (7)
   68: (4,3)
   72: (3,4)
   74: (3,2,2)
   82: (2,3,2)
   84: (2,2,3)

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

See link for sequences related to standard compositions.
A subset of A022340.
These compositions are counted by A251729.
The unordered version (using Heinz numbers of partitions) is A356845.
A333217 ranks complete compositions.
A356230 ranks gapless factorization lengths, firsts A356603.
A356233 counts factorizations into gapless numbers.
A356841 ranks gapless compositions, counted by A107428.
A356842 ranks non-gapless compositions, counted by A356846.
A356844 ranks compositions with at least one 1.
Cf. A053251, A055932, A073491, A073492, A073493, A137921, A356224/A356225.

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

Complement of A333217 in A356841.

A356605 Number of integer compositions of n into odd parts covering an interval of odd positive integers.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 6, 10, 15, 26, 41, 65, 104, 164, 262, 424, 687, 1112, 1792, 2898, 4677, 7556, 12197, 19699, 31836, 51466, 83234, 134593, 217674, 352057, 569452, 921165, 1490173, 2410784, 3900288, 6310436, 10210358, 16521108, 26733020, 43258086, 69999295

Offset: 0

Gus Wiseman, Aug 31 2022

nonn

			The a(1) = 1 through a(8) = 15 compositions:
  (1)  (11)  (3)    (13)    (5)      (33)      (7)        (35)
             (111)  (31)    (113)    (1113)    (133)      (53)
                    (1111)  (131)    (1131)    (313)      (1133)
                            (311)    (1311)    (331)      (1313)
                            (11111)  (3111)    (11113)    (1331)
                                     (111111)  (11131)    (3113)
                                               (11311)    (3131)
                                               (13111)    (3311)
                                               (31111)    (111113)
                                               (1111111)  (111131)
                                                          (111311)
                                                          (113111)
                                                          (131111)
                                                          (311111)
                                                          (11111111)

These compositions are ranked by the intersection of A060142 and A356841.
Before restricting to odds we have A107428, initial A107429.
The not necessarily gapless version is A324969 (essentially A000045).
The strict case is A332032.
The initial case is A356604.
The case of partitions is A356737, initial A053251 (ranked by A356232).
A000041 counts partitions, compositions A011782.
A066208 lists numbers with all odd prime indices, counted by A000009.
A073491 lists numbers with gapless prime indices, initial A055932.
Cf. A001227, A066205, A137921, A333217, A356224, A356846.

nogapQ[m_]:=m=={}||Union[m]==Range[Min[m],Max[m]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], And@@OddQ/@#&&nogapQ[(#+1)/2]&]],{n,0,15}]

More terms from Alois P. Heinz, Sep 01 2022

A356737 Number of integer partitions of n into odd parts covering an interval of odd numbers.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 4, 6, 6, 7, 8, 9, 10, 13, 13, 15, 17, 19, 21, 25, 26, 29, 33, 37, 40, 46, 49, 54, 61, 66, 72, 81, 87, 97, 106, 115, 125, 139, 150, 163, 179, 193, 210, 232, 248, 269, 293, 317, 343, 373, 401, 433, 470, 507, 545, 590, 633, 682, 737, 790

Offset: 0

Gus Wiseman, Sep 03 2022

nonn

			The a(1) = 1 through a(9) = 6 partitions:
  1  11  3    31    5      33      7        53        9
         111  1111  311    3111    331      3311      333
                    11111  111111  31111    311111    531
                                   1111111  11111111  33111
                                                      3111111
                                                      111111111

The strict case is A034178, for compositions A332032.
The initial case is A053251, ranked by A356232 and A356603.
The initial case for compositions is A356604.
The version for compositions is A356605, ranked by A060142 /\ A356841.
A000041 counts partitions, compositions A011782.
A066208 lists numbers with all odd prime indices, counted by A000009.
A073491 lists gapless numbers, initial A055932.
Cf. A001227, A066205, A107428, A107429, A333217, A356224, A356846.

nogapQ[m_]:=Or[m=={},Union[m]==Range[Min[m],Max[m]]];
Table[Length[Select[IntegerPartitions[n],And@@OddQ/@#&&nogapQ[(#+1)/2]&]],{n,0,30}]

cp's OEIS Frontend

A107428 Number of gap-free compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A356843 Numbers k such that the k-th composition in standard order covers an interval of positive integers (gapless) but contains no 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A356605 Number of integer compositions of n into odd parts covering an interval of odd positive integers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A356737 Number of integer partitions of n into odd parts covering an interval of odd numbers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica