login
List giving all subsets of natural numbers arranged in standard statistical (or Yates) order.
326

%I #33 Feb 01 2023 14:34:08

%S 0,1,2,1,2,3,1,3,2,3,1,2,3,4,1,4,2,4,1,2,4,3,4,1,3,4,2,3,4,1,2,3,4,5,

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

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

%N List giving all subsets of natural numbers arranged in standard statistical (or Yates) order.

%C For n>0: first occurrence of n in row 2^(n-1), and when the table is seen as a flattened list at position n*2^(n-1)+1, cf. A005183. - _Reinhard Zumkeller_, Nov 16 2013

%C Row n lists the positions of 1's in the reversed binary expansion of n. Compare to triangles A112798 and A213925. - _Gus Wiseman_, Jul 22 2019

%D S. Hedayat, N. J. A. Sloane and J. Stufken, Orthogonal Arrays, Springer-Verlag, NY, 1999, p. 249.

%H Reinhard Zumkeller, <a href="/A048793/b048793.txt">Rows n = 0..1000 of triangle, flattened</a>

%F Constructed recursively: subsets that include n are obtained by appending n to all earlier subsets.

%e From _Gus Wiseman_, Jul 22 2019: (Start)

%e Triangle begins:

%e {}

%e 1

%e 2

%e 1 2

%e 3

%e 1 3

%e 2 3

%e 1 2 3

%e 4

%e 1 4

%e 2 4

%e 1 2 4

%e 3 4

%e 1 3 4

%e 2 3 4

%e 1 2 3 4

%e 5

%e 1 5

%e 2 5

%e 1 2 5

%e 3 5

%e (End)

%p T:= proc(n) local i, l, m; l:= NULL; m:= n;

%p if n=0 then return 0 fi; for i while m>0 do

%p if irem(m, 2, 'm')=1 then l:=l, i fi od; l

%p end:

%p seq(T(n), n=0..50); # _Alois P. Heinz_, Sep 06 2014

%t s[0] = {{}}; s[n_] := s[n] = Join[s[n - 1], Append[#, n]& /@ s[n - 1]]; Join[{0}, Flatten[s[6]]] (* _Jean-François Alcover_, May 24 2012 *)

%t Table[Join@@Position[Reverse[IntegerDigits[n,2]],1],{n,30}] (* _Gus Wiseman_, Jul 22 2019 *)

%o (C)

%o #include <stdio.h>

%o #include <stdlib.h>

%o #define USAGE "Usage: 'A048793 num' where num is the largest number to use creating sets.\n"

%o #define MAX_NUM 10

%o #define MAX_ROW 1024

%o int main(int argc, char *argv[]) {

%o unsigned short a[MAX_ROW][MAX_NUM]; signed short old_row, new_row, i, j, end;

%o if (argc < 2) { fprintf(stderr, USAGE); return EXIT_FAILURE; }

%o end = atoi(argv[1]); end = (end > MAX_NUM) ? MAX_NUM: end;

%o for (i = 0; i < MAX_ROW; i++) for ( j = 0; j < MAX_NUM; j++) a[i][j] = 0;

%o a[1][0] = 1; new_row = 2;

%o for (i = 2; i <= end; i++) {

%o a[new_row++ ][0] = i;

%o for (old_row = 1; a[old_row][0] != i; old_row++) {

%o for (j = 0; a[old_row][j] != 0; j++) { a[new_row][j] = a[old_row][j]; }

%o a[new_row++ ][j] = i;

%o }

%o }

%o fprintf(stdout, "Values: 0");

%o for (i = 1; a[i][0] != 0; i++) for (j = 0; a[i][j] != 0; j++) fprintf(stdout, ",%d", a[i][j]);

%o fprintf(stdout, "\n"); return EXIT_SUCCESS

%o }

%o (Haskell)

%o a048793 n k = a048793_tabf !! n !! k

%o a048793_row n = a048793_tabf !! n

%o a048793_tabf = [0] : [1] : f [[1]] where

%o f xss = yss ++ f (xss ++ yss) where

%o yss = [y] : map (++ [y]) xss

%o y = last (last xss) + 1

%o -- _Reinhard Zumkeller_, Nov 16 2013

%Y Cf. A048794.

%Y Row lengths are A000120.

%Y First column is A001511.

%Y Heinz numbers of rows are A019565.

%Y Row sums are A029931.

%Y Reversing rows gives A272020.

%Y Subtracting 1 from each term gives A133457; subtracting 1 and reversing rows gives A272011.

%Y Indices of relatively prime rows are A291166 (see also A326674); arithmetic progressions are A295235; rows with integer average are A326669 (see also A326699/A326700); pairwise coprime rows are A326675.

%Y Cf. A035327, A070939.

%K nonn,tabf,easy,nice

%O 0,3

%A _N. J. A. Sloane_

%E More terms from Larry Reeves (larryr(AT)acm.org), Apr 11 2000