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

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