A107429 -id:A107429 - cp's OEIS frontend

A335942 Number of compositions of n such that the set s of parts and multiplicities satisfies s = {1..max(s)}.

1, 1, 2, 2, 3, 12, 12, 32, 51, 144, 191, 486, 679, 1487, 3149, 5909, 11637, 18630, 36928, 76431, 141009, 264784, 535057, 921105, 1774022, 3388054, 6303519, 12255373, 22527578, 43358822, 77695383, 145170435, 264722429, 527776034, 936538336, 1807344134

Offset: 0

Alois P. Heinz, Jun 30 2020

nonn

			a(4) = 3: 211, 121, 112.
a(5) = 12: 23, 32, 113, 122, 131, 212, 221, 311, 1112, 1121, 1211, 2111.

Chai Wah Wu, Table of n, a(n) for n = 0..142 (n = 0..100 from Alois P. Heinz)

Cf. A107429, A329741, A335941.

b:= proc(n, i, s, p) option remember;
     `if`(n=0, `if`(s={$0..max(s)}, p!, 0), `if`(i<1, 0, add(
      b(n-i*j, i-1, {s[], j, `if`(j=0, 0, i)}, p+j)/j!, j=0..n/i)))
    end:
a:= n-> b(n, floor((sqrt(1+8*(n+1))-1)/2), {0}, 0):
seq(a(n), n=0..35);

b[n_, i_, s_, p_] := b[n, i, s, p] =
     If[n == 0, If[s == Range[0, Max[s]], p!, 0], If[i < 1, 0, Sum[
     b[n - i*j, i - 1, Union@Flatten@{s, j, If[j == 0, 0, i]}, p + j]/j!,
     {j, 0, n/i}]]];
a[n_] := b[n, Floor[(Sqrt[1 + 8*(n + 1)] - 1)/2], {0}, 0];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, May 30 2022, after Alois P. Heinz *)

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

Original entry on oeis.org

1, 1, 1, 1, 3, 4, 5, 9, 13, 24, 40, 61, 101, 160, 257, 415, 679, 1103, 1774, 2884, 4656, 7517, 12165, 19653, 31753, 51390, 83134, 134412, 217505, 351814, 569081, 920769, 1489587, 2409992, 3899347, 6309059, 10208628, 16518910, 26729830, 43254212, 69994082

Offset: 0

Gus Wiseman, Aug 30 2022

nonn

			The a(1) = 1 through a(8) = 13 compositions:
  (1)  (11)  (111)  (13)    (113)    (1113)    (133)      (1133)
                    (31)    (131)    (1131)    (313)      (1313)
                    (1111)  (311)    (1311)    (331)      (1331)
                            (11111)  (3111)    (11113)    (3113)
                                     (111111)  (11131)    (3131)
                                               (11311)    (3311)
                                               (13111)    (111113)
                                               (31111)    (111131)
                                               (1111111)  (111311)
                                                          (113111)
                                                          (131111)
                                                          (311111)
                                                          (11111111)
The a(9) = 24 compositions:
  (135)  (11133)  (1111113)  (111111111)
  (153)  (11313)  (1111131)
  (315)  (11331)  (1111311)
  (351)  (13113)  (1113111)
  (513)  (13131)  (1131111)
  (531)  (13311)  (1311111)
         (31113)  (3111111)
         (31131)
         (31311)
         (33111)

The case of partitions is A053251, ranked by A356232 and A356603.
These compositions are ranked by the intersection of A060142 and A333217.
This is the odd initial case of A107428.
This is the odd restriction of A107429.
This is the normal/covering case of A324969 (essentially A000045).
The non-initial version is A356605.
A000041 counts partitions, compositions A011782.
A055932 lists numbers with prime indices covering an initial interval.
A066208 lists numbers with all odd prime indices, counted by A000009.
Cf. A001221, A001222, A001227, A005408, A061395, A066205, A073493, A137921, A356224.

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

More terms from Alois P. Heinz, Sep 01 2022

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

A371293 Numbers whose binary indices have (1) prime indices covering an initial interval and (2) squarefree product.

Original entry on oeis.org

1, 2, 3, 6, 7, 22, 23, 32, 33, 48, 49, 86, 87, 112, 113, 516, 517, 580, 581, 1110, 1111, 1136, 1137, 1604, 1605, 5206, 5207, 5232, 5233, 5700, 5701, 8212, 8213, 9236, 9237, 13332, 13333, 16386, 16387, 16450, 16451, 17474, 17475, 21570, 21571, 24576, 24577

Offset: 1

Gus Wiseman, Mar 28 2024

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 binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The terms together with their prime indices of binary indices begin:
    1: {{}}
    2: {{1}}
    3: {{},{1}}
    6: {{1},{2}}
    7: {{},{1},{2}}
   22: {{1},{2},{3}}
   23: {{},{1},{2},{3}}
   32: {{1,2}}
   33: {{},{1,2}}
   48: {{3},{1,2}}
   49: {{},{3},{1,2}}
   86: {{1},{2},{3},{4}}
   87: {{},{1},{2},{3},{4}}
  112: {{3},{1,2},{4}}
  113: {{},{3},{1,2},{4}}
  516: {{2},{1,3}}
  517: {{},{2},{1,3}}
  580: {{2},{4},{1,3}}
  581: {{},{2},{4},{1,3}}

Without the covering condition we have A371289.
Without squarefree product we have A371292.
Interchanging binary and prime indices gives A371448.
A000009 counts partitions covering initial interval, compositions A107429.
A000670 counts ordered set partitions, allowing empty sets A000629.
A005117 lists squarefree numbers.
A011782 counts multisets covering an initial interval.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A131689 counts patterns by number of distinct parts.
A302521 lists MM-numbers of set partitions, with empties A302505.
A326701 lists BII-numbers of set partitions.
A368533 lists numbers with squarefree binary indices, prime indices A302478.
Cf. A000040, A001222, A255906, A326782, A371291, A371294, A371447, A371452.

normQ[m_]:=m=={}||Union[m]==Range[Max[m]];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[1000],SquareFreeQ[Times @@ bpe[#]]&&normQ[Join@@prix/@bpe[#]]&]

Intersection of A371292 and A371289.

A371448 Numbers such that (1) the product of prime indices is squarefree, and (2) the binary indices of prime indices cover an initial interval of positive integers.

Original entry on oeis.org

1, 2, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 26, 30, 32, 33, 34, 40, 47, 48, 51, 52, 55, 60, 64, 66, 68, 80, 85, 86, 94, 96, 102, 104, 110, 120, 123, 127, 128, 132, 136, 141, 143, 160, 165, 170, 172, 187, 188, 192, 204, 205, 208, 215, 220, 221, 226, 240, 246

Offset: 1

Gus Wiseman, Mar 31 2024

nonn

Also Heinz numbers of integer partitions whose parts have (1) squarefree product and (2) binary indices covering an initial interval.
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
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.

			The terms together with their binary indices of prime indices begin:
   1: {}
   2: {{1}}
   4: {{1},{1}}
   5: {{1,2}}
   6: {{1},{2}}
   8: {{1},{1},{1}}
  10: {{1},{1,2}}
  12: {{1},{1},{2}}
  15: {{2},{1,2}}
  16: {{1},{1},{1},{1}}
  17: {{1,2,3}}
  20: {{1},{1},{1,2}}
  24: {{1},{1},{1},{2}}
  26: {{1},{2,3}}
  30: {{1},{2},{1,2}}
  32: {{1},{1},{1},{1},{1}}
  33: {{2},{1,3}}
  34: {{1},{1,2,3}}
  40: {{1},{1},{1},{1,2}}
  47: {{1,2,3,4}}
  48: {{1},{1},{1},{1},{2}}
  51: {{2},{1,2,3}}

An opposite version is A371293, A371292.
Without the squarefree condition we have A371447, see also A320456, A326754.
The connected components of this multiset system are counted by A371451.
A000009 counts partitions covering initial interval, compositions A107429.
A000670 counts patterns, ranked by A333217.
A011782 counts multisets covering an initial interval.
A048793 lists binary indices, reverse A272020, length A000120, sum A029931.
A070939 gives length of binary expansion.
A112798 lists prime indices, reverse A296150, length A001222, sum A056239.
A131689 counts patterns by number of distinct parts.
Cf. A000040, A000961, A019565, A055887, A255906, A325097, A325118, A326782, A368109, A371452.

normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000], SquareFreeQ[Times@@prix[#]]&&normQ[Join@@bpe/@prix[#]]&]

Intersection of A302505 and A371447.

A374726 Number of gap-free Carlitz compositions of n.

Original entry on oeis.org

1, 1, 3, 2, 4, 9, 11, 11, 29, 53, 82, 129, 215, 389, 726, 1237, 2079, 3660, 6386, 11127, 19719, 34658, 60358, 105776, 185641, 324822, 569565, 999824, 1753763, 3075263, 5390839, 9452903, 16579307, 29065205, 50947822, 89330076, 156628094, 274559046, 481250343

Offset: 1

John Tyler Rascoe, Jul 17 2024

nonn

These are integer compositions such that no adjacent parts are equal and their set of parts covers some interval.

			a(6) = 9 counts: (1,2,1,2), (2,1,2,1), (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (6).

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

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

A383253 Number of compositions of n with parts in standard order.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 16, 29, 53, 98, 182, 340, 638, 1202, 2273, 4312, 8204, 15650, 29925, 57344, 110101, 211771, 407987, 787174, 1520851, 2942030, 5697842, 11046881, 21438881, 41645541, 80967881, 157547508, 306791828, 597847686, 1165828440, 2274890125

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.

			a(6) = 9 counts: (1,1,1,1,1,1), (1,1,1,1,2), (1,1,1,2,1), (1,1,2,1,1), (1,2,1,1,1), (1,1,2,2), (1,2,1,2), (1,2,2,1), (1,2,3).

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

Cf. A000110, A011782, A047998, A107429, A126347, A278984, (row sums of A383713).

b:= proc(n, i) option remember; `if`(n=0, 1, add(
      b(n-j, max(i, j)), j=1..min(n, i+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..36);  # Alois P. Heinz, May 08 2025

A_x(N) = {my(x='x+O('x^(N+1))); Vec(1 + sum(i=1,(N/2)+1, x^(i*(i+1)/2)/prod(j=1,i, 1 - (x-x^(j+1))/(1-x))))}
A_x(40)

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

A329749 Number of complete compositions of n whose run-lengths cover an initial interval of positive integers.

Original entry on oeis.org

1, 1, 0, 2, 3, 5, 11, 23, 40, 80, 180, 344, 661, 1321, 2657, 5268, 10481, 20903, 41572, 82734, 164998, 328304, 654510, 1305421, 2598811, 5182174, 10332978, 20594318, 41066611, 81897091, 163309679, 325707492, 649648912, 1295827380, 2584941276, 5156774487

Offset: 0

Gus Wiseman, Nov 21 2019

nonn

A composition of n is a finite sequence of positive integers with sum n. It is complete if it covers an initial interval of positive integers.

			The a(0) = 1 through a(6) = 11 compositions (empty column not shown):
  ()  (1)  (1,2)  (1,1,2)  (1,2,2)    (1,2,3)
           (2,1)  (1,2,1)  (2,1,2)    (1,3,2)
                  (2,1,1)  (2,2,1)    (2,1,3)
                           (1,1,2,1)  (2,3,1)
                           (1,2,1,1)  (3,1,2)
                                      (3,2,1)
                                      (1,2,1,2)
                                      (1,2,2,1)
                                      (2,1,1,2)
                                      (2,1,2,1)
                                      (1,1,2,1,1)

Looking at  multiplicities instead of run-lengths gives A329748.
The non-complete version is A329766.
Complete compositions are A107429.
Cf. A000740, A008965, A098504, A244164, A274174, A329738, A329739, A329740, A329741, A329744.

normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],normQ[#]&&normQ[Length/@Split[#]]&]],{n,0,10}]

a(21)-a(35) from Alois P. Heinz, Jul 06 2020

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

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

A335942 Number of compositions of n such that the set s of parts and multiplicities satisfies s = {1..max(s)}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A371293 Numbers whose binary indices have (1) prime indices covering an initial interval and (2) squarefree product.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A371448 Numbers such that (1) the product of prime indices is squarefree, and (2) the binary indices of prime indices cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A374726 Number of gap-free Carlitz compositions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A383253 Number of compositions of n with parts in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A329749 Number of complete compositions of n whose run-lengths cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions