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
Examples
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)
References
- 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.
Links
- 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.
Crossrefs
Row sums of A241719.
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.
Programs
-
Maple
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 -
Mathematica
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 *) -
PARI
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 */ -
PARI
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
Formula
"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
Comments