A251729 -id:A251729 - cp's OEIS frontend

A107429 Number of complete compositions of n.

1, 1, 3, 4, 8, 18, 33, 65, 127, 264, 515, 1037, 2052, 4103, 8217, 16408, 32811, 65590, 131127, 262112, 524409, 1048474, 2097319, 4194250, 8389414, 16778024, 33557921, 67116113, 134235473, 268471790, 536948820, 1073893571, 2147779943, 4295515305, 8590928746

Offset: 1

N. J. A. Sloane, May 26 2005

nonn

A composition is complete if it is gap-free and contains a 1. - Geoffrey Critzer, Apr 13 2014

			a(5)=8 because we have: 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

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

Cf. A107428, A034296, A188575, A251729.

Row sums of A371417 and of A373118.

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, t!, 0),
      `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}],MemberQ[#,1]&&Length[Union[#]]==Max[#]-Min[#]+1&]],{n,1,20}] (* Geoffrey Critzer, Apr 13 2014 *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[i == 0, t!, 0], 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 *)

C_x(s,N)={my(x='x+O('x^N), g=if(#s <1,1, sum(i=1,#s, C_x(setminus(s,[s[i]]),N) * x^(s[i]) )/(1-sum(i=1,#s, x^(s[i]))))); return(g)}
B_x(N)={my(x='x+O('x^N), j=1, h=0); while((j*(j+1))/2 <= N, h += C_x(vector(j,i,i),N+1); j+=1); my(a = Vec(h)); vector(N,i,a[i])}
B_x(35) \\ John Tyler Rascoe, May 25 2024

a(n) ~ 2^(n-2). - Vaclav Kotesovec, Sep 05 2014

G.f.: Sum_{k>0} C({1..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, May 24 2024

More terms from Vladeta Jovovic, May 26 2005

A107428 Number of gap-free compositions of n.

Original entry on oeis.org

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

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

A188575 Number of non-complete compositions of n.

Original entry on oeis.org

0, 1, 1, 4, 8, 14, 31, 63, 129, 248, 509, 1011, 2044, 4089, 8167, 16360, 32725, 65482, 131017, 262176, 524167, 1048678, 2096985, 4194358, 8387802, 16776408, 33550943, 67101615, 134199983, 268399122, 536793004, 1073590077, 2147187353, 4294419287, 8588940438

Offset: 1

N. J. A. Sloane, Apr 04 2011

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000
M. Archibald and A. Knopfmacher, The largest missing value in a composition of an integer, Discrete Math., 311 (2011), 723-731.
Alois P. Heinz, Plot of (a(n)-2^(n-2))/2^(n-2) for n = 60..1000

Cf. A107429, A188576, A188577, A251729.

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

b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[i == 0, t!, 0], If[i<1 || nJean-François Alcover, Mar 09 2015, after Alois P. Heinz *)

a(n) = 2^(n-1) - A107429(n) ~ 2^(n-2). - Alois P. Heinz, Dec 06 2014

More terms from Alois P. Heinz, Dec 06 2014

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.

A264396 Number of partitions of n such that the part sizes occurring in it form an interval that does not start at 1.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 8, 8, 9, 12, 12, 14, 17, 18, 21, 25, 26, 30, 36, 39, 43, 51, 55, 62, 73, 78, 88, 101, 110, 125, 141, 154, 172, 195, 215, 238, 269, 294, 327, 368, 402, 446, 498, 547, 606, 672, 737, 814, 903, 991, 1091, 1205, 1320, 1452, 1603, 1752, 1924, 2118, 2314, 2539, 2785, 3042, 3329, 3648, 3984

Offset: 1

Emeric Deutsch, Nov 17 2015

nonn

The partitions in the definition are called non-complete gap-free (see the Grabner et al. reference).

a(n) = number of partitions of n where the largest part occurs at least twice and all other parts are distinct. Example: a(9) = 5 because we have 441, 333, 3321, 22221, and 111111111.

			a(9) = 5 because there are these partitions of 9: 9, 54, 432, 333, and 3222.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
P. J. Grabner, A. Knopfmacher, Analysis of some new partition statistics, Ramanujan J., 12, 2006, 439-454.

Cf. A251729.

g := sum(x^(2*j)*(product(1+x^i, i = 1 .. j-1))/(1-x^j), j = 1 .. 100): gser := series(g, x = 0, 80): seq(coeff(gser, x, n), n = 1 .. 70);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, `if`(i=0, 0, 1),
      `if`(i<1 or n add(b(n, i), i=2..n):
seq(a(n), n=1..70);  # Alois P. Heinz, Nov 29 2015

b[n_, i_] := b[n, i] = If[n == 0, If[i == 0, 0, 1], If[i < 1 || n < i, 0, Sum[b[n - i*j, i - 1], {j, 1, n/i}]]]; a[n_] := Sum[b[n, i], {i, 2, n}]; Table[a[n], {n, 1, 70}] (* Jean-François Alcover, Dec 22 2016, after Alois P. Heinz *)

G.f.: g = sum((x^{2j}/(1-x^j))*product(1+x^i, i=1..j), j=1..infinity).

a(n) ~ 3^(1/4) * Pi * exp(Pi*sqrt(n/3)) / (24 * n^(5/4)). - Vaclav Kotesovec, May 24 2018

A371417 Triangle read by rows: T(n,k) is the number of complete compositions of n with k parts.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 1, 0, 0, 0, 3, 4, 1, 0, 0, 0, 6, 6, 5, 1, 0, 0, 0, 0, 16, 10, 6, 1, 0, 0, 0, 0, 12, 30, 15, 7, 1, 0, 0, 0, 0, 12, 35, 50, 21, 8, 1, 0, 0, 0, 0, 24, 50, 75, 77, 28, 9, 1, 0, 0, 0, 0, 0, 90, 126, 140, 112, 36, 10, 1

Offset: 0

John Tyler Rascoe, Mar 23 2024

A composition (ordered partition) is complete if the set of parts both covers an interval (is gap-free) and contains 1.

			The triangle begins:
    k=0  1  2  3   4   5   6   7   8   9  10
n=0:  1;
n=1:  0, 1;
n=2:  0, 0, 1;
n=3:  0, 0, 2, 1;
n=4:  0, 0, 0, 3,  1;
n=5:  0, 0, 0, 3,  4,  1;
n=6:  0, 0, 0, 6,  6,  5,  1;
n=7:  0, 0, 0, 0, 16, 10,  6,  1;
n=8:  0, 0, 0, 0, 12, 30, 15,  7,  1;
n=9:  0, 0, 0, 0, 12, 35, 50, 21,  8,  1;
n=10: 0, 0, 0, 0, 24, 50, 75, 77, 28,  9,  1;
...
For n = 5 there are a total of 8 complete compositions:
  T(5,3) = 3: (221), (212), (122)
  T(5,4) = 4: (2111), (1211), (1121), (1112)
  T(5,5) = 1: (11111)

Alois P. Heinz, Rows n = 0..200, flattened

A107428 counts gap-free compositions.
A251729 counts gap-free but not complete compositions.
Cf. A107429 (row sums give complete compositions of n), A000670 (column sums), A152947 (number of nonzero terms per column).
Cf. A066099, A124774, A373118.

b:= proc(n, i, t) option remember; `if`(n=0,
     `if`(i=0, t!, 0), `if`(i<1 or n (p-> seq(coeff(p, x, i), i=0..n))(add(b(n, i, 0), i=0..n)):
seq(T(n), n=0..12);  # Alois P. Heinz, Apr 03 2024

G(N)={ my(z='z+O('z^N)); Vec(sum(i=1,N,z^(i*(i+1)/2)*t^i*prod(j=1,i,sum(k=0,N, (z^(j*k)*t^k)/(k+1)!))))}
my(v=G(10)); for(n=0, #v, if(n<1,print([1]), my(p=v[n], r=vector(n+1)); for(k=0, n, r[k+1] =k!*polcoeff(p, k)); print(r)))

T(n,k) = k!*[z^n*t^k] Sum_{i>0} z^(i*(i+1)/2)*t^i * Product_{j=1..i} Sum_{k>=0} (z^(j*k)*t^k)/(k+1)!.

cp's OEIS Frontend

A107429 Number of complete compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A107428 Number of gap-free compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A356845 Odd numbers with gapless prime indices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A188575 Number of non-complete compositions of n.

Views

Author

Keywords

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

A264396 Number of partitions of n such that the part sizes occurring in it form an interval that does not start at 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A371417 Triangle read by rows: T(n,k) is the number of complete compositions of n with k parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs