A261836 -id:A261836 - cp's OEIS frontend

A032020 Number of compositions (ordered partitions) of n into distinct parts.

1, 1, 1, 3, 3, 5, 11, 13, 19, 27, 57, 65, 101, 133, 193, 351, 435, 617, 851, 1177, 1555, 2751, 3297, 4757, 6293, 8761, 11305, 15603, 24315, 30461, 41867, 55741, 74875, 98043, 130809, 168425, 257405, 315973, 431065, 558327, 751491, 958265, 1277867, 1621273

Offset: 0

Christian G. Bower, Apr 01 1998

Compositions into distinct parts are equivalent to (1,1)-avoiding compositions. - Gus Wiseman, Jun 25 2020

All terms are odd. - Alois P. Heinz, Apr 09 2021

			a(6) = 11 because 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.
From _Gus Wiseman_, Jun 25 2020: (Start)
The a(0) = 1 through a(7) = 13 strict compositions:
  ()  (1)  (2)  (3)    (4)    (5)    (6)      (7)
                (1,2)  (1,3)  (1,4)  (1,5)    (1,6)
                (2,1)  (3,1)  (2,3)  (2,4)    (2,5)
                              (3,2)  (4,2)    (3,4)
                              (4,1)  (5,1)    (4,3)
                                     (1,2,3)  (5,2)
                                     (1,3,2)  (6,1)
                                     (2,1,3)  (1,2,4)
                                     (2,3,1)  (1,4,2)
                                     (3,1,2)  (2,1,4)
                                     (3,2,1)  (2,4,1)
                                              (4,1,2)
                                              (4,2,1)
(End)

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
C. G. Bower, Transforms (2)
Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97.
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97. (free access)
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Cf. A008289, A032011.
Row sums of A241719.
Column k=1 of A243081, A242447, A261835, A261836, A327244, A327245.
Main diagonal of A261960.
Dominated by A003242 (anti-run compositions).
These compositions are ranked by A233564.
(1,1)-avoiding patterns are counted by A000142.
Numbers with strict prime signature are A130091.
(1,1,1)-avoiding compositions are counted by A232432.
(1,1)-matching compositions are counted by A261982.
Inseparable partitions are counted by A325535.
Patterns matched by compositions are counted by A335456.
Strict permutations of prime indices are counted by A335489.
Cf. A000009, A011782, A102726, A181796, A261962, A333489, A335457.

b:= proc(n, i) b(n, i):= `if`(n=0, [1], `if`(i<1, [], zip((x, y)
      -> x+y, b(n, i-1), `if`(i>n, [], [0, b(n-i, i-1)[]]), 0))) end:
a:= proc(n) local l; l:=b(n, n): add((i-1)! *l[i], i=1..nops(l)) end:
seq(a(n), n=0..50);  # Alois P. Heinz, Dec 12 2012
# second Maple program:
T:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), T(n-k, k) +k*T(n-k, k-1)))
    end:
a:= n-> add(T(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..60);  # Alois P. Heinz, Sep 04 2015

f[list_]:=Length[list]!; Table[Total[Map[f, Select[IntegerPartitions[n], Sort[#] == Union[#] &]]], {n, 0,30}]
T[n_, k_] := T[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], T[n-k, k] + k*T[n-k, k-1]]]; a[n_] := Sum[T[n, k], {k, 0, Floor[(Sqrt[8*n + 1] - 1) / 2]}]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Sep 22 2015, after Alois P. Heinz *)

N=66;  q='q+O('q^N);
gf=sum(n=0,N, n!*q^(n*(n+1)/2) / prod(k=1,n, 1-q^k ) );
Vec(gf)
/* Joerg Arndt, Oct 20 2012 */

Q(N) = { \\ A008289
  my(q = vector(N)); q[1] = [1, 0, 0, 0];
  for (n = 2, N,
    my(m = (sqrtint(8*n+1) - 1)\2);
    q[n] = vector((1 + (m>>2)) << 2); q[n][1] = 1;
    for (k = 2, m, q[n][k] = q[n-k][k] + q[n-k][k-1]));
  return(q);
};
seq(N) = concat(1, apply(q -> sum(k = 1, #q, q[k] * k!), Q(N)));
seq(43) \\ Gheorghe Coserea, Sep 09 2018

"AGK" (ordered, elements, unlabeled) transform of 1, 1, 1, 1, ...
G.f.: Sum_{k>=0} k! * x^((k^2+k)/2) / Product_{j=1..k} (1-x^j). - David W. Wilson May 04 2000
a(n) = Sum_{m=1..n} A008289(n,m)*m!. - Geoffrey Critzer, Sep 07 2012

A032011 Partition n labeled elements into sets of different sizes and order the sets.

Original entry on oeis.org

1, 1, 1, 7, 9, 31, 403, 757, 2873, 12607, 333051, 761377, 3699435, 16383121, 108710085, 4855474267, 13594184793, 76375572751, 388660153867, 2504206435681, 20148774553859, 1556349601444477, 5050276538344665, 33326552998257031, 186169293932977115, 1305062351972825281, 9600936552132048553, 106019265737746665727, 12708226588208611056333, 47376365554715905155127

Offset: 0

Christian G. Bower, Apr 01 1998

nonn

From Alois P. Heinz, Sep 02 2015: (Start)
Also the number of matrices with n rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.  Equivalently, the number of compositions of n into distinct parts where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order and all n letters occur exactly once.
a(3) = 7:
[1]   [1 0]  [0 1]  [1 0]  [0 1]  [0 1]  [1 0]
[1]   [1 0]  [0 1]  [0 1]  [1 0]  [1 0]  [0 1]
[1]   [0 1]  [1 0]  [1 0]  [0 1]  [1 0]  [0 1].
3abc, 2ab1c, 1c2ab, 2ac1b, 1b2ac, 2bc1a, 1a2bc.  (End)

Alois P. Heinz, Table of n, a(n) for n = 0..670
C. G. Bower, Transforms (2)

Cf. A000670, A007837, A032020, A114902, A120774, A131632.

Main diagonal of A261836 and A261959.

b:= proc(n, i, p) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(n,i))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 02 2015

f[list_]:=Apply[Multinomial,list]*Length[list]!; Table[Total[Map[f, Select[IntegerPartitions[n], Sort[#] == Union[#] &]]], {n, 1, 30}]
b[n_, i_, p_] := b[n, i, p] = If[i*(i+1)/2n, 0, b[n-i, i-1, p+1]*Binomial[n, i]]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 16 2015, after Alois P. Heinz *)

seq(n)=[subst(serlaplace(y^0*p),y,1) | p <- Vec(serlaplace(prod(k=1, n, 1 + x^k*y/k! + O(x*x^n))))] \\ Andrew Howroyd, Sep 13 2018

"AGJ" (ordered, elements, labeled) transform of 1, 1, 1, 1, ...

a(n) = Sum_{k>=0} k! * A131632(n,k). - Alois P. Heinz, Sep 09 2015

a(0)=1 prepended by Alois P. Heinz, Sep 02 2015

A261835 Number A(n,k) of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 3, 0, 1, 4, 6, 16, 3, 0, 1, 5, 10, 46, 21, 5, 0, 1, 6, 15, 100, 75, 50, 11, 0, 1, 7, 21, 185, 195, 231, 205, 13, 0, 1, 8, 28, 308, 420, 736, 1414, 292, 19, 0, 1, 9, 36, 476, 798, 1876, 6032, 2376, 587, 27, 0

Offset: 0

Alois P. Heinz, Sep 02 2015

Also matrices with k rows of nonnegative integers with distinct positive column sums and total element sum n.
A(2,2) = 3: (matrices and corresponding marked compositions are given)
  [1]   [2]   [0]
  [1]   [0]   [2]
  2ab,  2aa,  2bb.

			A(3,2) = 16: 3aaa, 3aab, 3abb, 3bbb, 2aa1a, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 2bb1b, 1a2aa, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1b2bb.
Square array A(n,k) begins:
  1,  1,   1,    1,     1,     1,      1,      1, ...
  0,  1,   2,    3,     4,     5,      6,      7, ...
  0,  1,   3,    6,    10,    15,     21,     28, ...
  0,  3,  16,   46,   100,   185,    308,    476, ...
  0,  3,  21,   75,   195,   420,    798,   1386, ...
  0,  5,  50,  231,   736,  1876,   4116,   8106, ...
  0, 11, 205, 1414,  6032, 19320,  51114, 117936, ...
  0, 13, 292, 2376, 11712, 42610, 126288, 322764, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-10 give: A000007, A032020, A261840, A261841, A261842, A261843, A261844, A261845, A261846, A261847, A261848.
Rows n=0-4 give: A000012, A001477, A000217, A255211, A228317(n+2).
Main diagonal gives A261837.
Cf. A261780, A261836.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
A:= (n, k)-> b(n$2, 0, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2 < n, 0, If[n == 0, p!, b[n, i-1, p, k] + If[i>n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; A[n_, k_] := b[n, n, 0, k]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 16 2017, translated from Maple *)

A(n,k) = Sum_{i=0..k} C(k,i) * A261836(n,k-i).

A261828 Number of compositions of 2n into distinct parts where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order and all n letters occur at least once in the composition.

Original entry on oeis.org

1, 1, 15, 832, 14791, 2008546, 55380132, 2868333476, 511805155863, 31512728488918, 2638310862477610, 926651539894899446, 74254761492776175196, 6851495812540548188072, 9541620342114654822145972, 611287722968440282212322702, 58354641005988089624088037623

Offset: 0

Alois P. Heinz, Sep 02 2015

nonn

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

Cf. A261784, A261836.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
a:= n-> add(b(2*n$2, 0, n-i)*(-1)^i*binomial(n, i), i=0..n):
seq(a(n), n=0..20);

b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; a[n_] := Sum[b[2*n, 2*n, 0, n-i]*(-1)^i*Binomial[n, i], {i, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 25 2017, translated from Maple *)

a(n) = A261836(2n,n).

A261838 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet (k=1,2,3,...) whose letters appear in alphabetical order and all k letters occur at least once in the composition.

Original entry on oeis.org

1, 1, 2, 20, 48, 264, 4296, 14528, 89472, 593248, 19115360, 75604544, 599169408, 4141674240, 40147321344, 2159264715776, 10240251475456, 92926573965184, 746025520714112, 7285397378650112, 82900557619046912, 7796186873306241024, 41825012467664893440

Offset: 0

Alois P. Heinz, Sep 02 2015

nonn

Also number of matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n and the column sums are distinct.
a(2) = 2:
[1]   [2]
[1]

			a(0) = 1: the empty composition.
a(1) = 1: 1a.
a(2) = 2: 2aa (for k=1), 2ab (for k=2).

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

Row sums of A261836.

Cf. A120733.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
a:= n-> add(add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k), k=0..n):
seq(a(n), n=0..25);

b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2 < n, 0, If[n == 0, p!, b[n, i-1, p, k] + If[i>n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; a[n_] := Sum[b[n, n, 0, k-i]*(-1)^i*Binomial[k, i], {k, 0, n}, {i, 0, k}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 25 2017, translated from Maple *)

A261858 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a septenary alphabet whose letters appear in alphabetical order and all letters occur at least once in the composition.

Original entry on oeis.org

757, 13671, 148638, 5623044, 19334910, 115231480, 522931570, 2868333476, 63481817735, 156363633615, 661651830728, 2317522429544, 8940138012274, 34465610055870, 703252581037436, 1456494080466446, 5428978793488341, 16082092961535517, 53836540488601696

Offset: 7

Alois P. Heinz, Sep 03 2015

nonn

Also number of matrices with seven rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.

Alois P. Heinz, Table of n, a(n) for n = 7..2500

Column k=7 of A261836.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
a:= n->(k->add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k))(7):
seq(a(n), n=7..30);

a(n) = A261836(n,7).

A261853 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a binary alphabet whose letters appear in alphabetical order and all letters occur at least once in the composition.

Original entry on oeis.org

1, 10, 15, 40, 183, 266, 549, 1056, 4421, 5850, 12245, 20644, 39809, 141818, 195421, 370808, 633379, 1126518, 1870135, 6531964, 8547045, 16324018, 26458275, 46612364, 73200021, 127916094, 385244951, 518151276, 939317459, 1516648678, 2564211485, 4008404972

Offset: 2

Alois P. Heinz, Sep 03 2015

nonn

Also number of matrices with two rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.

Alois P. Heinz, Table of n, a(n) for n = 2..2500

Column k=2 of A261836.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
a:= n->(k->add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k))(2):
seq(a(n), n=2..40);

a(n) = A261836(n,2).

A261854 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a ternary alphabet whose letters appear in alphabetical order and all letters occur at least once in the composition.

Original entry on oeis.org

7, 21, 96, 832, 1539, 4281, 10902, 76020, 117585, 306639, 634686, 1537206, 9013319, 13793487, 32005392, 64458596, 138068775, 278292429, 1622912266, 2321086080, 5318890971, 10014128239, 20784037248, 38209197732, 80154402633, 415073903937, 593664848658

Offset: 3

Alois P. Heinz, Sep 03 2015

nonn

Also number of matrices with three rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.

Alois P. Heinz, Table of n, a(n) for n = 3..2500

Column k=3 of A261836.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
a:= n->(k->add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k))(3):
seq(a(n), n=3..40);

a(n) = A261836(n,3):

A261855 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a quaternary alphabet whose letters appear in alphabetical order and all letters occur at least once in the composition.

Original entry on oeis.org

9, 92, 1562, 3908, 14791, 50208, 540552, 987120, 3138143, 7862580, 23436690, 204455140, 349297653, 956040232, 2228084512, 5599922904, 13449425997, 116772809532, 182990434794, 483410072060, 1033025269277, 2455590595520, 5184309618676, 12755194552152

Offset: 4

Alois P. Heinz, Sep 03 2015

nonn

Also number of matrices with four rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.

Alois P. Heinz, Table of n, a(n) for n = 4..2500

Column k=4 of A261836.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
a:= n->(k->add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k))(4):
seq(a(n), n=4..40);

a(n) = A261836(n,4).

A261856 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a quinary alphabet whose letters appear in alphabetical order and all letters occur at least once in the composition.

Original entry on oeis.org

31, 1305, 4955, 26765, 124450, 2008546, 4399870, 17016950, 51516925, 187653115, 2298210803, 4405690315, 14002637160, 37448507530, 109070884580, 308549728478, 3711879979775, 6377942356265, 19056675979455, 45667548869495, 122550455798230, 293681447602030

Offset: 5

Alois P. Heinz, Sep 03 2015

nonn

Also number of matrices with five rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.

Alois P. Heinz, Table of n, a(n) for n = 5..2500

Column k=5 of A261836.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
a:= n->(k->add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k))(5):
seq(a(n), n=5..30);

a(n) = A261836(n,5).

cp's OEIS Frontend

A032020 Number of compositions (ordered partitions) of n into distinct parts.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A032011 Partition n labeled elements into sets of different sizes and order the sets.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A261835 Number A(n,k) of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A261828 Number of compositions of 2n into distinct parts where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order and all n letters occur at least once in the composition.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A261838 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet (k=1,2,3,...) whose letters appear in alphabetical order and all k letters occur at least once in the composition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A261858 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a septenary alphabet whose letters appear in alphabetical order and all letters occur at least once in the composition.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A261853 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a binary alphabet whose letters appear in alphabetical order and all letters occur at least once in the composition.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs