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. 44
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)

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) = {

  my(q = vector(n));

  q[1] = [1, 0, 0, 0];

  for (i = 2, n,

       my(m = floor((sqrt(8*i+1) - 1)/2));

       q[i] = vector((1 + (m>>2)) << 2);

       q[i][1] = 1;

       for (j = 2, m, q[i][j] = q[i-j][j] + q[i-j][j-1]));

  return(q);

};

N = 44;

concat(1, apply(q -> sum(k = 1, #q, q[k] * k!), Q(N)))  \\ Gheorghe Coserea, Nov 21 2015

CROSSREFS

Cf. A003242, 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 A084656 A073749

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 February 18 17:08 EST 2018. Contains 299325 sequences. (Running on oeis4.)