A082185 -id:A082185 - cp's OEIS frontend

A193360 Concatenation of P{1},P{1,2},P{1,2,3}... where P(A) denotes the power set of A ordered by the size of the subsets, and in each subset, following the increasing order.

1, 1, 2, 1, 2, 1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 3, 1, 4, 2, 3, 2, 4, 3, 4, 1, 2, 3, 1, 2, 4, 1, 3, 4, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 1, 3, 1, 4, 1, 5, 2, 3, 2, 4, 2, 5, 3, 4, 3, 5, 4, 5, 1, 2, 3, 1, 2, 4, 1, 2, 5, 1, 3, 4

Offset: 1

José María Grau Ribas, Jul 24 2011

Fractal sequence.
From Robert Israel, Jan 09 2023: (Start)
Subsets of the same size are ordered lexicographically.
The first occurrence of k in this sequence is at position (k - 2)*2^(k - 1) + k + 1. (End)

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A082185.

comp:= proc(a,b) local i;
  for i from 1 do if a[i] < b[i] then return true elif a[i] > b[i] then return false fi od
end proc:
[seq(seq(op(map(op, sort(combinat:-choose(n,k),comp))),k=1..n),n=1..6)]; # Robert Israel, Jan 09 2023
# second Maple program:
T:= n-> map(x-> x[], [seq(combinat[choose]([$1..n], i)[], i=1..n)])[]:
seq(T(n), n=1..5);  # Alois P. Heinz, Jan 30 2023

t={};Do[t=Join[t,Subsets[Range[n]]],{n,1,5}];Flatten[t]
Table[Subsets[Range[n]],{n,5}]//Flatten (* Harvey P. Dale, May 05 2019 *)

A152884 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} with excedance set equal to the k-th subset of {1,2,...,n-1} (n>=0, 0<=k<=ceiling(2^(n-1))-1). The subsets of {1,2,...,n-1} are ordered according to size, while the subsets of the same size follow the lexicographic order.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 3, 1, 7, 3, 1, 1, 1, 15, 7, 3, 1, 31, 17, 7, 7, 3, 1, 15, 7, 3, 1, 1, 1, 31, 15, 7, 3, 1, 115, 69, 37, 15, 31, 17, 7, 7, 3, 1, 115, 69, 31, 37, 17, 7, 15, 7, 3, 1, 31, 15, 7, 3, 1, 1, 1, 63, 31, 15, 7, 3, 1, 391, 245, 145, 77, 31, 115, 69, 37, 15, 31, 17, 7, 7, 3, 1

Offset: 0

Emeric Deutsch, Jan 13 2009

For example, the eight subsets of {1,2,3} are ordered as empty,1,2,3,12,13,23,123. The excedance set of a permutation p of {1,2,...,n} is the set of indices i such that p(i)>i; it is a subset of {1,2,...,n-1}.
Row n contains ceiling(2^(n-1)) entries.
Sum of entries in row n is n! (A000142).
The given Maple program yields the term of the sequence corresponding to a specified permutation size n and a specified excedance set A.
All terms are odd. - Alois P. Heinz, Jan 31 2023

			T(5,3) = 3 because the 3rd subset of {1,2,3,4} is {3} and the permutations of {1,2,3,4,5} with excedance set {3} are 12435, 12534 and 12543.
T(5,4) = 1: 12354 (4th subset of {1,2,3,4} is {4}).
Triangle starts:
      k=0   1  2  3  4   5   6  7  8 ...
  n=0:  1;
  n=1:  1;
  n=2:  1,  1;
  n=3:  1,  3, 1, 1;
  n=4:  1,  7, 3, 1, 7,  3,  1, 1;
  n=5:  1, 15, 7, 3, 1, 31, 17, 7, 7, 3, 1, 15, 7, 3, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..15, flattened
R. Ehrenborg and E. Steingrimsson, The excedance set of a permutation, Advances in Appl. Math., 24, 284-299, 2000.

Row sums are A000142.
See A360288, A360289 for similar triangles.
Cf. A000225, A011782, A082185, A136126, A193360, A329369 (another version).

n := 7: A := {1, 2, 4}: with(combinat): P := permute(n): EX := proc (p) local S, i: S := {}: for i to n-1 do if i < p[i] then S := `union`(S, {i}) else end if end do: S end proc: ct := 0: for j to factorial(n) do if EX(P[j]) = A then ct := ct+1 else end if end do: ct;
# second Maple program:
T:= proc(n) option remember; uses combinat; local b, i, l;
      l:= map(x-> {x[]}, [seq(choose([$1..n-1], i)[], i=0..n-1)]):
      for i to nops(l) do h(l[i]):=i od:
      b:= proc(s, l) option remember; (m->
           `if`(m=0, x^h(l), add(b(s minus {i}, {l[],
           `if`(i
      seq(coeff(p, x, i), i=1..degree(p)))(b({$1..n}, {}))
    end: T(0):=1:
seq(T(n), n=0..8);  # Alois P. Heinz, Jan 29 2023

T(n,k) = A000225(n-k) = 2^(n-k) - 1 for n>k>0. - Alexander R. Povolotsky, May 14 2025

T(0,0)=1 prepended and indexing adapted by Alois P. Heinz, Jan 29 2023

A335845 Irregular triangular array T(n,k) read by rows. Row n gives the number of permutations of {1,2,...,n} whose descent set is S for each subset S of {1,2,...,n-1} ordered lexicographically within the rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 3, 3, 5, 3, 1, 1, 4, 9, 9, 4, 6, 16, 11, 11, 16, 6, 4, 9, 9, 4, 1, 1, 5, 14, 19, 14, 5, 10, 35, 40, 19, 26, 61, 40, 26, 35, 10, 10, 35, 26, 40, 61, 26, 19, 40, 35, 10, 5, 14, 19, 14, 5, 1, 1, 6, 20, 34, 34, 20, 6, 15, 64, 99

Offset: 0

Geoffrey Critzer, Jun 26 2020

Row lengths are A011782(n).

Every row begins and ends with a 1 because there is exactly 1 n-permutation whose descent set is the empty set and there is exactly 1 n-permutation whose descent set is {1,2,...,n-1}, namely the identity permutation and its reverse.

			T(5,5) = 6 because there are 6 permutations of [5] whose descent set is {1,2}: (3,2,1,4,5), (4,2,1,3,5), (4,3,1,2,5), (5,2,1,3,4), (5,3,1,2,4), (5,4,1,2,3).
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2, 2, 1;
  1, 3, 5, 3, 3, 5,  3,  1;
  1, 4, 9, 9, 4, 6, 16, 11, 11, 16, 6, 4, 9, 9, 4, 1;
  ...

Alois P. Heinz, Rows n = 0..15, flattened

Row sums give A000142.

Cf. A011782, A060350, A060351, A082185.

T:= proc(n) option remember; local b, i, l; l:=
      map(x-> add(2^(i-1), i=x), [seq(combinat[choose](
              [$1..n-1], i)[], i=0..n-1)]); h(0):=0;
      for i to nops(l) do h(l[i]):= (i-1) od: b:=
      proc(u, o, t) option remember; `if`(u+o=0, x^h(t),
        add(b(u-j, o+j-1, t), j=1..u)+
        add(b(u+j-1, o-j, t+2^(u+o-1)), j=1..o))
      end; (p->
      seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2))
    end:
seq(T(n), n=0..7);  # Alois P. Heinz, Feb 03 2023

f[list_] := (-1)^(Length[list] + 1) Apply[Multinomial, list];
Table[g[S_] :=Abs[Total[Map[f, Map[Differences,Map[Prepend[#, 0] &, Map[Append[#, n] &, Subsets[S]]]]]]];Map[g, Subsets[Range[n - 1]]], {n, 1, 5}] // Grid

T(0,0)=1 prepended by Alois P. Heinz, Sep 08 2020

A359941 Irregular triangle read row by row. The k-th row are integers from 0 to 2^k-1 in base 2 ordered in graded reverse lexicographical order.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 4, 3, 5, 6, 7, 0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12, 7, 11, 13, 14, 15, 0, 1, 2, 4, 8, 16, 3, 5, 9, 17, 6, 10, 18, 12, 20, 24, 7, 11, 19, 13, 21, 25, 14, 22, 26, 28, 15, 23, 27, 29, 30, 31, 0, 1, 2, 4, 8, 16, 32, 3, 5, 9, 17, 33, 6

Offset: 0

Jean Liénardy, Jan 19 2023

The integers in the k-th row are first ordered by the number of 1 in their binary representation (Hamming weight). Elements of the same Hamming weight are ordered by reverse colexicographical order.

The k-th row corresponds to the graded lexicographical order of monomials. For example, with k=3, the monomial are ordered as {1, x0, x1, x2, x1*x0, x2*x0, x2*x1, x2*x1*x0}. This ordering of monomial leads to efficient implementation of polynomial long division (see Links section).

			As an irregular triangle:
  0;
  0, 1;
  0, 1, 2, 3;
  0, 1, 2, 4, 3, 5, 6, 7;
  0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12, 7, 11, 13, 14, 15;
  ...
For k = 4, the graded lexicographical order of integers 0..15 written in base 2 is
  0000
  0001, 0010, 0100, 1000,
  0011, 0101, 1001, 0110, 1010, 1100,
  0111, 1011, 1101, 1110,
  1111
Note that 1001 < 0110 as the least significant digit on which they differ is the last one, and 1 < 0 due to the reverse colexicographical ordering.

Alois P. Heinz, Rows n = 0..13, flattened
Jean Liénardy, C++ program
Wikipedia, Monomial order

Cf. A023443, A082185, A360302.

T:= n-> map(x-> add(2^(i-1), i=x), [seq(
    combinat[choose]([$1..n], i)[], i=0..n)])[]:
seq(T(n), n=0..6);  # Alois P. Heinz, Feb 03 2023

T(n,A360302(n,k)) = k = A360302(n,T(n,k)). - Alois P. Heinz, Feb 06 2023

A360302 T(n,k) is the position of the set encoded in the binary expansion of k within the shortlex order for the powerset of [n]; triangle T(n,k), n>=0, 0<=k<=2^n-1, read by rows.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 4, 3, 5, 6, 7, 0, 1, 2, 5, 3, 6, 8, 11, 4, 7, 9, 12, 10, 13, 14, 15, 0, 1, 2, 6, 3, 7, 10, 16, 4, 8, 11, 17, 13, 19, 22, 26, 5, 9, 12, 18, 14, 20, 23, 27, 15, 21, 24, 28, 25, 29, 30, 31, 0, 1, 2, 7, 3, 8, 12, 22, 4, 9, 13, 23, 16

Offset: 0

Alois P. Heinz, Feb 03 2023

In shortlex order for 2^[n] the subsets are primarily sorted by cardinality and then into lexicographical order.
The set encoded by k consists of the indices of 1-bits (rightmost index is 1).
Row n is a permutation of {0, 1, ..., 2^n-1} whose inverse is in row n of A359941.

			The subsets of [4] listed in shortlex order (starting at position 0) are: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}.
T(4,0) = T(4,0000_2) = 0: {} is at position 0.
T(4,3) = T(4,0011_2) = 5: {1,2} is at position 5.
T(4,6) = T(4,0110_2) = 8: {2,3} is at position 8.
T(4,7) = T(4,0111_2) = 11: {1,2,3} is at position 11.
T(4,15) = T(4,1111_2) = 15: {1,2,3,4} is at position 15.
Triangle T(n,k) begins:
  0;
  0, 1;
  0, 1, 2, 3;
  0, 1, 2, 4, 3, 5, 6,  7;
  0, 1, 2, 5, 3, 6, 8, 11, 4, 7, 9, 12, 10, 13, 14, 15;
  ...

Alois P. Heinz, Rows n = 0..13, flattened
Wikipedia, Shortlex order

Columns k=0-1 give: A000004, A057427.
Row sums give A006516(n) = A000217(A000225(n)).
Row lengths are A000079.
Cf. A082185, A193360, A359941.

T:= proc(n) option remember; local h, i, l;
      l:= map(x-> add(2^(i-1), i=x),
         [seq(combinat[choose]([$1..n], i)[], i=0..n)]);
      h(0):=0; for i to nops(l) do h(l[i]):= (i-1) od:
      seq(h(i), i=0..2^n-1)
    end:
seq(T(n), n=0..6);

T(n,A359941(n,k)) = k = A359941(n,T(n,k)).

cp's OEIS Frontend

A193360 Concatenation of P{1},P{1,2},P{1,2,3}... where P(A) denotes the power set of A ordered by the size of the subsets, and in each subset, following the increasing order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A335845 Irregular triangular array T(n,k) read by rows. Row n gives the number of permutations of {1,2,...,n} whose descent set is S for each subset S of {1,2,...,n-1} ordered lexicographically within the rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A359941 Irregular triangle read row by row. The k-th row are integers from 0 to 2^k-1 in base 2 ordered in graded reverse lexicographical order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A360302 T(n,k) is the position of the set encoded in the binary expansion of k within the shortlex order for the powerset of [n]; triangle T(n,k), n>=0, 0<=k<=2^n-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula