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

A251729 Number of gap-free but not complete compositions of n.

Original entry on oeis.org

0, 1, 1, 2, 3, 3, 6, 6, 14, 12, 27, 33, 58, 86, 134, 210, 323, 539, 810, 1371, 2044, 3510, 5263, 8927, 13702, 22870, 35821, 58750, 93343, 152236, 243244, 395078, 634342, 1027876, 1656543, 2676693, 4325727, 6982440, 11299457, 18232217, 29518334, 47641410

Offset: 1

Alois P. Heinz, Dec 07 2014

nonn

A composition is gap-free but not complete if all integers in the interval defined by the smallest and the largest part are parts but 1 is not a part.

			a(6) = 3: [6], [3,3], [2,2,2].
a(7) = 6: [7], [3,4], [4,3], [2,2,3], [2,3,2], [3,2,2].

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

Cf. A001622, A034296, A107428, A107429, A188575, A238353, A264396.

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, 0, t!),
     `if`(i<1 or n add(b(n, i, 0), i=1..n):
seq(a(n), n=1..50);

b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[i == 0, 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}];
Array[a, 50] (* Jean-François Alcover, Jan 25 2021, after Alois P. Heinz *)

a(n) = A107428(n) - A107429(n).

lim_{n -> oo} a(n)/a(n-1) = (1+sqrt(5))/2 = phi = A001622.

A356846 Number of integer compositions of n into parts not covering an interval of positive integers.

Original entry on oeis.org

0, 0, 0, 0, 2, 5, 11, 25, 57, 115, 236, 482, 978, 1986, 4003, 8033, 16150, 32402, 64943, 130207, 260805, 522123, 1045168, 2091722, 4185431, 8374100, 16753538, 33515122, 67042865, 134106640, 268246886, 536549760, 1073194999, 2146553011, 4293391411, 8587283895

Offset: 0

Gus Wiseman, Sep 03 2022

nonn

			The a(0) = 0 through a(6) = 8 compositions:
  .  .  .  .  (13)  (14)   (15)
              (31)  (41)   (24)
                    (113)  (42)
                    (131)  (51)
                    (311)  (114)
                           (141)
                           (411)
                           (1113)
                           (1131)
                           (1311)
                           (3111)

The complement is counted by A107428, initial A107429.
The case of partitions is A239955, ranked by A073492, initial A053251, complement A034296.
These compositions are ranked by A356842, complement A356841.
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, A060142, A080259, A188575, A239327, A356604, A356605.

gappyQ[m_]:=And[m!={},Union[m]!=Range[Min[m],Max[m]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],gappyQ]],{n,0,15}]

a(n) = A011782(n) - A107428(n).

A188576 Number of compositions of n with the LMV property.

Original entry on oeis.org

0, 1, 1, 4, 6, 14, 26, 54, 105, 213, 423, 849, 1697, 3399, 6799, 13608, 27220, 54451, 108901, 217789, 435517, 870892, 1741467, 3482322, 6963512, 13925078, 27846979, 55689150, 111371677, 222735709, 445466058, 890938357, 1781916885, 3563957177, 7128223846

Offset: 1

N. J. A. Sloane, Apr 04 2011

nonn

A composition has the largest missing value (LMV) property if its largest part is at least 2 and it does not contain a part one less than its largest part. - Andrew Howroyd, May 18 2020

			The a(5) = 6 compositions of 5 with the LMV property are: 5, 14, 41, 113, 131, 311. - _Andrew Howroyd_, May 18 2020

Andrew Howroyd, 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.

Cf. A188575, A188577.

seq(n)={Vec(sum(k=2, n, 1/(1 - x*(1-x^(k-2))/(1-x) - x^k) - 1/(1 - x*(1-x^(k-2))/(1-x))  + O(x*x^n)), -n)} \\ Andrew Howroyd, May 18 2020

G.f.: Sum_{k>=2} 1/(1 - x*(1-x^(k-2))/(1-x) - x^k) - 1/(1 - x*(1-x^(k-2))/(1-x)). - Andrew Howroyd, May 18 2020

Terms a(21) and beyond from Andrew Howroyd, May 18 2020

A188577 Sum of the largest missing values in all compositions of n with the LMV property.

Original entry on oeis.org

0, 1, 2, 8, 18, 39, 89, 195, 415, 865, 1823, 3787, 7869, 16230, 33352, 68422, 140013, 285991, 583235, 1187718

Offset: 1

N. J. A. Sloane, Apr 04 2011

M. Archibald and A. Knopfmacher, The largest missing value in a composition of an integer, Discrete Math., 311 (2011), 723-731.

Cf. A188575, A188576.

cp's OEIS Frontend

A107429 Number of complete compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A251729 Number of gap-free but not complete compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A356846 Number of integer compositions of n into parts not covering an interval of positive integers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A188576 Number of compositions of n with the LMV property.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A188577 Sum of the largest missing values in all compositions of n with the LMV property.

Views

Author

Keywords

Links

Crossrefs