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

A332721 Number of compositions of n^2 with parts <= n, such that each element of [n] is used at least once.

Original entry on oeis.org

1, 1, 3, 72, 5752, 1501620, 1171326960, 2571831080160, 15245263511750160, 236246829658682027760, 9325247205993698149853760, 917699267902161951609308035200, 221117091698491444413008381486903040, 128433050637127079872089064922773889126400

Offset: 0

Alois P. Heinz, Feb 21 2020

nonn

			a(2) = 3: 112, 121, 211.
a(3) = 72: 111123, 111132, 111213, 111231, 111312, 111321, 112113, 112131, 112311, 113112, 113121, 113211, 121113, 121131, 121311, 123111, 131112, 131121, 131211, 132111, 211113, 211131, 211311, 213111, 231111, 311112, 311121, 311211, 312111, 321111, 11223, 11232, 11322, 12123, 12132, 12213, 12231, 12312, 12321, 13122, 13212, 13221, 21123, 21132, 21213, 21231, 21312, 21321, 22113, 22131, 22311, 23112, 23121, 23211, 31122, 31212, 31221, 32112, 32121, 32211, 1233, 1323, 1332, 2133, 2313, 2331, 3123, 3132, 3213, 3231, 3312, 3321.

Alois P. Heinz, Table of n, a(n) for n = 0..50

Cf. A000079, A000290, A103488, A332716, A332747, A332796, A373118.

b:= proc(n, i, p) option remember; `if`(n=0 or i=1, (p+n)!
       /(n+1)!, add(b(n-i*j, i-1, p+j)/(j+1)!, j=0..n/i))
    end:
a:= n-> b(n*(n-1)/2, n$2):
seq(a(n), n=0..15);

b[n_, i_, p_] := b[n, i, p] = If[n == 0 || i == 1, (p + n)!/(n + 1)!, Sum[b[n - i*j, i - 1, p + j]/(j + 1)!, {j, 0, n/i}]];
a[n_] := b[n(n - 1)/2, n, n];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Mar 04 2022, after Alois P. Heinz *)

a(n) = A373118(n^2,n). - Alois P. Heinz, May 26 2024

A373306 Sum over all complete compositions of n of the element multiset size.

Original entry on oeis.org

0, 1, 2, 7, 13, 30, 73, 157, 345, 743, 1650, 3517, 7593, 16120, 34294, 72683, 153475, 323293, 679231, 1423721, 2977692, 6218395, 12959249, 26970243, 56037071, 116280086, 240953162, 498719275, 1031029386, 2129266321, 4392871427, 9054428894, 18645998093

Offset: 0

Alois P. Heinz, May 31 2024

nonn

A complete composition of n has element set [k] with k<=n (without gaps).

			a(1) = 1: 1.
a(2) = 2: 11.
a(3) = 7 = 2 + 2 + 3: 12, 21, 111.
a(4) = 13 = 3 + 3 + 3 + 4: 112, 121, 211, 1111.
a(5) = 30 = 3*3 + 4*4 + 5: 122, 212, 221, 1112, 1121, 1211, 2111, 11111.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A107429, A373118, A373305.

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, [t!, 0], 0),
     `if`(i<1 or n p+[0, p[1]]*j)(
        b(n-i*j, i-1, t+j)/j!), j=1..n/i)))
    end:
a:= n-> add(b(n, k, 0)[2], k=0..floor((sqrt(1+8*n)-1)/2)):
seq(a(n), n=0..32);

b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[i == 0, {t!, 0}, {0, 0}], If[i < 1 || n < i*(i + 1)/2, {0, 0}, Sum[Function[p, p + {0, p[[1]]}*j][b[n - i*j, i - 1, t + j]/j!], {j, 1, n/i}]]];
a[n_] := Sum[b[n, k, 0][[2]], {k, 0, Floor[(Sqrt[1 + 8*n] - 1)/2]}];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jun 08 2024, after Alois P. Heinz *)

G.f.: Sum_{k>0} d/dy C({1..k},x,y)|y = 1 where C({s},x,y) = Sum_{i in {s}} (C({s}-{i},x,y)*y*x^i)/(1 - Sum_{i in {s}} (y*x^i)) with C({},x,y) = 1. - John Tyler Rascoe, Jun 18 2024

A245738 Number of compositions of n into parts 1 and 2 with both parts present.

Original entry on oeis.org

2, 3, 7, 11, 20, 32, 54, 87, 143, 231, 376, 608, 986, 1595, 2583, 4179, 6764, 10944, 17710, 28655, 46367, 75023, 121392, 196416, 317810, 514227, 832039, 1346267, 2178308, 3524576, 5702886, 9227463, 14930351, 24157815, 39088168, 63245984, 102334154, 165580139, 267914295, 433494435, 701408732, 1134903168, 1836311902

Offset: 3

David Neil McGrath, Jul 31 2014

			a(9) = 54. The tuples are (22221) = 5!/4! = 5, (222111) = 6!/3!/3! = 20, (2211111) = 7!/5!/2! = 21, (21111111) = 8!/7! = 8.

Colin Barker, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1).

Cf. A245332, A245492, A245487, A245527.

Column k=2 of A373118.

LinearRecurrence[{1,2,-1,-1},{2,3,7,11},50] (* Harvey P. Dale, Dec 20 2014 *)

Vec(1+1/(1-x-x^2)-1/(1-x)-1/(1-x^2)+O(x^66)) \\ Joerg Arndt, Aug 04 2014

G.f.: 1+1/(1-x-x^2)-1/(1-x)-1/(1-x^2).
a(n) = A052952(n-4)+2*A052952(n-3). - R. J. Mathar, Aug 05 2014
From Colin Barker, Jul 13 2017: (Start)
a(n) = (-20 + sqrt(5)*(-(1-sqrt(5))^(1+n) + (1+sqrt(5))^(1+n))/2^n) / 10 for n even.
a(n) = (-10 + sqrt(5)*(-(1-sqrt(5))^(1+n) + (1+sqrt(5))^(1+n))/2^n) / 10 for n odd.
a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4) for n>6. (End)
a(n) = Sum_{i=1..floor((n-1)/2)} C(n-i,i). - Wesley Ivan Hurt, Sep 19 2017
a(n) = A000045(n+1) - A000034(n+1). - J. M. Bergot and Robert Israel, Oct 11 2021

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)!.

A373305 Sum over all complete compositions of n of the element set cardinality.

Original entry on oeis.org

0, 1, 1, 5, 7, 15, 41, 77, 161, 325, 727, 1460, 3058, 6228, 12815, 26447, 54099, 110800, 226247, 461531, 939678, 1914189, 3890279, 7905962, 16045367, 32550830, 65971827, 133645098, 270561031, 547468214, 1107208235, 2238242852, 4522679064, 9135128917

Offset: 0

Alois P. Heinz, May 31 2024

nonn

A complete composition of n has element set [k] with k<=n (without gaps).

			a(1) = 1: 1.
a(2) = 1: 11.
a(3) = 5 = 2 + 2 + 1: 12, 21, 111.
a(4) = 7 = 2 + 2 + 2 + 1: 112, 121, 211, 1111.
a(5) = 15 = 7*2 + 1: 122, 212, 221, 1112, 1121, 1211, 2111, 11111.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A003056, A107429, A373118, A373306.

g:= proc(n, i, t) `if`(n=0, `if`(i=0, t!, 0),
     `if`(i<1 or n add(g(n, k, 0)*k, k=0..floor((sqrt(1+8*n)-1)/2)):
seq(a(n), n=0..33);

g[n_, i_, t_] := If[n == 0, If[i == 0, t!, 0], If[i < 1 || n < i*(i+1)/2, 0, b[n, i, t]]];
b[n_, i_, t_] := b[n, i, t] = Sum[g[n-i*j, i-1, t+j]/j!, {j, 1, n/i}];
a[n_] := Sum[g[n, k, 0]*k, {k, 0, Floor[(Sqrt[1 + 8*n] - 1)/2]}];
Table[a[n], {n, 0, 33}] (* Jean-François Alcover, Jun 08 2024, after Alois P. Heinz *)

a(n) = Sum_{k=0..A003056(n)} k * A373118(n,k).

A372702 Number of compositions of n such that the set of parts is {1,2,3}.

Original entry on oeis.org

6, 12, 32, 72, 152, 311, 625, 1225, 2378, 4566, 8700, 16475, 31052, 58290, 109079, 203584, 379144, 704821, 1308268, 2425259, 4491074, 8308879, 15360082, 28376089, 52391492, 96683649, 178344205, 328854566, 606190627, 1117103729, 2058129088, 3791056189

Offset: 6

John Tyler Rascoe, May 25 2024

Alois P. Heinz, Table of n, a(n) for n = 6..3779

Cf. A048793, A107429, A245738.

Column k=3 of A373118.

b:= proc(n, t) option remember; `if`(n=0, `if`(t=7, 1, 0),
      add(b(n-j, Bits[Or](t, 2^(j-1))), j=1..min(n, 3)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=6..42);  # Alois P. Heinz, May 25 2024

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(h=C_x([1,2,3],n)); Vec(h)}
B_x(40)

G.f.: C({1,2,3},x) = (x^6/(-x^3 - x^2 - x + 1)) *
 (1/((1 - x)*(-x^2 - x + 1)) +
  1/((1 - x)*(-x^3 - x + 1)) +
  1/((1 - x^2)*(-x^2 - x + 1)) +
  1/((1 - x^2)*(-x^3 - x^2 + 1)) +
  1/((1 - x^3)*(-x^3 - x + 1)) +
  1/((1 - x^3)*(-x^3 - x^2 + 1))).
Where C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/(1 - Sum_{i in {s}} (x^i)).

cp's OEIS Frontend

A107429 Number of complete compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A332721 Number of compositions of n^2 with parts <= n, such that each element of [n] is used at least once.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A373306 Sum over all complete compositions of n of the element multiset size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A245738 Number of compositions of n into parts 1 and 2 with both parts present.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

Maple

PARI

Formula

A373305 Sum over all complete compositions of n of the element set cardinality.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A372702 Number of compositions of n such that the set of parts is {1,2,3}.

Views

Author

Keywords

Links

Crossrefs

Programs