A097910 -id:A097910 - cp's OEIS frontend

A072574 Triangle T(n,k) of number of compositions (ordered partitions) of n into exactly k distinct parts, 1<=k<=n.

1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 1, 4, 0, 0, 0, 1, 4, 6, 0, 0, 0, 1, 6, 6, 0, 0, 0, 0, 1, 6, 12, 0, 0, 0, 0, 0, 1, 8, 18, 0, 0, 0, 0, 0, 0, 1, 8, 24, 24, 0, 0, 0, 0, 0, 0, 1, 10, 30, 24, 0, 0, 0, 0, 0, 0, 0, 1, 10, 42, 48, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 48, 72, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 60, 120, 0

Offset: 1

Henry Bottomley, Jun 21 2002

If terms in the compositions did not need to be distinct then the triangle would have values C(n-1,k-1), essentially A007318 offset.

			T(6,2)=4 since 6 can be written as 1+5=2+4=4+2=5+1.
Triangle starts (trailing zeros omitted for n>=10):
[ 1]  1;
[ 2]  1, 0;
[ 3]  1, 2, 0;
[ 4]  1, 2, 0, 0;
[ 5]  1, 4, 0, 0, 0;
[ 6]  1, 4, 6, 0, 0, 0;
[ 7]  1, 6, 6, 0, 0, 0, 0;
[ 8]  1, 6, 12, 0, 0, 0, 0, 0;
[ 9]  1, 8, 18, 0, 0, 0, 0, 0, 0;
[10]  1, 8, 24, 24, 0, 0, ...;
[11]  1, 10, 30, 24, 0, 0, ...;
[12]  1, 10, 42, 48, 0, 0, ...;
[13]  1, 12, 48, 72, 0, 0, ...;
[14]  1, 12, 60, 120, 0, 0, ...;
[15]  1, 14, 72, 144, 120, 0, 0, ...;
[16]  1, 14, 84, 216, 120, 0, 0, ...;
[17]  1, 16, 96, 264, 240, 0, 0, ...;
[18]  1, 16, 114, 360, 360, 0, 0, ...;
[19]  1, 18, 126, 432, 600, 0, 0, ...;
[20]  1, 18, 144, 552, 840, 0, 0, ...;
These rows (without the zeros) are shown in the Richmond/Knopfmacher reference.
From _Gus Wiseman_, Oct 17 2022: (Start)
Column n = 8 counts the following compositions.
  (8)  (1,7)  (1,2,5)
       (2,6)  (1,3,4)
       (3,5)  (1,4,3)
       (5,3)  (1,5,2)
       (6,2)  (2,1,5)
       (7,1)  (2,5,1)
              (3,1,4)
              (3,4,1)
              (4,1,3)
              (4,3,1)
              (5,1,2)
              (5,2,1)
(End)

Joerg Arndt, Table of n, a(n) for n = 1..5050 (rows 1..100, flattened).
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97.
Index entries for sequences related to compositions

Columns (offset) include A057427 and A052928.
Row sums are A032020.
Cf. A060016, A072576.
A008289 is the version for partitions (zeros removed).
A072575 counts strict compositions by maximum.
A097805 is the non-strict version, or A007318 (zeros removed).
A113704 is the constant instead of strict version.
A216652 is a condensed version (zeros removed).
A336131 counts splittings of partitions with distinct sums.
A336139 counts strict compositions of each part of a strict composition.
Cf. A075900, A097910, A307068, A336127, A336128, A336130, A336132, A336141, A336142, A336342, A336343.

Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&],Length[#]==k&]],{n,0,15},{k,1,n}] (* Gus Wiseman, Oct 17 2022 *)

N=21;  q='q+O('q^N);
gf=sum(n=0,N, n! * z^n * q^((n^2+n)/2) / prod(k=1,n, 1-q^k ) );
/* print triangle: */
gf -= 1; /* remove row zero */
P=Pol(gf,'q);
{ for (n=1,N-1,
    p = Pol(polcoeff(P, n),'z);
    p += 'z^(n+1);  /* preserve trailing zeros */
    v = Vec(polrecip(p));
    v = vector(n,k,v[k]); /* trim to size n */
    print(v);
); }
/* Joerg Arndt, Oct 20 2012 */

T(n, k) = T(n-k, k)+k*T(n-k, k-1) [with T(n, 0)=1 if n=0 and 0 otherwise] = A000142(k)*A060016(n, k).

G.f.: sum(n>=0, n! * z^n * q^((n^2+n)/2) / prod(k=1..n, 1-q^k ) ), rows by powers of q, columns by powers of z; includes row 0 (drop term for n=0 for this triangle, see PARI code); setting z=1 gives g.f. for A032020. [Joerg Arndt, Oct 20 2012]

A216652 Triangular array read by rows: T(n,k) is the number of compositions of n into exactly k distinct parts.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 1, 4, 6, 1, 6, 6, 1, 6, 12, 1, 8, 18, 1, 8, 24, 24, 1, 10, 30, 24, 1, 10, 42, 48, 1, 12, 48, 72, 1, 12, 60, 120, 1, 14, 72, 144, 120, 1, 14, 84, 216, 120, 1, 16, 96, 264, 240, 1, 16, 114, 360, 360, 1, 18, 126, 432, 600, 1, 18, 144, 552, 840

Offset: 1

Geoffrey Critzer, Sep 12 2012

Same as A072574, with zeros dropped. [Joerg Arndt, Oct 20 2012]
Row sums = A032020.
Row n contains A003056(n) = floor((sqrt(8*n+1)-1)/2) terms (number of terms increases by one at each triangular number).

			Triangle starts:
[ 1]  1;
[ 2]  1;
[ 3]  1, 2;
[ 4]  1, 2;
[ 5]  1, 4;
[ 6]  1, 4, 6;
[ 7]  1, 6, 6;
[ 8]  1, 6, 12;
[ 9]  1, 8, 18;
[10]  1, 8, 24, 24;
[11]  1, 10, 30, 24;
[12]  1, 10, 42, 48;
[13]  1, 12, 48, 72;
[14]  1, 12, 60, 120;
[15]  1, 14, 72, 144, 120;
[16]  1, 14, 84, 216, 120;
[17]  1, 16, 96, 264, 240;
[18]  1, 16, 114, 360, 360;
[19]  1, 18, 126, 432, 600;
[20]  1, 18, 144, 552, 840;
T(5,2) = 4 because we have: 4+1, 1+4, 3+2, 2+3.

Alois P. Heinz, Rows n = 1..500, flattened
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97.

Cf. A003056, A008289, A072574, A097910.

b:= proc(n, k) option remember; `if`(n<0, 0, `if`(n=0, 1,
      `if`(k<1, 0, b(n, k-1) +b(n-k, k))))
    end:
T:= (n, k)-> b(n-k*(k+1)/2, k)*k!:
seq(seq(T(n, k), k=1..floor((sqrt(8*n+1)-1)/2)), n=1..24);  # Alois P. Heinz, Sep 12 2012

nn=20;f[list_]:=Select[list,#>0&];Map[f,Drop[CoefficientList[Series[ Sum[Product[j y x^j/(1-x^j),{j,1,k}],{k,0,nn}],{x,0,nn}],{x,y}],1]]//Flatten

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

T(n,k) = A008289(n,k)*k!.

A336875 Number of parts, counted without multiplicity, in all compositions of n.

Original entry on oeis.org

0, 1, 2, 6, 13, 30, 66, 144, 308, 655, 1380, 2891, 6024, 12500, 25844, 53274, 109530, 224690, 460033, 940276, 1918979, 3911186, 7962194, 16191875, 32896364, 66776727, 135445212, 274532607, 556086916, 1125727954, 2277650681, 4605981879, 9310120876, 18810538092

Offset: 0

Alois P. Heinz, Aug 06 2020

nonn

			a(4) = 1 + 2 + 2 + 2 + 1 + 2 + 2 + 1 = 13: (1)111, (1)1(2), (1)(2)1, (2)(1)1, (2)2, (1)(3), (3)(1), (4).

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

Cf. A000070 (the same for partitions), A001792 (all parts), A097910, A336516.

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

b[n_, i_, p_] := b[n, i, p] = If[n == 0, {p!, 0},
     If[i<1, {0, 0}, Sum[{0, If[j == 0, 0, #[[1]]]}+#&[
     b[n-i*j, i-1, p+j]/j!], {j, 0, n/i}]]];
a[n_] := b[n, n, 0][[2]];
a /@ Range[0, 38] (* Jean-François Alcover, Jun 13 2021, after Alois P. Heinz *)

A339351 Irregular triangle read by rows in which row n lists the compositions (ordered partitions) of n into distinct parts in lexicographic order.

Original entry on oeis.org

1, 2, 1, 2, 2, 1, 3, 1, 3, 3, 1, 4, 1, 4, 2, 3, 3, 2, 4, 1, 5, 1, 2, 3, 1, 3, 2, 1, 5, 2, 1, 3, 2, 3, 1, 2, 4, 3, 1, 2, 3, 2, 1, 4, 2, 5, 1, 6, 1, 2, 4, 1, 4, 2, 1, 6, 2, 1, 4, 2, 4, 1, 2, 5, 3, 4, 4, 1, 2, 4, 2, 1, 4, 3, 5, 2, 6, 1, 7, 1, 2, 5, 1, 3, 4, 1, 4, 3, 1, 5, 2, 1, 7, 2, 1, 5, 2, 5, 1, 2, 6, 3, 1, 4, 3, 4, 1, 3, 5, 4, 1, 3, 4, 3, 1, 5, 1, 2, 5, 2, 1, 5, 3, 6, 2, 7, 1, 8

Offset: 1

Ilya Gutkovskiy, Dec 01 2020

			Triangle begins:
[1],
[2],
[1, 2], [2, 1], [3],
[1, 3], [3, 1], [4],
[1, 4], [2, 3], [3, 2], [4, 1], [5],
...

Index entries for sequences related to compositions

Cf. A026793, A066099, A097910 (row lengths), A118457, A228369, A246688, A304797 (row sums), A339178.

Table[Sort[Join @@ Permutations /@ Select[IntegerPartitions[n], UnsameQ @@ # &], OrderedQ[PadRight[{#1, #2}]] &], {n, 8}] // Flatten

A304797 Expansion of x * (d/dx) Sum_{k>=0} k!x^(k(k+1)/2)/Product_{j=1..k} (1 - x^j).

Original entry on oeis.org

0, 1, 2, 9, 12, 25, 66, 91, 152, 243, 570, 715, 1212, 1729, 2702, 5265, 6960, 10489, 15318, 22363, 31100, 57771, 72534, 109411, 151032, 219025, 293930, 421281, 680820, 883369, 1256010, 1727971, 2396000, 3235419, 4447506, 5894875, 9266580, 11691001, 16380470, 21774753

Offset: 0

Ilya Gutkovskiy, May 18 2018

nonn

Sum of all parts of all compositions (ordered partitions) of n into distinct parts.

Index entries for sequences related to compositions

Cf. A001787, A032020, A066186, A066189, A097910, A303664.

b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
     `if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))
    end:
a:= n-> n*add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..50);  # Alois P. Heinz, May 18 2018

nmax = 39; CoefficientList[Series[x D[Sum[k! x^(k (k + 1)/2)/Product[1 - x^j, {j, 1, k}], {k, 0, nmax}], x], {x, 0, nmax}], x]

a(n) = n*A032020(n).

A097936 Total number of parts in all compositions of n into distinct odd parts.

Original entry on oeis.org

1, 0, 1, 4, 1, 4, 1, 8, 19, 8, 19, 12, 37, 12, 55, 112, 73, 112, 91, 212, 127, 308, 145, 504, 781, 600, 817, 892, 1453, 1084, 2089, 1472, 3343, 1760, 4579, 6564, 6433, 6948, 8287, 11944, 11341, 16744, 14395, 26156, 18667, 35468, 22921, 53712, 64273, 67440

Offset: 1

Vladeta Jovovic, Sep 05 2004

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

Cf. A097910, A079499, A032021.

b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(n>(i+1)^2/4, [][], zip((x, y)->x+y, [b(n, i-2)],
      `if`(i>n, [], [0, b(n-i, i-2)]), 0)[]))
    end:
a:= proc(n) option remember; local l; l:=[b(n, n-1+irem(n,2))];
      add(i*l[i+1]*i!, i=1..nops(l)-1)
    end:
seq (a(n), n=1..60);  # Alois P. Heinz, Nov 20 2012

Drop[ CoefficientList[ Series[Sum[k*k!*x^k^2/Product[1 - x^(2j), {j, 1, k}], {k, 1, 55}], {x, 0, 50}], x], 1] (* Robert G. Wilson v, Sep 08 2004 *)

Sum_{k>0} (k*k!*x^(k^2)/Product_{j=1..k} (1-x^(2*j))).

More terms from Robert G. Wilson v, Sep 08 2004

A339178 Irregular triangle read by rows in which row n lists the compositions (ordered partitions) of n into distinct parts in reverse lexicographic order.

Original entry on oeis.org

1, 2, 3, 2, 1, 1, 2, 4, 3, 1, 1, 3, 5, 4, 1, 3, 2, 2, 3, 1, 4, 6, 5, 1, 4, 2, 3, 2, 1, 3, 1, 2, 2, 4, 2, 3, 1, 2, 1, 3, 1, 5, 1, 3, 2, 1, 2, 3, 7, 6, 1, 5, 2, 4, 3, 4, 2, 1, 4, 1, 2, 3, 4, 2, 5, 2, 4, 1, 2, 1, 4, 1, 6, 1, 4, 2, 1, 2, 4, 8, 7, 1, 6, 2, 5, 3, 5, 2, 1, 5, 1, 2, 4, 3, 1, 4, 1, 3, 3, 5, 3, 4, 1, 3, 1, 4, 2, 6, 2, 5, 1, 2, 1, 5, 1, 7, 1, 5, 2, 1, 4, 3, 1, 3, 4, 1, 2, 5

Offset: 1

Ilya Gutkovskiy, Nov 26 2020

			Triangle begins:
[1],
[2],
[3], [2, 1], [1, 2],
[4], [3, 1], [1, 3],
[5], [4, 1], [3, 2], [2, 3], [1, 4],
...

Index entries for sequences related to compositions

Cf. A026793, A066099, A097910 (row lengths), A118457, A228369, A246688, A304797 (row sums).

Table[Sort[Join @@ Permutations /@ Select[IntegerPartitions[n], UnsameQ @@ # &], OrderedQ[PadRight[{#2, #1}]] &], {n, 8}] // Flatten

cp's OEIS Frontend

A072574 Triangle T(n,k) of number of compositions (ordered partitions) of n into exactly k distinct parts, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A216652 Triangular array read by rows: T(n,k) is the number of compositions of n into exactly k distinct parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A336875 Number of parts, counted without multiplicity, in all compositions of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A339351 Irregular triangle read by rows in which row n lists the compositions (ordered partitions) of n into distinct parts in lexicographic order.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A304797 Expansion of x * (d/dx) Sum_{k>=0} k!*x^(k*(k+1)/2)/Product_{j=1..k} (1 - x^j).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A097936 Total number of parts in all compositions of n into distinct odd parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A339178 Irregular triangle read by rows in which row n lists the compositions (ordered partitions) of n into distinct parts in reverse lexicographic order.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A304797 Expansion of x * (d/dx) Sum_{k>=0} k!x^(k(k+1)/2)/Product_{j=1..k} (1 - x^j).