A290103 -id:A290103 - cp's OEIS frontend

A218970 Number of connected cyclic conjugacy classes of subgroups of the symmetric group.

1, 1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 2, 14, 3, 17, 11, 24, 10, 40, 16, 53, 35, 71, 43, 112, 68, 144, 112, 203, 152, 301, 219, 393, 342, 540, 474, 770, 661, 1022, 967, 1397, 1313, 1928, 1821, 2565, 2564, 3439, 3445, 4676, 4687, 6186, 6406, 8215, 8543, 10974, 11435

Offset: 0

Liam Naughton, Nov 26 2012

nonn

a(n) is also the number of connected partitions of n in the following sense. Given a partition of n, the vertices are the parts of the partition and two vertices are connected if and only if their gcd is greater than 1. We call a partition connected if the graph is connected.

			From _Gus Wiseman_, Dec 03 2018: (Start)
The a(12) = 14 connected integer partitions of 12:
  (12)  (6,6)   (4,4,4)  (3,3,3,3)  (4,2,2,2,2)  (2,2,2,2,2,2)
        (8,4)   (6,3,3)  (4,4,2,2)
        (9,3)   (6,4,2)  (6,2,2,2)
        (10,2)  (8,2,2)
(End)

Liam Naughton and Goetz Pfeiffer, Integer sequences realized by the subgroup pattern of the symmetric group, arXiv:1211.1911 [math.GR], 2012-2013.
Liam Naughton, CountingSubgroups.g
Liam Naughton and Goetz Pfeiffer, Tomlib, The GAP table of marks library

Cf. A018783, A200976, A286518, A286520, A290103, A304714, A304716, A305078, A305079, A322306, A322307.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c=={},s,zsm[Sort[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n],Length[zsm[#]]==1&]],{n,10}]

For n > 1, a(n) = A304716(n) - 1. - Gus Wiseman, Dec 03 2018

More terms from Gus Wiseman, Dec 03 2018

A333226 Least common multiple of the n-th composition in standard order.

Original entry on oeis.org

1, 2, 1, 3, 2, 2, 1, 4, 3, 2, 2, 3, 2, 2, 1, 5, 4, 6, 3, 6, 2, 2, 2, 4, 3, 2, 2, 3, 2, 2, 1, 6, 5, 4, 4, 3, 6, 6, 3, 4, 6, 2, 2, 6, 2, 2, 2, 5, 4, 6, 3, 6, 2, 2, 2, 4, 3, 2, 2, 3, 2, 2, 1, 7, 6, 10, 5, 12, 4, 4, 4, 12, 3, 6, 6, 3, 6, 6, 3, 10, 4, 6, 6, 6, 2, 2

Offset: 1

Gus Wiseman, Mar 26 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 version for binary indices is A271410.
The version for prime indices is A290103.
Positions of first appearances are A333225.
Let q(k) be the k-th composition in standard order:
- The terms of q(k) are row k of A066099.
- The sum of q(k) is A070939(k).
- The product of q(k) is A124758(k).
- The GCD of q(k) is A326674(k).
- The LCM of q(k) is A333226(k).
Cf. A000120, A029931, A048793, A074971, A076078, A233564, A285572, A289508, A289509, A324837, A333227, A333492.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[LCM@@stc[n],{n,100}]

A305193 Number of connected factorizations of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 5, 1, 1, 1, 4, 1, 1, 1, 2, 2, 1, 1, 7, 2, 2, 1, 2, 1, 4, 1, 4, 1, 1, 1, 3, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 10, 1, 1, 2, 2, 1, 1, 1, 7, 5, 1, 1, 3, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 12, 1, 2, 2, 5, 1, 1, 1, 4, 1

Offset: 1

Gus Wiseman, May 27 2018

nonn

Given a finite multiset S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. This sequence counts factorizations S such that G(S) is a connected graph.

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Nov 07 2018

			The a(72) = 10 factorizations:
(72),
(2*2*18), (2*3*12), (2*6*6), (3*4*6),
(2*36), (3*24), (4*18), (6*12),
(2*2*3*6).

Antti Karttunen, Table of n, a(n) for n = 1..20736
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000
Index entries for sequences computed from exponents in factorization of n

Cf. A048143, A281116, A286518, A286520, A290103, A303837, A304118, A304714, A304716, A305078, A305079, A319786.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c=={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],Length[zsm[#]]==1&]],{n,100}]

is_connected(facs) = { my(siz=length(facs)); if(1==siz,1,my(m=matrix(siz,siz,i,j,(gcd(facs[i],facs[j])!=1))^siz); for(n=1,siz,if(0==vecmin(m[n,]),return(0))); (1)); };
A305193aux(n, m, facs) = if(1==n, is_connected(Set(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs,d); s += A305193aux(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Nov 07 2018
A305193(n) = if(1==n,0,A305193aux(n, n, List([]))); \\ Antti Karttunen, Nov 07 2018

More terms from Antti Karttunen, Nov 07 2018

A320458 MM-numbers of labeled simple graphs spanning an initial interval of positive integers.

Original entry on oeis.org

1, 13, 377, 611, 1363, 1937, 2021, 2117, 16211, 17719, 26273, 27521, 44603, 56173, 58609, 83291, 91031, 91039, 99499, 141401, 143663, 146653, 147533, 153023, 159659, 167243, 170839, 203087, 237679, 243893, 265369, 271049, 276877, 290029, 301129, 315433, 467711

Offset: 1

Gus Wiseman, Oct 13 2018

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset multisystem with MM-number 78 is {{},{1},{1,2}}.

			The sequence of terms together with their multiset multisystems begins:
      1: {}
     13: {{1,2}}
    377: {{1,2},{1,3}}
    611: {{1,2},{2,3}}
   1363: {{1,3},{2,3}}
   1937: {{1,2},{3,4}}
   2021: {{1,4},{2,3}}
   2117: {{1,3},{2,4}}
  16211: {{1,2},{1,3},{1,4}}
  17719: {{1,2},{1,3},{2,3}}
  26273: {{1,2},{1,4},{2,3}}
  27521: {{1,2},{1,3},{2,4}}
  44603: {{1,2},{2,3},{2,4}}
  56173: {{1,2},{1,3},{3,4}}
  58609: {{1,3},{1,4},{2,3}}
  83291: {{1,2},{1,4},{3,4}}
  91031: {{1,3},{1,4},{2,4}}
  91039: {{1,2},{2,3},{3,4}}
  99499: {{1,3},{2,3},{2,4}}

Eric Weisstein's World of Mathematics, Simple Graph

Cf. A001222, A003963, A005117, A055932, A056239, A112798, A255906, A290103, A302242, A302478, A302491, A305052.

Cf. A320456, A320459, A320461, A320462, A320463.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
normQ[sys_]:=Or[Length[sys]==0,Union@@sys==Range[Max@@Max@@sys]];
Select[Range[10000],And[SquareFreeQ[#],normQ[primeMS/@primeMS[#]],And@@(And[SquareFreeQ[#],Length[primeMS[#]]==2]&/@primeMS[#])]&]

A305566 Number of finite sets of relatively prime positive integers > 1 with least common multiple n.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 10, 0, 2, 2, 0, 0, 10, 0, 10, 2, 2, 0, 44, 0, 2, 0, 10, 0, 84, 0, 0, 2, 2, 2, 122, 0, 2, 2, 44, 0, 84, 0, 10, 10, 2, 0, 184, 0, 10, 2, 10, 0, 44, 2, 44, 2, 2, 0, 1590, 0, 2, 10, 0, 2, 84, 0, 10, 2, 84, 0, 1156, 0, 2, 10, 10, 2

Offset: 1

Gus Wiseman, Jun 05 2018

nonn

From Robert Israel, Jun 06 2018: (Start)
a(n) depends only on the prime signature of n.
If n is in A000961, a(n)=0.
If n is in A006881, a(n)=2. (End)
If n = p^k*q, where p and q are distinct primes and k >= 1, then a(n) = 3*4^(k-1)-2^(k-1). - Robert Israel, Jun 07 2018

			The a(12) = 10 sets:
{3,4},
{2,3,4}, {2,3,12}, {3,4,6}, {3,4,12},
{2,3,4,6}, {2,3,4,12}, {2,3,6,12}, {3,4,6,12},
{2,3,4,6,12}.

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

Cf. A000961, A006881, A076078, A181819, A281116, A285572, A290103, A304818, A305563, A305564, A305565, A305567.

f:= proc(n) g(sort(map(t -> t[2],ifactors(n)[2]))) end proc:
f(1):= 0:
g:= proc(L) option remember;
  local nL, Cands, nC, Cons, i;
  nL:= nops(L);
  Cands:= [[]];
  for i from 1 to nL do
    Cands:= [seq(seq([op(s),t],t=0..L[i]),s=Cands)];
  od:
  Cands:= remove(t -> max(t)=0, Cands);
  nC:= nops(Cands);
  Cons:= [seq(select(t -> Cands[t][i]=0, {$1..nC}),i=1..nL),
          seq(select(t -> Cands[t][i]=L[i], {$1..nC}), i=1..nL)];
  h(Cons, {$1..nC})
end proc:
h:= proc(Cons, Cands)
  local t,i,Consi, Candsi;
  if Cons = [] then return 2^nops(Cands) fi;
  t:= 0;
  for i from 1 to nops(Cons[1]) do
    Consi:= map(proc(t) if member(Cons[1][i],t) then NULL else t minus Cons[1][1..i-1] fi end proc, Cons[2..-1]);
    if member({},Consi) then next fi;
    Candsi:= Cands minus Cons[1][1..i];
    t:= t + procname(Consi, Candsi)
  od;
  t
end proc:
map(f, [$1..100]); # Robert Israel, Jun 07 2018

Table[Length[Select[Subsets[Rest[Divisors[n]]],And[GCD@@#==1,LCM@@#==n]&]],{n,100}]

A320462 MM-numbers of labeled multigraphs with loops spanning an initial interval of positive integers.

Original entry on oeis.org

1, 7, 13, 49, 91, 161, 169, 299, 329, 343, 377, 611, 637, 667, 1127, 1183, 1261, 1363, 1937, 2021, 2093, 2117, 2197, 2303, 2401, 2639, 3703, 3887, 4277, 4459, 4669, 4901, 6877, 7567, 7889, 7943, 8281, 8671, 8827, 9541, 10933, 13559, 14053, 14147, 14651, 14819

Offset: 1

Gus Wiseman, Oct 13 2018

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset multisystem with MM-number 78 is {{},{1},{1,2}}.

			The sequence of terms together with their multiset multisystems begins:
     1: {}
     7: {{1,1}}
    13: {{1,2}}
    49: {{1,1},{1,1}}
    91: {{1,1},{1,2}}
   161: {{1,1},{2,2}}
   169: {{1,2},{1,2}}
   299: {{2,2},{1,2}}
   329: {{1,1},{2,3}}
   343: {{1,1},{1,1},{1,1}}
   377: {{1,2},{1,3}}
   611: {{1,2},{2,3}}
   637: {{1,1},{1,1},{1,2}}
   667: {{2,2},{1,3}}
  1127: {{1,1},{1,1},{2,2}}
  1183: {{1,1},{1,2},{1,2}}

Eric Weisstein's World of Mathematics, Simple Graph

Cf. A003963, A055932, A056239, A112798, A255906, A290103, A302242, A305052, A305078.

Cf. A320456, A320458, A320459, A320461, A320533.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
normQ[sys_]:=Or[Length[sys]==0,Union@@sys==Range[Max@@Max@@sys]];
Select[Range[10000],And[normQ[primeMS/@primeMS[#]],And@@(Length[primeMS[#]]==2&/@primeMS[#])]&]

A074971 Number of partitions of n into distinct parts of order n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 6, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 32, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 25, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 1, 24, 1, 1, 1, 2, 1, 24, 1, 1, 1, 1, 1, 12, 1, 1, 1, 3, 1, 2

Offset: 1

Vladeta Jovovic, Oct 05 2002

nonn

Order of partition is lcm of its parts.

			The a(36) = 6 partitions are (36), (18,12,6), (18,12,4,2), (18,12,3,2,1), (18,9,4,3,2), (12,9,6,4,3,2). - _Gus Wiseman_, Aug 01 2018

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A000837, A074761, A285572, A290103, A305566, A316431, A316433, A317624.

Cf. also A033630.

A074971(n) = { my(q=0); fordiv(n,i,my(p=1); fordiv(i,j,p *= (1 + 'x^j)); q += moebius(n/i)*p); polcoeff(q,n); }; \\ Antti Karttunen, Dec 19 2018

Coefficient of x^n in expansion of Sum_{i divides n} mu(n/i)*Product_{j divides i} (1+x^j).

A316429 Heinz numbers of integer partitions whose length is equal to their LCM.

Original entry on oeis.org

2, 6, 9, 20, 50, 56, 84, 125, 126, 176, 189, 196, 240, 294, 360, 416, 441, 540, 600, 624, 686, 810, 900, 936, 968, 1029, 1040, 1088, 1215, 1350, 1404, 1500, 1560, 2025, 2106, 2250, 2340, 2401, 2432, 2600, 2704, 3159, 3375, 3510, 3648, 3750, 3900, 4056, 5265

Offset: 1

Gus Wiseman, Jul 02 2018

A110295 is a subsequence.

			3750 is the Heinz number of (3,3,3,3,2,1), whose length and lcm are both 6.

David A. Corneth, Table of n, a(n) for n = 1..10822 (Terms <= 5 * 10^11)

Cf. A056239, A074761, A110295, A143773, A237984, A289508, A289509, A290103, A296150, A316413, A316428, A316430, A316431.

Select[Range[2,200],PrimeOmega[#]==LCM@@Cases[FactorInteger[#],{p_,k_}:>PrimePi[p]]&]

heinz(n) = my(f=factor(n), pr=f[,1]~,exps=f[,2], res=vector(vecsum(exps)), t=0); for(i = 1, #pr, pr[i] = primepi(pr[i]); for(j=1, exps[i],t++; res[t] = pr[i])); res
is(n) = my(h = heinz(n)); lcm(h)==#h \\ David A. Corneth, Jul 05 2018

A316432 Number of integer partitions of n whose length is equal to the GCD of all parts.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 1, 1, 2, 0, 2, 0, 3, 2, 3, 0, 5, 0, 3, 4, 5, 0, 8, 1, 6, 6, 6, 0, 11, 0, 8, 10, 8, 2, 18, 0, 9, 14, 15, 0, 19, 0, 16, 21, 11, 0, 34, 1, 16, 24, 24, 0, 30, 10, 27, 30, 14, 0, 71, 0, 15, 34, 38, 18, 47, 0, 47, 44, 36, 0, 88, 0, 18, 79, 63, 5

Offset: 1

Gus Wiseman, Jul 02 2018

nonn

			The a(24) = 8 partitions:
(14,10), (22,2),
(9,9,6), (12,9,3), (15,6,3), (18,3,3),
(8,8,4,4), (12,4,4,4).

Cf. A000837, A067538, A074761, A289508, A289509, A290103, A316429, A316430, A316431, A316433.

Table[Length[Select[IntegerPartitions[n],GCD@@#==Length[#]&]],{n,30}]

a(n) = {my(nb = 0); forpart(p=n, if (gcd(p)==#p, nb++);); nb;} \\ Michel Marcus, Jul 03 2018

A328168 Numbers whose prime indices minus 1 are relatively prime.

Original entry on oeis.org

3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 35, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 65, 66, 69, 70, 72, 75, 77, 78, 81, 84, 87, 90, 91, 93, 95, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 130, 132, 133, 135, 138, 140, 141, 143, 144, 145, 147

Offset: 1

Gus Wiseman, Oct 08 2019

nonn

A multiset is relatively prime if the GCD of its elements is 1. Zeros are ignored when computing GCD, and the empty set has GCD 0.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of partitions whose parts minus one are relatively prime. The enumeration of these partitions by sum is given by A328170.

			The sequence of terms together with their prime indices begins:
    3: {2}
    6: {1,2}
    9: {2,2}
   12: {1,1,2}
   15: {2,3}
   18: {1,2,2}
   21: {2,4}
   24: {1,1,1,2}
   27: {2,2,2}
   30: {1,2,3}
   33: {2,5}
   35: {3,4}
   36: {1,1,2,2}
   39: {2,6}
   42: {1,2,4}
   45: {2,2,3}
   48: {1,1,1,1,2}
   51: {2,7}
   54: {1,2,2,2}
   57: {2,8}

Positions of 1's in A328167.
Numbers whose prime indices are relatively prime are A289509.
The version for prime indices plus 1 is A318981.
The GCD of prime indices is A289508.
Partitions whose parts minus 1 are relatively prime are A328170.
Cf. A000837, A056239, A112798, A258409, A281116, A290103, A328163, A328169.

q:= n-> igcd(map(i-> numtheory[pi](i[1])-1, ifactors(n)[2])[])=1:
select(q, [$1..150])[];  # Alois P. Heinz, Oct 13 2019

Select[Range[100],GCD@@(PrimePi/@First/@If[#==1,{},FactorInteger[#]]-1)==1&]

cp's OEIS Frontend

A218970 Number of connected cyclic conjugacy classes of subgroups of the symmetric group.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A333226 Least common multiple of the n-th composition in standard order.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A305193 Number of connected factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320458 MM-numbers of labeled simple graphs spanning an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A305566 Number of finite sets of relatively prime positive integers > 1 with least common multiple n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A320462 MM-numbers of labeled multigraphs with loops spanning an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A074971 Number of partitions of n into distinct parts of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A316429 Heinz numbers of integer partitions whose length is equal to their LCM.

Views

Author

Keywords

Comments