The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A032020 Number of compositions (ordered partitions) of n into distinct parts. 147
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS a(n) = the number of different ways to run up a staircase with n steps, taking steps of distinct sizes where the order matters and there is no other restriction on the number or the size of each step taken. - Mohammad K. Azarian, May 21 2008 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 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 T. D. Noe and 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) 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 EXAMPLE 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) MAPLE b:= proc(n, i) b(n, i):= `if`(n=0, , `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 *) PROG (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, 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;     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 CROSSREFS 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. Sequence in context: A235859 A279790 A338847 * A261962 A301500 A084656 Adjacent sequences:  A032017 A032018 A032019 * A032021 A032022 A032023 KEYWORD nonn,easy,nice AUTHOR Christian G. Bower, Apr 01 1998 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 26 13:40 EDT 2021. Contains 346294 sequences. (Running on oeis4.)