login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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, 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.

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. A003242, A008289, A032011, A232432, A261982.

Row sums of A241719.

Column k=1 of A243081, A242447 (for n>0), A261835, A261836 (for n>0).

Main diagonal of A261960.

Sequence in context: A286514 A235859 A279790 * 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 09:37 EDT 2018. Contains 316211 sequences. (Running on oeis4.)