cp's OEIS Frontend

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

%I A228369 #70 Dec 14 2017 09:23:16
%S A228369 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 A228369 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 A228369 2,1,2,3,3,1,1,3,2,4,1,5,1,1,1,1,1,1
%N A228369 Triangle read by rows in which row n lists the compositions (ordered partitions) of n in lexicographic order.
%C A228369 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 A228369 The equivalent sequence for partitions is A026791.
%C A228369 Row n has length A001792(n-1).
%C A228369 Row sums give A001787, n >= 1.
%C A228369 The m-th composition has length A008687(m+1), m >= 1. - _Andrey Zabolotskiy_, Jul 19 2017
%H A228369 Joerg Arndt, <a href="/A228369/b228369.txt">Table of n, a(n) for n = 1..10000</a>
%e A228369 Illustration of initial terms:
%e A228369 -----------------------------------
%e A228369 n  j       Diagram   Composition j
%e A228369 -----------------------------------
%e A228369 .               _
%e A228369 1  1           |_|   1;
%e A228369 .             _ _
%e A228369 2  1         | |_|   1, 1,
%e A228369 2  2         |_ _|   2;
%e A228369 .           _ _ _
%e A228369 3  1       | | |_|   1, 1, 1,
%e A228369 3  2       | |_ _|   1, 2,
%e A228369 3  3       |   |_|   2, 1,
%e A228369 3  4       |_ _ _|   3;
%e A228369 .         _ _ _ _
%e A228369 4  1     | | | |_|   1, 1, 1, 1,
%e A228369 4  2     | | |_ _|   1, 1, 2,
%e A228369 4  3     | |   |_|   1, 2, 1,
%e A228369 4  4     | |_ _ _|   1, 3,
%e A228369 4  5     |   | |_|   2, 1, 1,
%e A228369 4  6     |   |_ _|   2, 2,
%e A228369 4  7     |     |_|   3, 1,
%e A228369 4  8     |_ _ _ _|   4;
%e A228369 .
%e A228369 Triangle begins:
%e A228369 [1];
%e A228369 [1,1],[2];
%e A228369 [1,1,1],[1,2],[2,1],[3];
%e A228369 [1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4];
%e A228369 [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 A228369 ...
%t A228369 Table[Sort[Join@@Permutations/@IntegerPartitions[n],OrderedQ[PadRight[{#1,#2}]]&],{n,5}] (* _Gus Wiseman_, Dec 14 2017 *)
%o A228369 (PARI)
%o A228369 gen_comp(n)=
%o A228369 {  /* Generate compositions of n as lists of parts (order is lex): */
%o A228369     my(ct = 0);
%o A228369     my(m, z, pt);
%o A228369     \\ init:
%o A228369     my( a = vector(n, j, 1) );
%o A228369     m = n;
%o A228369     while ( 1,
%o A228369         ct += 1;
%o A228369         pt = vector(m, j, a[j]);
%o A228369         /* for A228369  print composition: */
%o A228369         for (j=1, m, print1(pt[j],", ") );
%o A228369 \\        /* for A228525 print reversed (order is colex): */
%o A228369 \\        forstep (j=m, 1, -1, print1(pt[j],", ") );
%o A228369         if ( m<=1,  return(ct) );  \\ current is last
%o A228369         a[m-1] += 1;
%o A228369         z = a[m] - 2;
%o A228369         a[m] = 1;
%o A228369         m += z;
%o A228369     );
%o A228369     return(ct);
%o A228369 }
%o A228369 for(n=1, 12, gen_comp(n) );
%o A228369 \\ _Joerg Arndt_, Sep 02 2013
%o A228369 (Haskell)
%o A228369 a228369 n = a228369_list !! (n - 1)
%o A228369 a228369_list = concatMap a228369_row [1..]
%o A228369 a228369_row 0 = []
%o A228369 a228369_row n
%o A228369   | 2^k == 2 * n + 2 = [k - 1]
%o A228369   | otherwise        = a228369_row (n `div` 2^k) ++ [k] where
%o A228369     k = a007814 (n + 1) + 1
%o A228369 -- _Peter Kagey_, Jun 27 2016
%o A228369 (Python)
%o A228369 a = [[[]], [[1]]]
%o A228369 for s in range(2, 9):
%o A228369     a.append([])
%o A228369     for k in range(1, s+1):
%o A228369         for ss in a[s-k]:
%o A228369             a[-1].append([k]+ss)
%o A228369 print(a)
%o A228369 # _Andrey Zabolotskiy_, Jul 19 2017
%Y A228369 Cf. A001511, A026791, A066099, A101211, A124734, A228351, A228525, A281013.
%K A228369 nonn,tabf
%O A228369 1,4
%A A228369 _Omar E. Pol_, Aug 28 2013