A059519 -id:A059519 - cp's OEIS frontend

A367906 Numbers k such that it is possible to choose a different binary index of each binary index of k.

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 26, 28, 32, 33, 34, 35, 36, 37, 38, 40, 41, 44, 48, 49, 50, 52, 56, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 76, 80, 81, 82, 84, 88, 96, 97, 98, 100, 104, 112, 128, 129, 130, 131, 132

Offset: 1

Gus Wiseman, Dec 11 2023

Also BII-numbers of set-systems (sets of nonempty sets) satisfying a strict version of the axiom of choice.
A binary index of k (row k of A048793) is any position of a 1 in its reversed binary expansion. A set-system is a finite set of finite nonempty sets. We define the set-system with BII-number k to be obtained by taking the binary indices of each binary index of k. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary digits (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The set-system {{2,3},{1,2,3},{1,4}} with BII-number 352 has choices such as (2,1,4) that satisfy the axiom, so 352 is in the sequence.
The terms together with the corresponding set-systems begin:
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  16: {{1,3}}
  17: {{1},{1,3}}

John Tyler Rascoe, Table of n, a(n) for n = 1..10000
Wikipedia, Axiom of choice.

These set-systems are counted by A367902, non-isomorphic A368095.
Positions of positive terms in A367905, firsts A367910, sorted A367911.
The complement is A367907.
If there is one unique choice we get A367908, counted by A367904.
If there are multiple choices we get A367909, counted by A367772.
Unlabeled multiset partitions of this type are A368098, complement A368097.
A version for MM-numbers of multisets is A368100, complement A355529.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
Cf. A000612, A055621, A059519, A072639, A083323, A309326, A326702, A326753, A367770, A367912.
BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers), A326783 (uniform), A326784 (regular), A326788 (simple), A330217 (achiral).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100], Select[Tuples[bpe/@bpe[#]], UnsameQ@@#&]!={}&]

from itertools import count, islice, product
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen(): #generator of terms
    for n in count(1):
        for j in list(product(*[bin_i(k) for k in bin_i(n)])):
            if len(set(j)) == len(j):
                yield(n); break
A367906_list = list(islice(a_gen(),100)) # John Tyler Rascoe, Dec 23 2023

A291166 Connected Haar graph numbers.

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81

Offset: 1

Eric W. Weisstein, Aug 19 2017

nonn

Complement of A291165.

These appear to be numbers whose positions of 1's in their reversed binary expansion are relatively prime. If so, this sequence lists all positions of 1's in A326674. Numbers whose positions of 1's in their reversed binary expansion are pairwise coprime (as opposed to relatively prime) are A326675. - Gus Wiseman, Jul 19 2019

Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Haar Graph

Cf. A000120, A029931, A048793, A059519, A070939, A289508, A291165, A295235, A319826, A326031, A326669, A326672, A326673.

A333224 Number of distinct positive consecutive subsequence-sums of the k-th composition in standard order.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 3, 3, 1, 3, 2, 4, 3, 4, 4, 4, 1, 3, 3, 5, 3, 5, 4, 5, 3, 4, 5, 5, 5, 5, 5, 5, 1, 3, 3, 5, 2, 5, 5, 6, 3, 6, 3, 6, 5, 6, 5, 6, 3, 4, 6, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 1, 3, 3, 5, 3, 6, 6, 7, 3, 5, 5, 7, 4, 6, 6, 7, 3, 6, 4, 7, 5, 7, 6

Offset: 0

Gus Wiseman, Mar 18 2020

nonn

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The composition (4,3,1,2) has positive subsequence-sums 1, 2, 3, 4, 6, 7, 8, 10, so a(550) = 8.

Dominated by A124770.
Compositions where every subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222. The case of partitions is counted by A325768 and ranked by A325779.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and A325592 and ranked by A299702.
Strict knapsack partitions are counted by A275972 and ranked by A059519 and A301899.
Knapsack compositions are counted by A325676 and A325687 and ranked by A333223. The case of partitions is counted by A325769 and ranked by A325778, for which the number of distinct consecutive subsequences is given by A325770.
Allowing empty subsequences gives A333257.
Cf. A000120, A003022, A029931, A048793, A066099, A070939, A103295, A124767, A143823, A295235, A325680, A333217.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[ReplaceList[stc[n],{_,s__,_}:>Plus[s]]]],{n,0,100}]

a(n) = A333257(n) - 1.

A333257 Number of distinct consecutive subsequence-sums of the k-th composition in standard order.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 4, 4, 2, 4, 3, 5, 4, 5, 5, 5, 2, 4, 4, 6, 4, 6, 5, 6, 4, 5, 6, 6, 6, 6, 6, 6, 2, 4, 4, 6, 3, 6, 6, 7, 4, 7, 4, 7, 6, 7, 6, 7, 4, 5, 7, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 2, 4, 4, 6, 4, 7, 7, 8, 4, 6, 6, 8, 5, 7, 7, 8, 4, 7, 5, 8, 6, 8, 7

Offset: 0

Gus Wiseman, Mar 20 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The ninth composition in standard order is (3,1), which has consecutive subsequences (), (1), (3), (3,1), with sums 0, 1, 3, 4, so a(9) = 4.

Dominated by A124771.
Compositions where every subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222, while the case of partitions is counted by A325768 and ranked by A325779.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and ranked by A299702.
Knapsack compositions are counted by A325676 and A325687 and ranked by A333223.
The version for Heinz numbers of partitions is A325770.
Not allowing empty subsequences gives A333224.
Cf. A000120, A029931, A048793, A059519, A066099, A070939, A114994, A124765, A124767, A233564, A272919, A325778, A333217.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[ReplaceList[stc[n],{_,s___,_}:>Plus[s]]]],{n,0,100}]

a(n) = A333224(n) + 1.

A367908 Numbers n such that there is only one way to choose a different binary index of each binary index of n.

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 9, 10, 11, 13, 14, 17, 19, 21, 22, 24, 26, 28, 34, 35, 37, 38, 40, 41, 44, 49, 50, 56, 67, 69, 70, 73, 74, 81, 88, 98, 104, 128, 129, 130, 131, 133, 134, 136, 137, 138, 139, 141, 142, 145, 147, 149, 150, 152, 154, 156, 162, 163, 165, 166, 168

Offset: 1

Gus Wiseman, Dec 11 2023

Also BII-numbers of set-systems (sets of nonempty sets) satisfying a strict version of the axiom of choice in exactly one way.
A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. A set-system is a finite set of finite nonempty sets. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary digits (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The set-system {{1},{1,2},{1,3}} with BII-number 21 satisfies the axiom in exactly one way, namely (1,2,3), so 21 is in the sequence.
The terms together with the corresponding set-systems begin:
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  17: {{1},{1,3}}
  19: {{1},{2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}

John Tyler Rascoe, Table of n, a(n) for n = 1..2000
Wikipedia, Axiom of choice.

These set-systems are counted by A367904.
Positions of 1's in A367905, firsts A367910, sorted firsts A367911.
If there is at least one choice we get A367906, counted by A367902.
If there are no choices we get A367907, counted by A367903.
If there are multiple choices we get A367909, counted by A367772.
The version for MM-numbers of multiset partitions is A368101.
A048793 lists binary indices, length A000120, reverse A272020, sum A029931.
A058891 counts set-systems, covering A003465, connected A323818.
A059201 counts covering T_0 set-systems.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
A368098 counts unlabeled multiset partitions for axiom, complement A368097.
Cf. A000612, A059519, A309326, A326675, A326702, A326753, A326872, A355529, A367902, A367912.
BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers), A326783 (uniform), A326784 (regular), A326788 (simple), A330217 (achiral).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100], Length[Select[Tuples[bpe/@bpe[#]], UnsameQ@@#&]]==1&]

from itertools import count, islice, product
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen(): #generator of terms
    for n in count(1):
        p = list(product(*[bin_i(k) for k in bin_i(n)]))
        x,c = len(p),0
        for j in range(x):
            if len(set(p[j])) == len(p[j]): c += 1
            if j+1 == x and c == 1: yield(n)
A367908_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Feb 10 2024

A367907 U A367908 U A367909 = A000027.

A333223 Numbers k such that every distinct consecutive subsequence of the k-th composition in standard order has a different sum.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 17, 18, 19, 20, 21, 24, 26, 28, 31, 32, 33, 34, 35, 36, 40, 41, 42, 48, 50, 56, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 80, 81, 84, 85, 88, 96, 98, 100, 104, 106, 112, 120, 127, 128, 129, 130, 131, 132, 133

Offset: 1

Gus Wiseman, Mar 17 2020

nonn

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The list of terms together with the corresponding compositions begins:
    0: ()            21: (2,2,1)           65: (6,1)
    1: (1)           24: (1,4)             66: (5,2)
    2: (2)           26: (1,2,2)           67: (5,1,1)
    3: (1,1)         28: (1,1,3)           68: (4,3)
    4: (3)           31: (1,1,1,1,1)       69: (4,2,1)
    5: (2,1)         32: (6)               70: (4,1,2)
    6: (1,2)         33: (5,1)             71: (4,1,1,1)
    7: (1,1,1)       34: (4,2)             72: (3,4)
    8: (4)           35: (4,1,1)           73: (3,3,1)
    9: (3,1)         36: (3,3)             74: (3,2,2)
   10: (2,2)         40: (2,4)             80: (2,5)
   12: (1,3)         41: (2,3,1)           81: (2,4,1)
   15: (1,1,1,1)     42: (2,2,2)           84: (2,2,3)
   16: (5)           48: (1,5)             85: (2,2,2,1)
   17: (4,1)         50: (1,3,2)           88: (2,1,4)
   18: (3,2)         56: (1,1,4)           96: (1,6)
   19: (3,1,1)       63: (1,1,1,1,1,1)     98: (1,4,2)
   20: (2,3)         64: (7)              100: (1,3,3)

Distinct subsequences are counted by A124770 and A124771.
A superset of A333222, counted by A169942, with partition case A325768.
These compositions are counted by A325676.
A version for partitions is A325769, with Heinz numbers A325778.
The number of distinct positive subsequence-sums is A333224.
The number of distinct subsequence-sums is A333257.
Numbers whose binary indices are a strict knapsack partition are A059519.
Knapsack partitions are counted by A108917, with strict case A275972.
Golomb subsets are counted by A143823.
Heinz numbers of knapsack partitions are A299702.
Maximal Golomb rulers are counted by A325683.
Cf. A000120, A003022, A029931, A048793, A066099, A070939, A103295 A325779, A233564, A325680, A325687, A325770, A333217.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],UnsameQ@@Total/@Union[ReplaceList[stc[#],{_,s__,_}:>{s}]]&]

A334268 Number of compositions of n where every distinct subsequence (not necessarily contiguous) has a different sum.

Original entry on oeis.org

1, 1, 2, 4, 5, 10, 10, 24, 24, 43, 42, 88, 72, 136, 122, 242, 213, 392, 320, 630, 490, 916, 742, 1432, 1160, 1955, 1604, 2826, 2310, 3850, 2888, 5416, 4426, 7332, 5814, 10046, 7983, 12946, 10236, 17780, 14100, 22674, 17582, 30232, 23674, 37522, 29426, 49832

Offset: 0

Gus Wiseman, Jun 02 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

The contiguous case is A325676.

			The a(1) = 1 through a(6) = 19 compositions:
  (1)  (2)    (3)      (4)        (5)          (6)
       (1,1)  (1,2)    (1,3)      (1,4)        (1,5)
              (2,1)    (2,2)      (2,3)        (2,4)
              (1,1,1)  (3,1)      (3,2)        (3,3)
                       (1,1,1,1)  (4,1)        (4,2)
                                  (1,1,3)      (5,1)
                                  (1,2,2)      (1,1,4)
                                  (2,2,1)      (2,2,2)
                                  (3,1,1)      (4,1,1)
                                  (1,1,1,1,1)  (1,1,1,1,1,1)

These compositions are ranked by A334967.
Compositions where every restriction to a subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222. The case of partitions is counted by A325768 and ranked by A325779.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and A325592 and ranked by A299702, while the strict case is counted by A275972 and ranked by A059519 and A301899.
Knapsack compositions are counted by A325676 and A325687 and ranked by A333223. The case of partitions is counted by A325769 and ranked by A325778, for which the number of distinct consecutive subsequences is given by A325770.
Cf. A003022, A029931, A103295, A143823, A325680, A333224.

b:= proc(n, s) option remember; `if`(n=0, 1, add((h->
      `if`(nops(h)=nops(map(l-> add(i, i=l), h)),
       b(n-j, h), 0))({s[], map(l-> [l[], j], s)[]}), j=1..n))
    end:
a:= n-> b(n, {[]}):
seq(a(n), n=0..23);  # Alois P. Heinz, Jun 03 2020

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@Total/@Union[Subsets[#]]&]],{n,0,15}]

a(18)-a(47) from Alois P. Heinz, Jun 03 2020

A059520 Number of partitions into distinct parts, with some sub-partitions having equal sums. Partition(n) = [a, b, c...] where 2n = 2^a + 2^b + 2^c + ...

Original entry on oeis.org

7, 13, 15, 22, 23, 25, 27, 29, 30, 31, 39, 42, 43, 45, 46, 47, 49, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 71, 75, 76, 77, 78, 79, 82, 83, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 97, 99, 101, 102, 103, 105, 106, 107, 108, 109, 110, 111, 113, 114, 115, 117, 118, 119

Offset: 1

Marc LeBrun, Jan 19 2001

Partition encoding as in A029931. Complement of A059519.

			13=1+4+8 so Partition(13) = [1,3,4], whose sub-sums are 0,1,3,4,5,7 and 13, with 4 twice (once from 1+3 and once from 4 by itself).

A029931, A059519.

cp's OEIS Frontend

A367906 Numbers k such that it is possible to choose a different binary index of each binary index of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A291166 Connected Haar graph numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

A333224 Number of distinct positive consecutive subsequence-sums of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A333257 Number of distinct consecutive subsequence-sums of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A367908 Numbers n such that there is only one way to choose a different binary index of each binary index of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A333223 Numbers k such that every distinct consecutive subsequence of the k-th composition in standard order has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334268 Number of compositions of n where every distinct subsequence (not necessarily contiguous) has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A059520 Number of partitions into distinct parts, with some sub-partitions having equal sums. Partition(n) = [a, b, c...] where 2n = 2^a + 2^b + 2^c + ...

Views

Author

Keywords

Comments

Examples

Crossrefs