Displaying 1-10 of 12 results found.
Number of subsets of {1..n} such that it is possible to choose a different binary index of each element.
+10
27
1, 2, 4, 7, 14, 24, 39, 61, 122, 203, 315, 469, 676, 952, 1307, 1771, 3542, 5708, 8432, 11877, 16123, 21415, 27835, 35757, 45343, 57010, 70778, 87384, 106479, 129304, 155802, 187223, 374446, 588130, 835800, 1124981, 1456282, 1841361, 2281772, 2791896, 3367162
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
EXAMPLE
The a(0) = 1 through a(4) = 14 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{2} {2} {2}
{1,2} {3} {3}
{1,2} {4}
{1,3} {1,2}
{2,3} {1,3}
{1,4}
{2,3}
{2,4}
{3,4}
{1,2,4}
{1,3,4}
{2,3,4}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], Select[Tuples[bpe/@#], UnsameQ@@#&]!={}&]], {n, 0, 10}]
CROSSREFS
Unlabeled graphs of this type are counted by A134964, complement A140637. Simple graphs not of this type are counted by A367867, covering A367868. Set systems uniquely of this type are counted by A367904, ranks A367908. Unlabeled multiset partitions of this type are A368098, complement A368097. A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
Number of maximal subsets of {1..n} such that it is possible to choose a different prime factor of each element.
+10
22
1, 1, 1, 1, 2, 2, 5, 5, 7, 11, 25, 25, 38, 38, 84, 150, 178, 178, 235, 235, 341, 579, 1235, 1235
COMMENTS
First differs from A307984 at a(21) = 579, A307984(21) = 578. The difference is due to the set {10,11,13,14,15,17,19,21}, which is not a basis because log(10) + log(21) = log(14) + log(15). Also length-pi(n) subsets of {1..n} such that it is possible to choose a different prime factor of each element.
EXAMPLE
The a(0) = 1 through a(8) = 7 subsets:
{} {} {2} {2,3} {2,3} {2,3,5} {2,3,5} {2,3,5,7} {2,3,5,7}
{3,4} {3,4,5} {2,5,6} {2,5,6,7} {2,5,6,7}
{3,4,5} {3,4,5,7} {3,4,5,7}
{3,5,6} {3,5,6,7} {3,5,6,7}
{4,5,6} {4,5,6,7} {3,5,7,8}
{4,5,6,7}
{5,6,7,8}
MATHEMATICA
Table[Length[Select[Subsets[Range[n], {PrimePi[n]}], Length[Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]>0&]], {n, 0, 10}]
CROSSREFS
Factorizations of this type are counted by A368414, complement A368413. A307984 counts Q-bases of logarithms of positive integers.
A355741 counts choices of a prime factor of each prime index.
Cf. A000040, A000720, A005117, A045778, A133686, A333331, A355739, A355740, A355744, A355745, A367905, A368110.
Number of subsets of {1..n} such that it is not possible to choose a different binary index of each element.
+10
20
0, 0, 0, 1, 2, 8, 25, 67, 134, 309, 709, 1579, 3420, 7240, 15077, 30997, 61994, 125364, 253712, 512411, 1032453, 2075737, 4166469, 8352851, 16731873, 33497422, 67038086, 134130344, 268328977, 536741608, 1073586022, 2147296425, 4294592850, 8589346462, 17179033384
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
EXAMPLE
The a(0) = 0 through a(5) = 8 subsets:
. . . {1,2,3} {1,2,3} {1,2,3}
{1,2,3,4} {1,4,5}
{1,2,3,4}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], Select[Tuples[bpe/@#], UnsameQ@@#&]=={}&]], {n, 0, 10}]
CROSSREFS
Simple graphs not of this type are counted by A133686, covering A367869. Unlabeled graphs of this type are counted by A140637, complement A134964. Set systems uniquely not of this type are counted by A367904, ranks A367908. Unlabeled multiset partitions of this type are A368097, complement A368098. 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, A072639, A355739, A355740, A367772, A367905, A367909, A367912, A368094, A368095, A368109.
Number of subsets of {1..n} such that a unique set can be obtained by choosing a different binary index of each element.
+10
15
1, 2, 4, 6, 12, 19, 30, 45, 90, 147, 230, 343, 504, 716, 994, 1352, 2704, 4349, 6469
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
EXAMPLE
The set {3,4} has binary indices {{1,2},{3}}, with two choices {1,3}, {2,3}, so is not counted under a(4).
The a(0) = 1 through a(5) = 19 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{1,2} {1,2} {4} {4}
{1,3} {1,2} {1,2}
{2,3} {1,3} {1,3}
{1,4} {1,4}
{2,3} {1,5}
{2,4} {2,3}
{1,2,4} {2,4}
{1,3,4} {4,5}
{2,3,4} {1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{2,3,4}
{2,3,5}
{2,4,5}
{3,4,5}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], Length[Union[Sort /@ Select[Tuples[bpe/@#], UnsameQ@@#&]]]==1&]], {n, 0, 10}]
CROSSREFS
A version for MM-numbers of multisets is A368101. Factorizations of this type are counted by A370645. A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Number of subsets of {1..n} containing n such that it is possible to choose a different binary index of each element.
+10
11
0, 1, 2, 3, 7, 10, 15, 22, 61, 81, 112, 154, 207, 276, 355, 464, 1771, 2166, 2724, 3445, 4246, 5292, 6420, 7922, 9586, 11667, 13768, 16606, 19095, 22825, 26498, 31421, 187223, 213684, 247670, 289181, 331301, 385079, 440411, 510124, 575266, 662625, 747521
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
EXAMPLE
The a(0) = 0 through a(6) = 15 subsets:
. {1} {2} {3} {4} {5} {6}
{1,2} {1,3} {1,4} {1,5} {1,6}
{2,3} {2,4} {2,5} {2,6}
{3,4} {3,5} {3,6}
{1,2,4} {4,5} {4,6}
{1,3,4} {1,2,5} {5,6}
{2,3,4} {1,3,5} {1,2,6}
{2,3,5} {1,3,6}
{2,4,5} {1,4,6}
{3,4,5} {1,5,6}
{2,3,6}
{2,5,6}
{3,4,6}
{3,5,6}
{4,5,6}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], MemberQ[#, n] && Select[Tuples[bpe/@#], UnsameQ@@#&]!={}&]], {n, 0, 10}]
CROSSREFS
Unlabeled graphs of this type are counted by A134964, complement A140637. Simple graphs not of this type are counted by A367867, covering A367868. Set systems uniquely of this type are counted by A367904, ranks A367908. Unlabeled multiset partitions of this type are A368098, complement A368097. For prime instead of binary indices we have A370586, differences of A370582. 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, A326702, A355739, A355740, A367770, A367772, A367905, A367909, A367912, A368094, A368095, A368109, A370640.
Number of subsets of {1..n} containing n such that it is not possible to choose a different binary index of each element.
+10
10
0, 0, 0, 1, 1, 6, 17, 42, 67, 175, 400, 870, 1841, 3820, 7837, 15920, 30997, 63370, 128348, 258699, 520042, 1043284, 2090732, 4186382, 8379022, 16765549, 33540664, 67092258, 134198633, 268412631, 536844414, 1073710403, 2147296425, 4294753612, 8589686922, 17179580003
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
EXAMPLE
The binary indices of {1,4,5} are {{1},{3},{1,3}}, from which it is not possible to choose three different elements, so S is counted under a(3).
The binary indices of S = {1,6,8,9} are {{1},{2,3},{4},{1,4}}, from which it is not possible to choose four different elements, so S is counted under a(9).
The a(0) = 0 through a(6) = 17 subsets:
. . . {1,2,3} {1,2,3,4} {1,4,5} {2,4,6}
{1,2,3,5} {1,2,3,6}
{1,2,4,5} {1,2,4,6}
{1,3,4,5} {1,2,5,6}
{2,3,4,5} {1,3,4,6}
{1,2,3,4,5} {1,3,5,6}
{1,4,5,6}
{2,3,4,6}
{2,3,5,6}
{2,4,5,6}
{3,4,5,6}
{1,2,3,4,6}
{1,2,3,5,6}
{1,2,4,5,6}
{1,3,4,5,6}
{2,3,4,5,6}
{1,2,3,4,5,6}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], MemberQ[#, n] && Select[Tuples[bpe/@#], UnsameQ@@#&]=={}&]], {n, 0, 10}]
CROSSREFS
Simple graphs not of this type are counted by A133686, covering A367869. Unlabeled graphs of this type are counted by A140637, complement A134964. Set systems uniquely not of this type are counted by A367904, ranks A367908. Unlabeled multiset partitions of this type are A368097, complement A368098. 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, A072639, A326702, A355739, A355740, A367772, A367905, A367909, A367912, A368094, A368095, A368109, A370640.
Number of minimal subsets of {1..n} such that it is not possible to choose a different binary index of each element.
+10
9
0, 0, 0, 1, 1, 3, 9, 26, 26, 40, 82, 175, 338, 636, 1114
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
EXAMPLE
The a(0) = 0 through a(6) = 9 subsets:
. . . {1,2,3} {1,2,3} {1,2,3} {1,2,3}
{1,4,5} {1,4,5}
{2,3,4,5} {2,4,6}
{1,2,5,6}
{1,3,4,6}
{1,3,5,6}
{2,3,4,5}
{2,3,5,6}
{3,4,5,6}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
fasmin[y_]:=Complement[y, Union@@Table[Union[s, #]& /@ Rest[Subsets[Complement[Union@@y, s]]], {s, y}]];
Table[Length[fasmin[Select[Subsets[Range[n]], Select[Tuples[bpe/@#], UnsameQ@@#&]=={}&]]], {n, 0, 10}]
CROSSREFS
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
A370585 counts maximal choosable sets.
Number of maximal subsets of {1..n} containing n such that it is possible to choose a different binary index of each element.
+10
8
0, 1, 1, 2, 3, 5, 9, 15, 32, 45, 67, 98, 141, 197, 263, 358, 1201, 1493, 1920, 2482, 3123, 3967, 4884, 6137, 7584, 9369
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. Also choices of A029837(n) elements of {1..n} containing n such that it is possible to choose a different binary index of each.
EXAMPLE
The a(0) = 0 through a(7) = 15 subsets:
. {1} {1,2} {1,3} {1,2,4} {1,2,5} {1,2,6} {1,2,7}
{2,3} {1,3,4} {1,3,5} {1,3,6} {1,3,7}
{2,3,4} {2,3,5} {1,4,6} {1,4,7}
{2,4,5} {1,5,6} {1,5,7}
{3,4,5} {2,3,6} {1,6,7}
{2,5,6} {2,3,7}
{3,4,6} {2,4,7}
{3,5,6} {2,5,7}
{4,5,6} {2,6,7}
{3,4,7}
{3,5,7}
{3,6,7}
{4,5,7}
{4,6,7}
{5,6,7}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n], {IntegerLength[n, 2]}], MemberQ[#, n] && Length[Union[Sort/@Select[Tuples[bpe/@#], UnsameQ@@#&]]]>0&]], {n, 0, 25}]
CROSSREFS
A version for set-systems is A368601. Without requiring n we have A370640. A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Number of minimal subsets of {2..n} such that it is not possible to choose a different binary index of each element.
+10
6
0, 0, 0, 0, 0, 1, 4, 13, 13, 26, 56, 126, 243, 471, 812, 1438
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
EXAMPLE
The a(0) = 0 through a(7) = 13 subsets:
. . . . . {2,3,4,5} {2,4,6} {2,4,6}
{2,3,4,5} {2,3,4,5}
{2,3,5,6} {2,3,4,7}
{3,4,5,6} {2,3,5,6}
{2,3,5,7}
{2,3,6,7}
{2,4,5,7}
{2,5,6,7}
{3,4,5,6}
{3,4,5,7}
{3,4,6,7}
{3,5,6,7}
{4,5,6,7}
The a(0) = 0 through a(7) = 13 set-systems:
. . . . . {2}{12}{3}{13} {2}{3}{23} {2}{3}{23}
{2}{12}{3}{13} {2}{12}{3}{13}
{12}{3}{13}{23} {12}{3}{13}{23}
{2}{12}{13}{23} {2}{12}{13}{23}
{2}{12}{3}{123}
{2}{3}{13}{123}
{12}{3}{13}{123}
{12}{3}{23}{123}
{2}{12}{13}{123}
{2}{12}{23}{123}
{2}{13}{23}{123}
{3}{13}{23}{123}
{12}{13}{23}{123}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
fasmin[y_]:=Complement[y, Union@@Table[Union[s, #]& /@ Rest[Subsets[Complement[Union@@y, s]]], {s, y}]];
Table[Length[fasmin[Select[Subsets[Range[2, n]], Select[Tuples[bpe/@#], UnsameQ@@#&]=={}&]]], {n, 0, 10}]
CROSSREFS
This is the minimal case of A370643. A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A370585 counts maximal choosable sets.
Cf. A072639, A140637, A326031, A355529, A367905, A368109, A370589, A370591, A370636, A370639, A370640.
a(n) is the number of Q-bases which can be built from the set {log(1),...,log(n)}.
+10
5
1, 1, 1, 2, 2, 5, 5, 7, 11, 25, 25, 38, 38, 84, 150, 178, 178, 235, 235, 341, 578, 1233, 1233, 1521, 1966, 4156, 4820, 6832, 6832, 8952, 8952, 9824, 15926, 33256, 47732, 54488, 54488, 113388, 181728, 218592, 218592, 279348, 279348, 388576, 467028, 966700, 966700
COMMENTS
The real numbers log(p_1),...,log(p_r) where p_i is the i-th prime are known to be linearly independent over the rationals Q. Hence, for the numbers {log(1),...,log(n)}, where pi(n) = r, those numbers log(p_i) form a Q-basis of V_n:= <log(1),...,log(n)> = the Q-vector space generated by {log(1),...,log(n)}. This sequence a(n) counts the different Q-bases of V_n which can be build from the vectors of the set {log(1),...,log(n)}.
First differs from A370585 at A370585(21) = 579, a(21) = 578. The difference is due to the set {10,11,13,14,15,17,19,21}, which is not a basis because log(10) + log(21) = log(14) + log(15). - Gus Wiseman, Mar 13 2024
FORMULA
a(p) = a(p-1) for any prime number p. - Rémy Sigrist, May 09 2019
EXAMPLE
[{}] -> For n = 1, we have 1 = a(1) bases; we count {} as a basis for V_0 = {0};
[{2}] -> for n = 2, we have 1 = a(2) basis, which is {2};
[{2, 3}] -> for n = 3, we have 1 = a(3) basis, which is {2,3};
[{2, 3}, {3, 4}] -> for n = 4 we have 2 = a(4) bases, which are {2,3},{3,4};
[{2, 3, 5}, {3, 4, 5}] -> a(5) = 2;
[{2, 3, 5}, {2, 5, 6}, {3, 4, 5}, {3, 5, 6}, {4, 5, 6}] -> a(6) = 5;
[{2, 3, 5, 7}, {2, 5, 6, 7}, {3, 4, 5, 7}, {3, 5, 6, 7}, {4, 5, 6, 7}] -> a(7) = 5.
PROG
(Sage)
MAXN=100
def Log(a, N=MAXN):
return vector([valuation(a, p) for p in primes(N)])
def allBases(n, N=MAXN):
M = matrix([Log(n, N=N) for n in range(1, n+1)], ring=QQ)
r = M.rank()
rr = Set(range(1, n+1))
ll = []
for S in rr.subsets(r):
M = matrix([Log(k, N=N) for k in S])
if M.rank()==r:
ll.append(S)
return ll
[len(allBases(k)) for k in range(1, 12)]
CROSSREFS
A370585 counts maximal factor-choosable subsets.
Search completed in 0.014 seconds
|