A107429 -id:A107429 - cp's OEIS frontend

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

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

A374727 Number of n-color complete compositions of n.

Original entry on oeis.org

1, 1, 1, 1, 7, 13, 45, 91, 233, 477, 1079, 2205, 4709, 10299, 22393, 52005, 125055, 310373, 799677, 2096699, 5556681, 14806685, 39417431, 104570549, 276027337, 724183555, 1887993925, 4891368373, 12595644523, 32252683453, 82146468813, 208225916203, 525472131209

Offset: 1

John Tyler Rascoe, Jul 17 2024

nonn

These are integer compositions whose set of parts covers an initial interval and contains k colors of each part k.

			a(6) = 13 counts: (1,1,1,1,1,1) and the 12 permutations of parts 1, 1, 2_a, and 2_b.

Cf. A003242, A011782, A107428, A107429, A374147, A374726, A374728.

colr(x,y)={my(r=y-x+1, v=[x..y], z = vector(r*(r+(1+(x-1)*2))/2), k=1); for(i=1,#v,for(j=1,v[i],z[k]=v[i]; k++)); return(z)}
C_x(s,N)={my(x='x+O('x^N), g=if(#s <1,1, sum(i=1,#s, C_x(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, s=colr(1,j)); while(vecsum(s) <= N, h += C_x(s,N+1); j++;s=colr(1,j)); my(a = Vec(h)); vector(N, i, a[i])}
B_x(25)

A374728 Number of n-color gap-free compositions of n.

Original entry on oeis.org

1, 1, 1, 3, 7, 19, 45, 105, 239, 507, 1079, 2303, 4829, 10425, 23263, 53363, 127995, 318983, 816057, 2133241, 5640135, 14975051, 39772751, 105322879, 277547989, 727276225, 1894282195, 4903985955, 12621154315, 32302574959, 82248961437, 208426306113, 525884062427

Offset: 1

John Tyler Rascoe, Jul 17 2024

nonn

These are integer compositions whose set of parts covers some interval and contains k colors of each part k.

			a(5) = 7 counts: (1,1,1,1,1), (1,2_a,2_b), (1,2_b,2_a), (2_a,1,2_b), (2_a,2_b,1), (2_b,1,2_a), (2_b,2_a,1).

Cf. A003242, A011782, A107428, A107429, A374147, A374726, A374727.

colr(x,y)={my(r=y-x+1, v=[x..y], z = vector(r*(r+(1+(x-1)*2))/2), k=1); for(i=1,#v,for(j=1,v[i],z[k]=v[i]; k++)); return(z)}
C_x(s,N)={my(x='x+O('x^N), g=if(#s <1,1, sum(i=1,#s, C_x(s[^i],N+1) * x^(s[i]) )/(1-sum(i=1,#s, x^(s[i]))))); return(g)}
B_x(N)={my(x='x+O('x^N), h=0); for(u=1,N, my(j=0); while(vecsum(colr(u,u+j)) <= N, h += C_x(colr(u,u+j),N+1); j++)); my(a = Vec(h)); vector(N, i, a[i])}
B_x(20)

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

A380822 Triangle read by rows: T(n,k) is the number of compositions of n with k pairs of equal adjacent parts and all parts in standard order.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 3, 1, 0, 1, 2, 1, 4, 1, 0, 1, 3, 3, 3, 5, 1, 0, 1, 2, 10, 5, 4, 6, 1, 0, 1, 5, 9, 17, 8, 5, 7, 1, 0, 1, 8, 16, 22, 26, 10, 6, 8, 1, 0, 1, 10, 35, 33, 37, 37, 12, 7, 9, 1, 0, 1, 19, 44, 80, 59, 56, 48, 14, 8, 10, 1, 0, 1

Offset: 1

John Tyler Rascoe, May 08 2025

A composition with parts in standard order satisfies the condition that for any part p > 1, the part p - 1 has already appeared. All compositions of this kind have first part 1.

			Triangle begins:
     k=0   1   2   3   4  5  6  7  8  9
 n=1  [1],
 n=2  [0,  1],
 n=3  [1,  0,  1],
 n=4  [1,  1,  0,  1],
 n=5  [0,  3,  1,  0,  1],
 n=6  [2,  1,  4,  1,  0, 1],
 n=7  [3,  3,  3,  5,  1, 0, 1],
 n=8  [2, 10,  5,  4,  6, 1, 0, 1],
 n=9  [5,  9, 17,  8,  5, 7, 1, 0, 1],
 n=10 [8, 16, 22, 26, 10, 6, 8, 1, 0, 1],
...
Row n = 6 counts:
 T(6,0) = 2: (1,2,1,2), (1,2,3).
 T(6,1) = 1: (1,2,2,1).
 T(6,2) = 4: (1,1,1,2,1), (1,1,2,1,1), (1,1,2,2), (1,2,1,1,1).
 T(6,3) = 1: (1,1,1,1,2).
 T(6,4) = 0: .
 T(6,5) = 1: (1,1,1,1,1,1).

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

Cf. A000110, A003242, A047998, A106356, A107429, A126347, A278984, A383253 (row sums).

b:= proc(n, l, i) option remember; expand(`if`(n=0, 1, add(
      `if`(j=l, x, 1)*b(n-j, j, max(i, j)), j=1..min(n, i+1))))
    end:
T:= (n, k)-> coeff(b(n, 0$2), x, k):
seq(seq(T(n, k), k=0..n-1), n=1..12);  # Alois P. Heinz, May 08 2025

G(k,N) = {my(x='x+O('x^N)); if(k<1,1, G(k-1,N) * x^k * (1 + (1/(1 - sum(j=1,k, x^j/(1-(z-1)*x^j)))) * sum(j=1,k, z^(if(j==k,1,0)) * x^j/(1-(z-1)*x^j))))}
T_xz(max_row) = {my(N = max_row+1, x='x+O('x^N), h = sum(i=1,N/2+1, G(i,N))); vector(N-1, n, Vecrev(polcoeff(h, n)))}
T_xz(10)

G.f.: Sum_{i>0} G(i) where G(k) = G(k-1) * x*k * (1 + 1/(1 - Sum_{j=1..k} ( x^j/(1 - (z-1)*x^j) )) * Sum_{j=1..k} ( z^[j=k] * x^j/(1 - (z-1)*x^j) )) and G(0) = 1.

A383713 Triangle read by rows: T(n,k) is the number of compositions of n with k parts all in standard order.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 3, 4, 1, 0, 0, 0, 0, 4, 6, 5, 1, 0, 0, 0, 0, 2, 10, 10, 6, 1, 0, 0, 0, 0, 1, 9, 20, 15, 7, 1, 0, 0, 0, 0, 1, 7, 25, 35, 21, 8, 1, 0, 0, 0, 0, 0, 7, 26, 55, 56, 28, 9, 1, 0, 0, 0, 0, 0, 4, 29, 71, 105, 84, 36, 10, 1

Offset: 0

John Tyler Rascoe, May 06 2025

A composition with parts in standard order satisfies the condition that for any part p > 1, the part p - 1 has already appeared. All compositions of this kind have first part 1.

			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, 1, 1],
 n=4  [0, 0, 0, 2, 1],
 n=5  [0, 0, 0, 1, 3,  1],
 n=6  [0, 0, 0, 1, 3,  4,  1],
 n=7  [0, 0, 0, 0, 4,  6,  5,  1],
 n=8  [0, 0, 0, 0, 2, 10, 10,  6,  1],
 n=9  [0, 0, 0, 0, 1,  9, 20, 15,  7, 1],
 n=10 [0, 0, 0, 0, 1,  7, 25, 35, 21, 8, 1],
 ...
Row n = 6 counts:
 T(6,3) = 1: (1,2,3).
 T(6,4) = 3: (1,1,2,2), (1,2,1,2), (1,2,2,1).
 T(6,5) = 4: (1,1,1,1,2), (1,1,1,2,1), (1,1,2,1,1), (1,2,1,1,1).
 T(6,6) = 1: (1,1,1,1,1,1).

Cf. A000110 (column sums), A047998, A107429, A126347 (triangle transposed with no zeros), A278984, A383253 (row sums).

T_xy(max_row) = {my(N = max_row+1, x='x+O('x^N), h = 1 + sum(i=1,1+(N/2), y^i * x^(i*(i+1)/2)/prod(j=1,i, 1 - y*(x-x^(j+1))/(1-x)))); vector(N, n, Vecrev(polcoeff(h, n-1)))}
T_xy(10)

G.f.: 1 + Sum_{i>0} y^i * x^(i*(i+1)/2) / Product_{j=1..i} 1 - y*(x - x^(j+1))/(1 - x).

A330937 Number of strictly recursively normal integer partitions of n.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 15, 20, 27, 35, 49, 58, 81, 100, 126, 160, 206, 246, 316, 374, 462, 564, 696, 813, 1006, 1195, 1441, 1701, 2058, 2394, 2896, 3367, 4007, 4670, 5542, 6368, 7540, 8702, 10199, 11734, 13760, 15734, 18384, 21008, 24441, 27893, 32380, 36841

Offset: 0

Gus Wiseman, Mar 09 2020

nonn

A sequence is strictly recursively normal if either it empty, its run-lengths are distinct (strict), or its run-lengths cover an initial interval of positive integers (normal) and are themselves a strictly recursively normal sequence.

			The a(1) = 1 through a(9) = 15 partitions:
  (1)  (2)  (3)   (4)    (5)    (6)    (7)     (8)     (9)
            (21)  (31)   (32)   (42)   (43)    (53)    (54)
                  (211)  (41)   (51)   (52)    (62)    (63)
                         (221)  (321)  (61)    (71)    (72)
                         (311)  (411)  (322)   (332)   (81)
                                       (331)   (422)   (432)
                                       (421)   (431)   (441)
                                       (511)   (521)   (522)
                                       (3211)  (611)   (531)
                                               (3221)  (621)
                                               (4211)  (711)
                                                       (3321)
                                                       (4221)
                                                       (4311)
                                                       (5211)
                                                       (32211)

The narrow instead of strict version is A332272.
A wide instead of strict version is A332295(n) - 1 for n > 1.
Cf. A107429, A181819, A316496, A317081, A317245, A317491, A329744, A329746, A329766, A332277, A332576.

normQ[m_]:=m=={}||Union[m]==Range[Max[m]];
recnQ[ptn_]:=With[{qtn=Length/@Split[ptn]},Or[ptn=={},UnsameQ@@qtn,And[normQ[qtn],recnQ[qtn]]]];
Table[Length[Select[IntegerPartitions[n],recnQ]],{n,0,30}]

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}]

A373196 Maximal coefficient (in absolute value) in the numerator of C({1..n},x).

Original entry on oeis.org

1, 1, 2, 17, 444, 66559954, 14648786369948422, 791540878703169050660325841979096789557779, 1918013047695258943191946313451491492494186620117241479813740479213857275772347178176158

Offset: 0

John Tyler Rascoe, Jun 28 2024

nonn

			C_x({1,2,3},x) = (-x^15 - 5*x^14 - 12*x^13 - 17*x^12 - 11*x^11 + 4*x^10 + 16*x^9 + 10*x^8 - 6*x^6)/(x^15 + 4*x^14 + 7*x^13 + 4*x^12 - 8*x^11 - 18*x^10 - 13*x^9 + 7*x^8 + 19*x^7 + 11*x^6 - 6*x^5 - 10*x^4 - 2*x^3 + 3*x^2 + 2*x - 1) with maximal coefficient abs(-17) in the numerator, so a(3) = 17.

Cf. A107429, A114536, A278567.

C_x(s)={my(g=if(#s <1,1, sum(i=1,#s, C_x(s[^i])*x^(s[i]))/(1-sum(i=1,#s, x^(s[i]))))); return(g)}
a(n)={vecmax(abs(Vec(numerator(C_x([1..n])))))}

C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/(1 - Sum_{i in {s}} (x^i)) with C({},x) = 1.

A376117 Irregular triangle of numerator polynomial coefficients of C({1..n},x), T(n,k) for n >= 0 and k >= A000217(n).

Original entry on oeis.org

1, 1, -2, -1, -6, 0, 10, 16, 4, -11, -17, -12, -5, -1, -24, 84, -60, 30, -144, -48, 104, 186, 268, -12, -240, -436, -348, -46, 262, 444, 391, 199, -23, -166, -207, -172, -109, -55, -21, -6, -1, 120, -1200, 4560, -7740, 5064, -2472, 9768, -19152, 35004, -39408

Offset: 0

John Tyler Rascoe, Sep 10 2024

			For row n = 2, C({1,2},x) = (-2*x^3 - x^4)/(1 + x + 2*x^2 - x^3 - x^4).
Triangle begins
  k=0  1  2  3   4   5   6   7   8   9  10   11   12   13  14  15
n=0 1;
n=1 .  1;
n=2 .  .  . -2, -1;
n=3 .  .  .  .   .   .  -6,  0, 10, 16,  4, -11, -17, -12, -5, -1;

John Tyler Rascoe, Rows n = 0..7, flattened

Cf. A107429, A175669, A196847, A231147, A373196.

C_x(s)={my( g=if(#s <1, 1, sum(i=1, #s, C_x(s[^i]) * x^(s[i]) )/(1-sum(i=1, #s, x^(s[i]))))); return(g)}
A376117_row(n)={my(t=n*(n+1)/2, c=C_x([1..n]), d=poldegree(numerator(c))-t, z=vector(d+1)); for(k=0,d,z[k+1]=polcoeff(numerator(c),k+t)); z}

C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/(1 - Sum_{i in {s}} (x^i)) with C({},x) = 1.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A374727 Number of n-color complete compositions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A374728 Number of n-color gap-free compositions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A380822 Triangle read by rows: T(n,k) is the number of compositions of n with k pairs of equal adjacent parts and all parts in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A383713 Triangle read by rows: T(n,k) is the number of compositions of n with k parts all in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A330937 Number of strictly recursively normal integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica