login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032020 Number of compositions (ordered partitions) of n into distinct parts. 135
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

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)

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

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, [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 *)

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] = [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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 4 17:59 EST 2020. Contains 338935 sequences. (Running on oeis4.)