A228369 - OEIS

%I #70 Dec 14 2017 09:23:16

%S 1,1,1,2,1,1,1,1,2,2,1,3,1,1,1,1,1,1,2,1,2,1,1,3,2,1,1,2,2,3,1,4,1,1,

%T 1,1,1,1,1,1,2,1,1,2,1,1,1,3,1,2,1,1,1,2,2,1,3,1,1,4,2,1,1,1,2,1,2,2,

%U 2,1,2,3,3,1,1,3,2,4,1,5,1,1,1,1,1,1

%N Triangle read by rows in which row n lists the compositions (ordered partitions) of n in lexicographic order.

%C The representation of the compositions (for fixed n) is as lists of parts, the order between individual compositions (for the same n) is lexicographic. - _Joerg Arndt_, Sep 02 2013

%C The equivalent sequence for partitions is A026791.

%C Row n has length A001792(n-1).

%C Row sums give A001787, n >= 1.

%C The m-th composition has length A008687(m+1), m >= 1. - _Andrey Zabolotskiy_, Jul 19 2017

%H Joerg Arndt, <a href="/A228369/b228369.txt">Table of n, a(n) for n = 1..10000</a>

%e Illustration of initial terms:

%e -----------------------------------

%e n  j       Diagram   Composition j

%e -----------------------------------

%e .               _

%e 1  1           |_|   1;

%e .             _ _

%e 2  1         | |_|   1, 1,

%e 2  2         |_ _|   2;

%e .           _ _ _

%e 3  1       | | |_|   1, 1, 1,

%e 3  2       | |_ _|   1, 2,

%e 3  3       |   |_|   2, 1,

%e 3  4       |_ _ _|   3;

%e .         _ _ _ _

%e 4  1     | | | |_|   1, 1, 1, 1,

%e 4  2     | | |_ _|   1, 1, 2,

%e 4  3     | |   |_|   1, 2, 1,

%e 4  4     | |_ _ _|   1, 3,

%e 4  5     |   | |_|   2, 1, 1,

%e 4  6     |   |_ _|   2, 2,

%e 4  7     |     |_|   3, 1,

%e 4  8     |_ _ _ _|   4;

%e .

%e Triangle begins:

%e [1];

%e [1,1],[2];

%e [1,1,1],[1,2],[2,1],[3];

%e [1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4];

%e [1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,3],[1,2,1,1],[1,2,2],[1,3,1],[1,4],[2,1,1,1],[2,1,2],[2,2,1],[2,3],[3,1,1],[3,2],[4,1],[5];

%e ...

%t Table[Sort[Join@@Permutations/@IntegerPartitions[n],OrderedQ[PadRight[{#1,#2}]]&],{n,5}] (* _Gus Wiseman_, Dec 14 2017 *)

%o (PARI)

%o gen_comp(n)=

%o {  /* Generate compositions of n as lists of parts (order is lex): */

%o     my(ct = 0);

%o     my(m, z, pt);

%o     \\ init:

%o     my( a = vector(n, j, 1) );

%o     m = n;

%o     while ( 1,

%o         ct += 1;

%o         pt = vector(m, j, a[j]);

%o         /* for A228369  print composition: */

%o         for (j=1, m, print1(pt[j],", ") );

%o \\        /* for A228525 print reversed (order is colex): */

%o \\        forstep (j=m, 1, -1, print1(pt[j],", ") );

%o         if ( m<=1,  return(ct) );  \\ current is last

%o         a[m-1] += 1;

%o         z = a[m] - 2;

%o         a[m] = 1;

%o         m += z;

%o     );

%o     return(ct);

%o }

%o for(n=1, 12, gen_comp(n) );

%o \\ _Joerg Arndt_, Sep 02 2013

%o (Haskell)

%o a228369 n = a228369_list !! (n - 1)

%o a228369_list = concatMap a228369_row [1..]

%o a228369_row 0 = []

%o a228369_row n

%o   | 2^k == 2 * n + 2 = [k - 1]

%o   | otherwise        = a228369_row (n `div` 2^k) ++ [k] where

%o     k = a007814 (n + 1) + 1

%o -- _Peter Kagey_, Jun 27 2016

%o (Python)

%o a = [[[]], [[1]]]

%o for s in range(2, 9):

%o     a.append([])

%o     for k in range(1, s+1):

%o         for ss in a[s-k]:

%o             a[-1].append([k]+ss)

%o print(a)

%o # _Andrey Zabolotskiy_, Jul 19 2017

%Y Cf. A001511, A026791, A066099, A101211, A124734, A228351, A228525, A281013.

%K nonn,tabf

%O 1,4

%A _Omar E. Pol_, Aug 28 2013