A290689
Number of transitive rooted trees with n nodes.
Original entry on oeis.org
1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 143, 229, 370, 592, 955, 1527, 2457, 3929, 6304, 10081
Offset: 1
The a(7) = 8 7-node transitive rooted trees are: (o(oooo)), (oo(ooo)), (o(o)((o))), (o(o)(oo)), (ooo(oo)), (oo(o)(o)), (oooo(o)), (oooooo).
-
nn=18;
rtall[n_]:=If[n===1,{{}},Module[{cas},Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])]]];
Table[Length[Select[rtall[n],Complement[Union@@#,#]==={}&]],{n,nn}]
A364914
Number of subsets of {1..n} such that some element can be written as a nonnegative linear combination of the others.
Original entry on oeis.org
0, 0, 1, 3, 9, 20, 48, 101, 219, 454, 944, 1917, 3925, 7915, 16004, 32188, 64751, 129822, 260489, 521672, 1045060, 2091808, 4187047, 8377255, 16762285, 33531228, 67077485, 134170217, 268371678, 536772231, 1073611321, 2147282291, 4294697258, 8589527163, 17179321094
Offset: 0
The set {3,4,5,17} has 17 = 1*3 + 1*4 + 2*5, so is counted under a(17).
The a(0) = 0 through a(5) = 20 subsets:
. . {1,2} {1,2} {1,2} {1,2}
{1,3} {1,3} {1,3}
{1,2,3} {1,4} {1,4}
{2,4} {1,5}
{1,2,3} {2,4}
{1,2,4} {1,2,3}
{1,3,4} {1,2,4}
{2,3,4} {1,2,5}
{1,2,3,4} {1,3,4}
{1,3,5}
{1,4,5}
{2,3,4}
{2,3,5}
{2,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}
The binary version without re-usable parts is
A088809.
The complement without re-usable parts is
A151897.
The complement is counted by
A326083.
The version without re-usable parts is
A364534.
The version for partitions is
A364913.
Cf.
A011782,
A085489,
A103580,
A116861,
A124506,
A237113,
A237668,
A308546,
A324736,
A326020,
A326080,
A364272,
A364349,
A364756.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A364914(n):
c, mlist = 0, []
for m in range(1,n+1):
t = set()
for p in partitions(m,k=m-1):
t.add(tuple(sorted(p.keys())))
mlist.append([set(d) for d in t])
for k in range(2,n+1):
for w in combinations(range(1,n+1),k):
ws = set(w)
for d in w:
for s in mlist[d-1]:
if s <= ws:
c += 1
break
else:
continue
break
return c # Chai Wah Wu, Nov 17 2023
A365046
Number of subsets of {1..n} containing n such that some element can be written as a nonnegative linear combination of the others.
Original entry on oeis.org
0, 0, 1, 2, 6, 11, 28, 53, 118, 235, 490, 973, 2008, 3990, 8089, 16184, 32563, 65071, 130667, 261183, 523388, 1046748, 2095239, 4190208, 8385030, 16768943, 33546257, 67092732, 134201461, 268400553, 536839090, 1073670970, 2147414967, 4294829905, 8589793931
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
. . {1,2} {1,3} {1,4} {1,5}
{1,2,3} {2,4} {1,2,5}
{1,2,4} {1,3,5}
{1,3,4} {1,4,5}
{2,3,4} {2,3,5}
{1,2,3,4} {2,4,5}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
The positive complement is counted by
A365045, first differences of
A365044.
Without re-usable parts we have
A365069, first differences of
A364534.
A364350 counts combination-free strict partitions, complement
A364839.
A085489 and
A364755 count subsets without the sum of two distinct elements.
A088809 and
A364756 count subsets with the sum of two distinct elements.
A364913 counts combination-full partitions.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Or@@Table[combs[#[[k]],Union[Delete[#,k]]]!={},{k,Length[#]}]&]],{n,0,10}]
A325702
Number of integer partitions of n containing their multiset of multiplicities (as a submultiset).
Original entry on oeis.org
1, 1, 0, 0, 2, 1, 2, 1, 3, 3, 8, 7, 10, 13, 17, 19, 28, 35, 38, 51, 67, 81, 100, 128, 157, 195, 233, 285, 348, 427, 506, 613, 733, 873, 1063, 1263, 1503, 1802, 2131, 2537, 3005, 3565, 4171, 4922, 5820, 6775, 8001, 9333, 10860, 12739, 14840, 17206, 20029, 23248
Offset: 0
The partition x = (4,3,1,1,1) has multiplicities (3,1,1), which are a submultiset of x, so x is counted under a(10).
The a(1) = 1 through a(11) = 7 partitions:
(1) (22) (221) (2211) (3211) (4211) (333) (3322) (7211)
(211) (3111) (32111) (5211) (3331) (33221)
(41111) (32211) (6211) (52211)
(42211) (53111)
(43111) (322211)
(322111) (332111)
(421111) (431111)
(511111)
Cf.
A000041,
A181819,
A225486,
A290689,
A290822,
A304360,
A323014,
A324736,
A324748,
A324753,
A324843,
A325254,
A325755.
-
submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap]
Table[Length[Select[IntegerPartitions[n],submultQ[Sort[Length/@Split[#]],#]&]],{n,0,30}]
A324741
Number of subsets of {1...n} containing no prime indices of the elements.
Original entry on oeis.org
1, 2, 3, 5, 8, 13, 19, 30, 54, 96, 156, 248, 440, 688, 1120, 1864, 3664, 5856, 11232, 16896, 31296, 53952, 91008, 137472, 270528, 516720, 863088, 1710816, 3173856, 4836672, 9329472, 14897376, 29788128, 52256448, 88429248, 166037184, 331648704, 497685888, 829449600
Offset: 0
The a(0) = 1 through a(6) = 19 subsets:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{1,3} {4} {4} {4}
{1,3} {5} {5}
{2,4} {1,3} {6}
{3,4} {1,5} {1,3}
{2,4} {1,5}
{2,5} {2,4}
{3,4} {2,5}
{4,5} {3,4}
{2,4,5} {3,6}
{4,5}
{4,6}
{5,6}
{2,4,5}
{3,4,6}
{4,5,6}
An example for n = 20 is {5,6,7,9,10,12,14,15,16,19,20}, with prime indices:
5: {3}
6: {1,2}
7: {4}
9: {2,2}
10: {1,3}
12: {1,1,2}
14: {1,4}
15: {2,3}
16: {1,1,1,1}
19: {8}
20: {1,1,3}
None of these prime indices {1,2,3,4,8} belong to the subset, as required.
The maximal case is
A324743. The strict integer partition version is
A324751. The integer partition version is
A324756. The Heinz number version is
A324758. An infinite version is
A304360.
Cf.
A000720,
A001462,
A007097,
A076078,
A084422,
A112798,
A276625,
A279861,
A290689,
A290822,
A304360,
A306844.
-
Table[Length[Select[Subsets[Range[n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]],{n,0,10}]
-
pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(!bitand(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019
A365043
Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.
Original entry on oeis.org
0, 0, 1, 3, 7, 12, 21, 32, 49, 70, 99, 135, 185, 245, 323, 418, 541, 688, 873, 1094, 1368, 1693, 2092, 2564, 3138, 3810, 4620, 5565, 6696, 8012, 9569, 11381, 13518, 15980, 18872, 22194, 26075, 30535, 35711, 41627, 48473, 56290, 65283, 75533, 87298, 100631, 115911, 133219
Offset: 0
The subset S = {3,4,9} has 9 = 3*3 + 0*4, but this is not strictly positive, so S is not counted under a(9).
The subset S = {3,4,10} has 10 = 2*3 + 1*4, so S is counted under a(10).
The a(0) = 0 through a(5) = 12 subsets:
. . {1,2} {1,2} {1,2} {1,2}
{1,3} {1,3} {1,3}
{1,2,3} {1,4} {1,4}
{2,4} {1,5}
{1,2,3} {2,4}
{1,2,4} {1,2,3}
{1,3,4} {1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{1,4,5}
{2,3,5}
A085489 and
A364755 count subsets with no sum of two distinct elements.
A088809 and
A364756 count subsets with some sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n]]],combp[Last[#],Union[Most[#]]]!={}&]],{n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365043(n):
mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
return sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023
A324743
Number of maximal subsets of {1...n} containing no prime indices of the elements.
Original entry on oeis.org
1, 1, 2, 2, 3, 4, 5, 8, 8, 8, 8, 12, 12, 18, 18, 19, 19, 30, 30, 54, 54, 54, 54, 96, 96, 96, 96, 96, 96, 156, 156, 244, 244, 248, 248, 248, 248, 440, 440, 440, 440, 688, 688, 1120, 1120, 1120, 1120, 1864, 1864, 1864, 1864, 1864, 1864, 3664, 3664, 3664, 3664, 3664
Offset: 0
The a(0) = 1 through a(8) = 8 maximal subsets:
{} {1} {1} {2} {1,3} {1,3} {1,3} {1,3,7} {1,3,7}
{2} {1,3} {2,4} {1,5} {1,5} {1,5,7} {1,5,7}
{3,4} {3,4} {2,4,5} {2,4,5} {2,4,5,8}
{2,4,5} {3,4,6} {2,5,7} {2,5,7,8}
{4,5,6} {3,4,6} {3,4,6,8}
{3,6,7} {3,6,7,8}
{4,5,6} {4,5,6,8}
{5,6,7} {5,6,7,8}
An example for n = 15 is {1,5,7,9,13,15}, with prime indices:
1: {}
5: {3}
7: {4}
9: {2,2}
13: {6}
15: {2,3}
None of these prime indices {2,3,4,6} belong to the subset, as required.
The non-maximal case is
A324741. The case for subsets of {2...n} is
A324763.
Cf.
A000720,
A001462,
A007097,
A084422,
A085945,
A112798,
A276625,
A290689,
A290822,
A304360,
A306844,
A320426,
A324764.
-
maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]]],{n,0,10}]
-
pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n, k, pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=my(e=0); forstep(k=#p, 1, -1, if(bittest(b,k), e=bitor(e,p[k]), if(!bittest(e,k) && !bitand(p[k], b), return(0)) )); 1);
((k, b)->if(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 26 2019
A324753
Number of integer partitions of n containing all prime indices of their parts.
Original entry on oeis.org
1, 1, 1, 2, 2, 4, 5, 7, 8, 14, 16, 23, 29, 40, 49, 66, 81, 109, 133, 172, 211, 274, 332, 419, 511, 640, 775, 965, 1165, 1434, 1730, 2109, 2530, 3083, 3683, 4447, 5308, 6375, 7573, 9062, 10730, 12786, 15104, 17909, 21095, 24937, 29284, 34488, 40421, 47450
Offset: 0
The a(1) = 1 through a(8) = 8 integer partitions:
(1) (11) (21) (211) (41) (321) (421) (3221)
(111) (1111) (221) (411) (2221) (4211)
(2111) (2211) (3211) (22211)
(11111) (21111) (4111) (32111)
(111111) (22111) (41111)
(211111) (221111)
(1111111) (2111111)
(11111111)
-
Table[Length[Select[IntegerPartitions[n],SubsetQ[#,PrimePi/@First/@Join@@FactorInteger/@DeleteCases[#,1]]&]],{n,0,30}]
A065795
Number of subsets of {1,2,...,n} that contain the average of their elements.
Original entry on oeis.org
1, 2, 4, 6, 10, 16, 26, 42, 72, 124, 218, 390, 706, 1292, 2388, 4436, 8292, 15578, 29376, 55592, 105532, 200858, 383220, 732756, 1403848, 2694404, 5179938, 9973430, 19229826, 37125562, 71762396, 138871260, 269021848, 521666984, 1012520400, 1966957692, 3824240848
Offset: 1
a(4)=6, since {1}, {2}, {3}, {4}, {1,2,3} and {2,3,4} contain their averages.
From _Gus Wiseman_, Sep 14 2019: (Start)
The a(1) = 1 through a(6) = 16 subsets:
{1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{1,2,3} {4} {4} {4}
{1,2,3} {5} {5}
{2,3,4} {1,2,3} {6}
{1,3,5} {1,2,3}
{2,3,4} {1,3,5}
{3,4,5} {2,3,4}
{1,2,3,4,5} {2,4,6}
{3,4,5}
{4,5,6}
{1,2,3,6}
{1,4,5,6}
{1,2,3,4,5}
{2,3,4,5,6}
(End)
Subsets containing n whose mean is an element are
A000016.
The version for integer partitions is
A237984.
Subsets not containing their mean are
A327471.
-
Table[ Sum[a = Select[Divisors[i], OddQ[ # ] &]; Apply[ Plus, 2^(i/a) * EulerPhi[a]]/i, {i, n}]/2, {n, 34}]
(* second program *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,Mean[#]]&]],{n,0,10}] (* Gus Wiseman, Sep 14 2019 *)
-
a(n) = (1/2)*sum(i=1, n, (1/i)*sumdiv(i, d, if (d%2, 2^(i/d)*eulerphi(d)))); \\ Michel Marcus, Dec 20 2020
-
from sympy import totient, divisors
def A065795(n): return sum((sum(totient(d)<>(~k&k-1).bit_length(),generator=True))<<1)//k for k in range(1,n+1))>>1 # Chai Wah Wu, Feb 22 2023
A324744
Number of maximal subsets of {1...n} containing no element whose prime indices all belong to the subset.
Original entry on oeis.org
1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 8, 11, 11, 22, 22, 22, 22, 28, 28, 44, 44, 52, 52, 76, 76, 88, 88, 96, 96, 184, 184, 240, 240, 264, 264, 296, 296, 592, 592, 592, 592, 728, 728, 1456, 1456, 1456, 1456, 2912, 2912, 3168, 3168, 3168, 3168, 5568, 5568, 5568, 5568
Offset: 0
The a(1) = 1 through a(8) = 6 maximal subsets:
{1} {1} {2} {1,3} {1,3} {1,3,6} {3,4,6} {1,3,6,7}
{2} {1,3} {2,4} {1,5} {1,5,6} {1,3,6,7} {1,5,6,7}
{3,4} {3,4} {3,4,6} {1,5,6,7} {3,4,6,8}
{2,4,5} {2,4,5,6} {2,4,5,6} {3,6,7,8}
{2,5,6,7} {2,4,5,6,8}
{2,5,6,7,8}
The non-maximal case is
A324738. The case for subsets of {2...n} is
A324762.
Cf.
A000720,
A001462,
A007097,
A076078,
A084422,
A085945,
A112798,
A276625,
A290822,
A304360,
A306844,
A320426,
A324764.
-
maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]]],{n,0,10}]
-
pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n, k, if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=for(k=1, #p, if(!bittest(b,k) && bitnegimply(p[k], b), my(e=bitor(b, 1<#p, ismax(b), my(f=bitnegimply(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 27 2019
Showing 1-10 of 21 results.
Comments