cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 25 results. Next

A339656 Number of loop-graphical integer partitions of 2n.

Original entry on oeis.org

1, 2, 4, 8, 15, 28, 49, 84, 140, 229, 367, 577, 895, 1368, 2064, 3080, 4547, 6642, 9627, 13825, 19704, 27868, 39164, 54656, 75832, 104584
Offset: 0

Views

Author

Gus Wiseman, Dec 14 2020

Keywords

Comments

An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices. See A339658 for the Heinz numbers, and A339655 for the complement.
The following are equivalent characteristics for any positive integer n:
(1) the multiset of prime factors of n can be partitioned into distinct pairs, i.e., into a set of edges and loops;
(2) n can be factored into distinct semiprimes;
(3) the unordered prime signature of n is loop-graphical.

Examples

			The a(0) = 1 through a(4) = 15 partitions:
  ()  (2)    (2,2)      (3,3)          (3,3,2)
      (1,1)  (3,1)      (2,2,2)        (4,2,2)
             (2,1,1)    (3,2,1)        (4,3,1)
             (1,1,1,1)  (4,1,1)        (2,2,2,2)
                        (2,2,1,1)      (3,2,2,1)
                        (3,1,1,1)      (3,3,1,1)
                        (2,1,1,1,1)    (4,2,1,1)
                        (1,1,1,1,1,1)  (5,1,1,1)
                                       (2,2,2,1,1)
                                       (3,2,1,1,1)
                                       (4,1,1,1,1)
                                       (2,2,1,1,1,1)
                                       (3,1,1,1,1,1)
                                       (2,1,1,1,1,1,1)
                                       (1,1,1,1,1,1,1,1)
For example, there are four possible loop-graphs with degrees y = (2,2,1,1), namely
  {{1,1},{2,2},{3,4}}
  {{1,1},{2,3},{2,4}}
  {{1,2},{1,3},{2,4}}
  {{1,2},{1,4},{2,3}}
  {{1,3},{1,4},{2,2}},
so y is counted under a(3). On the other hand, there are two possible loop-multigraphs with degrees z = (4,2), namely
  {{1,1},{1,1},{2,2}}
  {{1,1},{1,2},{1,2}},
but neither of these is a loop-graph, so z is not counted under a(3).

Links

Crossrefs

A339658 ranks these partitions.
A001358 lists semiprimes, with squarefree case A006881.
A006125 counts labeled graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A062740 counts labeled connected loop-graphs.
A320461 ranks normal loop-graphs.
A320655 counts factorizations into semiprimes.
A322353 counts factorizations into distinct semiprimes.
A322661 counts covering loop-graphs.
A339845 counts the same partitions by length, or A339844 with zeros.
The following count vertex-degree partitions and give their Heinz numbers:
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A000569 counts graphical partitions (A320922).
- A058696 counts partitions of 2n (A300061).
- A209816 counts multigraphical partitions (A320924).
- A321728 is conjectured to count non-half-loop-graphical partitions of n.
- A339617 counts non-graphical partitions of 2n (A339618).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 [this sequence] counts loop-graphical partitions (A339658).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001222, A025065, A095268, A101048, A320656, A320921, A338902, A338912, A338913, A339659.

Programs

  • Mathematica
    spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]& /@spsbin[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Select[mpsbin[#],UnsameQ@@#&]!={}&]],{n,0,5}]

Formula

A058696(n) = a(n) + A339655(n).

Extensions

a(8)-a(25) from Andrew Howroyd, Jan 10 2024

A339113 Products of primes of squarefree semiprime index (A322551).

Original entry on oeis.org

1, 13, 29, 43, 47, 73, 79, 101, 137, 139, 149, 163, 167, 169, 199, 233, 257, 269, 271, 293, 313, 347, 373, 377, 389, 421, 439, 443, 449, 467, 487, 491, 499, 559, 577, 607, 611, 631, 647, 653, 673, 677, 727, 751, 757, 811, 821, 823, 829, 839, 841, 907, 929, 937
Offset: 1

Views

Author

Gus Wiseman, Mar 12 2021

Keywords

Comments

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.
Also MM-numbers of labeled multigraphs (without uncovered vertices). 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 of multisets 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 of multisets with MM-number 78 is {{},{1},{1,2}}.

Examples

			The sequence of terms together with the corresponding multigraphs begins:
      1: {}               233: {{2,7}}          487: {{2,11}}
     13: {{1,2}}          257: {{3,5}}          491: {{1,15}}
     29: {{1,3}}          269: {{2,8}}          499: {{3,8}}
     43: {{1,4}}          271: {{1,10}}         559: {{1,2},{1,4}}
     47: {{2,3}}          293: {{1,11}}         577: {{1,16}}
     73: {{2,4}}          313: {{3,6}}          607: {{2,12}}
     79: {{1,5}}          347: {{2,9}}          611: {{1,2},{2,3}}
    101: {{1,6}}          373: {{1,12}}         631: {{3,9}}
    137: {{2,5}}          377: {{1,2},{1,3}}    647: {{1,17}}
    139: {{1,7}}          389: {{4,5}}          653: {{4,7}}
    149: {{3,4}}          421: {{1,13}}         673: {{1,18}}
    163: {{1,8}}          439: {{3,7}}          677: {{2,13}}
    167: {{2,6}}          443: {{1,14}}         727: {{2,14}}
    169: {{1,2},{1,2}}    449: {{2,10}}         751: {{4,8}}
    199: {{1,9}}          467: {{4,6}}          757: {{1,19}}

Crossrefs

These primes (of squarefree semiprime index) are listed by A322551.
The strict (squarefree) case is A309356.
The prime instead of squarefree semiprime version:
primes: A006450
products: A076610
strict: A302590
The nonprime instead of squarefree semiprime version:
primes: A007821
products: A320628
odd: A320629
strict: A340104
odd strict: A340105
The semiprime instead of squarefree semiprime version:
primes: A106349
products: A339112
strict: A340020
A001358 lists semiprimes, with odd/even terms A046315/A100484.
A002100 counts partitions into squarefree semiprimes.
A005117 lists squarefree numbers.
A006881 lists squarefree semiprimes, with odd/even terms A046388/A100484.
A056239 gives the sum of prime indices, which are listed by A112798.
A302242 is the weight of the multiset of multisets with MM-number n.
A305079 is the number of connected components for MM-number n.
A320911 lists products of squarefree semiprimes (Heinz numbers of A338914).
A338899/A270650/A270652 give the prime indices of squarefree semiprimes.
A339561 lists products of distinct squarefree semiprimes (ranking: A339560).
MM-numbers: A255397 (normal), A302478 (set multisystems), A320630 (set multipartitions), A302494 (sets of sets), A305078 (connected), A316476 (antichains), A318991 (chains), A320456 (covers), A328514 (connected sets of sets), A329559 (clutters), A340019 (half-loop graphs).
Cf. A000040, A000720, A001055, A001222, A003963, A289509, A320461.

Programs

  • Mathematica
    sqfsemiQ[n_]:=SquareFreeQ[n]&&PrimeOmega[n]==2;
Select[Range[1000],FreeQ[If[#==1,{},FactorInteger[#]],{p_,k_}/;!sqfsemiQ[PrimePi[p]]]&]

A339559 Number of integer partitions of n that have an even number of parts and cannot be partitioned into distinct pairs of distinct parts, i.e., that are not the multiset union of any set of edges.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 4, 3, 7, 6, 14, 14, 23, 27, 41, 47, 70, 84, 114, 141, 190, 225, 303, 370, 475, 578, 738, 890, 1131, 1368, 1698, 2058, 2549, 3048, 3759, 4505, 5495, 6574, 7966, 9483, 11450, 13606, 16307, 19351, 23116, 27297, 32470, 38293, 45346, 53342, 62939
Offset: 0

Views

Author

Gus Wiseman, Dec 10 2020

Keywords

Comments

The multiplicities of such a partition form a non-graphical partition.

Examples

			The a(2) = 1 through a(10) = 14 partitions (empty column indicated by dot):
  11   .   22     2111   33       2221     44         3222       55
           1111          2211     4111     2222       6111       3322
                         3111     211111   3311       222111     3331
                         111111            5111       321111     4222
                                           221111     411111     4411
                                           311111     21111111   7111
                                           11111111              222211
                                                                 322111
                                                                 331111
                                                                 421111
                                                                 511111
                                                                 22111111
                                                                 31111111
                                                                 1111111111
For example, the partition y = (4,4,3,3,2,2,1,1,1,1) can be partitioned into a multiset of edges in just three ways:
  {{1,2},{1,2},{1,3},{1,4},{3,4}}
  {{1,2},{1,3},{1,3},{1,4},{2,4}}
  {{1,2},{1,3},{1,4},{1,4},{2,3}}
None of these are strict, so y is counted under a(22).

Links

Crossrefs

A320894 ranks these partitions (using Heinz numbers).
A338915 allows equal pairs (x,x).
A339560 counts the complement in even-length partitions.
A339564 counts factorizations of the same type.
A000070 counts non-multigraphical partitions of 2n, ranked by A339620.
A000569 counts graphical partitions, ranked by A320922.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A058696 counts partitions of even numbers, ranked by A300061.
A209816 counts multigraphical partitions, ranked by A320924.
A320655 counts factorizations into semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339617 counts non-graphical partitions of 2n, ranked by A339618.
A339655 counts non-loop-graphical partitions of 2n, ranked by A339657.
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001221, A005117, A007717, A025065, A030229, A089259, A292432, A320893, A338899, A338903, A339619.

Programs

  • Mathematica
    strs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strs[n/d],Min@@#>d&]],{d,Select[Rest[Divisors[n]],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];
Table[Length[Select[IntegerPartitions[n],EvenQ[Length[#]]&&strs[Times@@Prime/@#]=={}&]],{n,0,15}]

Formula

A027187(n) = a(n) + A339560(n).

Extensions

More terms from Jinyuan Wang, Feb 14 2025

A339658 Heinz numbers of loop-graphical partitions (of even numbers).

Original entry on oeis.org

1, 3, 4, 9, 10, 12, 16, 25, 27, 28, 30, 36, 40, 48, 63, 64, 70, 75, 81, 84, 88, 90, 100, 108, 112, 120, 144, 147, 160, 175, 189, 192, 196, 198, 208, 210, 220, 225, 243, 250, 252, 256, 264, 270, 280, 300, 324, 336, 343, 352, 360, 400, 432, 441, 448, 462, 468, 480
Offset: 1

Views

Author

Gus Wiseman, Dec 18 2020

Keywords

Comments

Equals the image of A181819 applied to the set of terms of A320912.
The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.
A partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices. Loop-graphical partitions are counted by A339656.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct pairs;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

Examples

			The sequence of terms > 1 together with their prime indices begins:
      3: {2}               70: {1,3,4}          192: {1,1,1,1,1,1,2}
      4: {1,1}             75: {2,3,3}          196: {1,1,4,4}
      9: {2,2}             81: {2,2,2,2}        198: {1,2,2,5}
     10: {1,3}             84: {1,1,2,4}        208: {1,1,1,1,6}
     12: {1,1,2}           88: {1,1,1,5}        210: {1,2,3,4}
     16: {1,1,1,1}         90: {1,2,2,3}        220: {1,1,3,5}
     25: {3,3}            100: {1,1,3,3}        225: {2,2,3,3}
     27: {2,2,2}          108: {1,1,2,2,2}      243: {2,2,2,2,2}
     28: {1,1,4}          112: {1,1,1,1,4}      250: {1,3,3,3}
     30: {1,2,3}          120: {1,1,1,2,3}      252: {1,1,2,2,4}
     36: {1,1,2,2}        144: {1,1,1,1,2,2}    256: {1,1,1,1,1,1,1,1}
     40: {1,1,1,3}        147: {2,4,4}          264: {1,1,1,2,5}
     48: {1,1,1,1,2}      160: {1,1,1,1,1,3}    270: {1,2,2,2,3}
     63: {2,2,4}          175: {3,3,4}          280: {1,1,1,3,4}
     64: {1,1,1,1,1,1}    189: {2,2,2,4}        300: {1,1,2,3,3}
For example, the four loop-graphs with degrees y = (3,1,1,1) are:
  {{1,1},{1,2},{3,4}}
  {{1,1},{1,3},{2,4}}
  {{1,1},{1,4},{2,3}}
  {{1,2},{1,3},{1,4}},
so the Heinz number 40 is in the sequence. On the other hand, the three loop-multigraphs with degrees y = (4,4) are
  {{1,1},{1,1},{2,2},{2,2}}
  {{1,1},{1,2},{1,2},{2,2}}
  {{1,2},{1,2},{1,2},{1,2}},
but none of these is a loop-graph, so the Heinz number 49 is not in the sequence.

Links

Crossrefs

A320912 has these prime shadows (see A181819).
A339656 counts these partitions.
A339657 ranks the complement, counted by A339655.
A001358 lists semiprimes, with squarefree case A006881.
A101048 counts partitions into semiprimes.
A320655 counts factorizations into semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A209816 counts multigraphical partitions (A320924).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A338914 can be partitioned into strict pairs (A320911).
- A338916 can be partitioned into distinct pairs (A320912).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001221, A001222, A007717, A056239, A112798, A320732, A320892, A338898, A338912, A338913, A339112.

Programs

  • Mathematica
    spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@spsbin[Range[Length[set]]]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[25],Select[mpsbin[nrmptn[#]],UnsameQ@@#&]!={}&]

Formula

A300061 = A339657 \/ A339658.

A029889 Number of graphical partitions (degree-vectors for graphs with n vertices, allowing self-loops which count as degree 1; or possible ordered row-sum vectors for a symmetric 0-1 matrix).

Original entry on oeis.org

1, 2, 5, 14, 43, 140, 476, 1664, 5939, 21518, 78876, 291784, 1087441, 4077662, 15369327, 58184110, 221104527, 842990294, 3223339023
Offset: 0

Views

Author

torsten.sillke(AT)lhsystems.com

Keywords

Comments

I call loops of degree one half-loops, so these are half-loop-graphs or graphs with half-loops. - Gus Wiseman, Dec 31 2020

Examples

			From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 14 sorted degree sequences:
  ()  (0)  (0,0)  (0,0,0)
      (1)  (1,0)  (1,0,0)
           (1,1)  (1,1,0)
           (2,1)  (2,1,0)
           (2,2)  (2,2,0)
                  (1,1,1)
                  (2,1,1)
                  (3,1,1)
                  (2,2,1)
                  (3,2,1)
                  (2,2,2)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graph
  {{1,3},{3}}
has degrees (1,0,2), so (2,1,0) is counted under a(3). The half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees (3,2,2), so (3,2,2) is counted under a(3).
(End)

References

  • R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

Links

Crossrefs

Cf. A000569, A004250, A029890, A029891.
Non-half-loop-graphical partitions are conjectured to be counted by A321728.
The covering case (no zeros) is A339843.
MM-numbers of half-loop-graphs are given by A340018 and A340019.
A004251 counts degree sequences of graphs, with covering case A095268.
A320663 counts unlabeled multiset partitions into singletons/pairs.
A339659 is a triangle counting graphical partitions.
A339844 counts degree sequences of loop-graphs, with covering case A339845.
Cf. A006125, A006129, A027187, A028260, A062740, A096373, A322661, A339560.

Programs

  • Mathematica
    Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Subsets[Subsets[Range[n],{1,2}]]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

Formula

Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.
a(n) = A029890(n) + A029891(n). - Andrew Howroyd, Apr 18 2021

Extensions

a(0) = 1 prepended by Gus Wiseman, Dec 31 2020

A339657 Heinz numbers of non-loop-graphical partitions of even numbers.

Original entry on oeis.org

7, 13, 19, 21, 22, 29, 34, 37, 39, 43, 46, 49, 52, 53, 55, 57, 61, 62, 66, 71, 76, 79, 82, 85, 87, 89, 91, 94, 101, 102, 107, 111, 113, 115, 116, 117, 118, 121, 129, 130, 131, 133, 134, 136, 138, 139, 146, 148, 151, 154, 155, 156, 159, 163, 165, 166, 169, 171
Offset: 1

Views

Author

Gus Wiseman, Dec 18 2020

Keywords

Comments

Equals the image of A181819 applied to the set of terms of A320892.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.
An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices. Loop-graphical partitions are counted by A339656, with Heinz numbers A339658.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct pairs, i.e., into a set of edges and loops;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

Examples

			The sequence of terms together with their prime indices begins:
      7: {4}         57: {2,8}      107: {28}
     13: {6}         61: {18}       111: {2,12}
     19: {8}         62: {1,11}     113: {30}
     21: {2,4}       66: {1,2,5}    115: {3,9}
     22: {1,5}       71: {20}       116: {1,1,10}
     29: {10}        76: {1,1,8}    117: {2,2,6}
     34: {1,7}       79: {22}       118: {1,17}
     37: {12}        82: {1,13}     121: {5,5}
     39: {2,6}       85: {3,7}      129: {2,14}
     43: {14}        87: {2,10}     130: {1,3,6}
     46: {1,9}       89: {24}       131: {32}
     49: {4,4}       91: {4,6}      133: {4,8}
     52: {1,1,6}     94: {1,15}     134: {1,19}
     53: {16}       101: {26}       136: {1,1,1,7}
     55: {3,5}      102: {1,2,7}    138: {1,2,9}
For example, the three loop-multigraphs with degrees y = (5,2,1) are:
  {{1,1},{1,1},{1,2},{2,3}}
  {{1,1},{1,1},{1,3},{2,2}}
  {{1,1},{1,2},{1,2},{1,3}},
but since none of these is a loop-graph (they have multiple edges), the Heinz number 66 is in the sequence.

Links

Crossrefs

A320892 has these prime shadows (see A181819).
A321728 is conjectured to be the version for half-loops {x} instead of loops {x,x}.
A339655 counts these partitions.
A339658 ranks the complement, counted by A339656.
A001358 lists semiprimes, with odd and even terms A046315 and A100484.
A006881 lists squarefree semiprimes, with odd and even terms A046388 and A100484.
A101048 counts partitions into semiprimes.
A320655 counts factorizations into semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339844 counts loop-graphical partitions by length.
factorizations of n into distinct primes or squarefree semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 counts non-loop-graphical partitions of 2n (A339657 [this sequence]).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001221, A001222, A007717, A056239, A112798, A320732, A338898, A338912, A338913, A339742, A339839.

Programs

  • Mathematica
    spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@spsbin[Range[Length[set]]]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[50],EvenQ[Length[nrmptn[#]]]&&Select[mpsbin[nrmptn[#]],UnsameQ@@#&]=={}&]

Formula

A300061 = A339657 \/ A339658.

A339620 Heinz numbers of non-multigraphical partitions of even numbers.

Original entry on oeis.org

3, 7, 10, 13, 19, 21, 22, 28, 29, 34, 37, 39, 43, 46, 52, 53, 55, 57, 61, 62, 66, 71, 76, 79, 82, 85, 87, 88, 89, 91, 94, 101, 102, 107, 111, 113, 115, 116, 117, 118, 129, 130, 131, 133, 134, 136, 138, 139, 146, 148, 151, 155, 156, 159, 163, 166, 171, 172, 173
Offset: 1

Views

Author

Gus Wiseman, Dec 18 2020

Keywords

Comments

An integer partition is non-multigraphical if it does not comprise the multiset of vertex-degrees of any multigraph (multiset of non-loop edges). Multigraphical partitions are counted by A209816, non-multigraphical partitions by A000070.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.
The following are equivalent characteristics for any positive integer n:
(1) the multiset of prime indices of n can be partitioned into strict pairs (a multiset of edges);
(2) n can be factored into squarefree semiprimes;
(3) the unordered prime signature of n is multigraphical.

Examples

			The sequence of terms together with their prime indices begins:
      3: {2}         53: {16}          94: {1,15}
      7: {4}         55: {3,5}        101: {26}
     10: {1,3}       57: {2,8}        102: {1,2,7}
     13: {6}         61: {18}         107: {28}
     19: {8}         62: {1,11}       111: {2,12}
     21: {2,4}       66: {1,2,5}      113: {30}
     22: {1,5}       71: {20}         115: {3,9}
     28: {1,1,4}     76: {1,1,8}      116: {1,1,10}
     29: {10}        79: {22}         117: {2,2,6}
     34: {1,7}       82: {1,13}       118: {1,17}
     37: {12}        85: {3,7}        129: {2,14}
     39: {2,6}       87: {2,10}       130: {1,3,6}
     43: {14}        88: {1,1,1,5}    131: {32}
     46: {1,9}       89: {24}         133: {4,8}
     52: {1,1,6}     91: {4,6}        134: {1,19}
For example, a complete lists of all loop-multigraphs with degrees (5,2,1) is:
  {{1,1},{1,1},{1,2},{2,3}}
  {{1,1},{1,1},{1,3},{2,2}}
  {{1,1},{1,2},{1,2},{1,3}},
but since none of these is a multigraph (they have loops), the Heinz number 66 belongs to the sequence.

Links

Crossrefs

A000070 counts these partitions.
A300061 is a superset.
A320891 has image under A181819 equal to this set of terms.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620 [this sequence]).
- A209816 counts multigraphical partitions (A320924).
- A147878 counts connected multigraphical partitions (A320925).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A005117, A007717, A030229, A050320, A056239, A112798, A320655, A338899, A339113, A339661.

Programs

  • Mathematica
    prpts[m_]:=If[Length[m]==0,{{}},Join@@Table[Prepend[#,ipr]&/@prpts[Fold[DeleteCases[#1,#2,{1},1]&,m,ipr]],{ipr,Select[Subsets[Union[m],{2}],MemberQ[#,m[[1]]]&]}]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],EvenQ[Length[nrmptn[#]]]&&prpts[nrmptn[#]]=={}&]

Formula

Equals A300061 \ A320924.
For all n, both A181821(a(n)) and A304660(a(n)) belong to A320891.

A339659 Irregular triangle read by rows where T(n,k) is the number of graphical partitions of 2n into k parts, 0 <= k <= 2n.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 2, 3, 2, 1, 1, 0, 0, 0, 0, 1, 4, 5, 3, 2, 1, 1, 0, 0, 0, 0, 1, 4, 7, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 4, 9, 11, 11, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 2, 11, 15, 17, 15, 11, 7, 5, 3, 2, 1, 1
Offset: 0

Views

Author

Gus Wiseman, Dec 18 2020

Keywords

Comments

Conjecture: The column sums 1, 0, 1, 2, 7, 20, 67, ... are given by A304787.
An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. Graphical partitions are counted by A000569.

Examples

			Triangle begins:
  1
  0 0 1
  0 0 0 1 1
  0 0 0 1 2 1 1
  0 0 0 0 2 3 2 1 1
  0 0 0 0 1 4 5 3 2 1 1
  0 0 0 0 1 4 7 7 5 3 2 1 1
For example, row n = 5 counts the following partitions:
  3322  22222  222211  2221111  22111111  211111111  1111111111
        32221  322111  3211111  31111111
        33211  331111  4111111
        42211  421111
               511111

Crossrefs

A000569 gives the row sums.
A004250 is the central column.
A005408 gives the row lengths.
A008284/A072233 is the version counting all partitions.
A259873 is the left half of the triangle.
A309356 is a universal embedding.
A027187 counts partitions of even length.
A339559 = partitions that cannot be partitioned into distinct strict pairs.
A339560 = partitions that can be partitioned into distinct strict pairs.
The following count vertex-degree partitions and give their Heinz numbers:
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A000569 counts graphical partitions (A320922).
- A058696 counts partitions of 2n (A300061).
- A147878 counts connected multigraphical partitions (A320925).
- A209816 counts multigraphical partitions (A320924).
- A320921 counts connected graphical partitions (A320923).
- A321728 is conjectured to count non-half-loop-graphical partitions of n.
- A339617 counts non-graphical partitions of 2n (A339618).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
Cf. A000219, A002100, A006881, A007717, A025065, A320656, A320894, A338914, A338916, A339561, A339661.

Programs

  • Mathematica
    prpts[m_]:=If[Length[m]==0,{{}},Join@@Table[Prepend[#,ipr]&/@prpts[Fold[DeleteCases[#1,#2,{1},1]&,m,ipr]],{ipr,Subsets[Union[m],{2}]}]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Length[Union[#]]==k&&Select[prpts[#],UnsameQ@@#&]!={}&]],{n,0,5},{k,0,2*n}]

A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.

Original entry on oeis.org

1, 0, 1, 2, 7, 20, 71, 240, 871, 3148, 11655, 43332, 162769, 614198, 2330537, 8875768, 33924859, 130038230, 499753855, 1924912894, 7429160296, 28723877732, 111236423288, 431403470222, 1675316535350, 6513837679610, 25354842100894, 98794053269694, 385312558571890, 1504105116253904, 5876236938019298, 22974847399695092
Offset: 0

Views

Author

Eric W. Weisstein, May 31 2004

Keywords

Comments

A002494 is the number of graphs on n nodes with no isolated points and A095268 is the number of these graphs having distinct degree sequences.
Now that more terms have been computed, we can see that this is not the self-convolution of any integer sequence. - Paul D. Hanna, Aug 18 2006
Is it true that a(n+1)/a(n) tends to 4? Is there a heuristic argument why this might be true? - Gordon F. Royle, Aug 29 2006
Previous values a(30) = 5876236938019300 from Lorand Lucz, Jul 07 2013 and a(31) = 22974847474172100 from Lorand Lucz, Sep 03 2013 are wrong. New values a(30) and a(31) independently computed Kai Wang and Axel Kohnert. - Vaclav Kotesovec, Apr 15 2016
In the article by A. Iványi, G. Gombos, L. Lucz, T. Matuszka: "Parallel enumeration of degree sequences of simple graphs II" is in the tables on pages 258 and 261 a wrong value a(31) = 22974847474172100, but in the abstract another wrong value a(31) = 22974847474172374. - Vaclav Kotesovec, Apr 15 2016
The asymptotic formula given below confirms that a(n+1)/a(n) tends to 4. - Tom Johnston, Jan 18 2023

Examples

			a(4) = 7 because a 4-vertex graph with no isolated vertices can have degree sequence 1111, 2211, 2222, 3111, 3221, 3322 or 3333.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 7 sorted degree sequences (empty column indicated by dot):
  ()  .  (1,1)  (2,1,1)  (1,1,1,1)
                (2,2,2)  (2,2,1,1)
                         (2,2,2,2)
                         (3,1,1,1)
                         (3,2,2,1)
                         (3,3,2,2)
                         (3,3,3,3)
For example, the complete graph K_4 has degrees y = (3,3,3,3), so y is counted under a(4). On the other hand, the only half-loop-graphs (up to isomorphism) with degrees y = (4,2,2,1) are: {(1),(1,2),(1,3),(1,4),(2,3)} and {(1),(2),(3),(1,2),(1,3),(1,4)}; and since neither of these is a graph (due to having half-loops), y is not counted under a(4).
(End)

Links

Crossrefs

Cf. A002494, A004250, A007721 (analog for connected graphs), A271831.
Counting the same partitions by sum gives A000569.
Allowing isolated nodes gives A004251.
The version with half-loops is A029889, with covering case A339843.
Covering simple graphs are ranked by A309356 and A320458.
Graphical partitions are ranked by A320922.
The version with loops is A339844, with covering case A339845.
A006125 counts simple graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A339659 is a triangle counting graphical partitions.
Cf. A007717, A096373, A181819, A320921, A322661, A339559, A339560.

Programs

  • Mathematica
    Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

Formula

a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - Tom Johnston, Jan 18 2023

Extensions

Edited by N. J. A. Sloane, Aug 26 2006
More terms from Gordon F. Royle, Aug 21 2006
a(21) and a(22) from Frank Ruskey, Aug 29 2006
a(23) from Frank Ruskey, Aug 31 2006
a(24)-a(29) from Matuszka Tamás, Jan 10 2013
a(30)-a(31) from articles by Kai Wang and Axel Kohnert, Apr 15 2016
a(0) = 1 and a(1) = 0 prepended by Gus Wiseman, Dec 31 2020

A339742 Number of factorizations of n into distinct primes or squarefree semiprimes.

Original entry on oeis.org

1, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 4, 1, 0, 2, 2, 2, 1, 1, 2, 2, 0, 1, 4, 1, 1, 1, 2, 1, 0, 0, 1, 2, 1, 1, 0, 2, 0, 2, 2, 1, 3, 1, 2, 1, 0, 2, 4, 1, 1, 2, 4, 1, 0, 1, 2, 1, 1, 2, 4, 1, 0, 0, 2, 1, 3, 2, 2, 2, 0, 1, 3, 2, 1, 2, 2, 2, 0, 1, 1, 1, 1, 1, 4, 1, 0, 4
Offset: 1

Views

Author

Gus Wiseman, Dec 20 2020

Keywords

Comments

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops and edges;
(2) n can be factored into distinct primes or squarefree semiprimes.

Examples

			The a(n) factorizations for n = 6, 30, 60, 210, 420 are respectively 2, 4, 3, 10, 9:
  (6)    (5*6)    (6*10)    (6*35)     (2*6*35)
  (2*3)  (2*15)   (2*5*6)   (10*21)    (5*6*14)
         (3*10)   (2*3*10)  (14*15)    (6*7*10)
         (2*3*5)            (5*6*7)    (2*10*21)
                            (2*3*35)   (2*14*15)
                            (2*5*21)   (2*5*6*7)
                            (2*7*15)   (3*10*14)
                            (3*5*14)   (2*3*5*14)
                            (3*7*10)   (2*3*7*10)
                            (2*3*5*7)

Links

Crossrefs

Dirichlet convolution of A008966 with A339661.
A008966 allows only primes.
A339661 does not allow primes, only squarefree semiprimes.
A339740 lists the positions of zeros.
A339741 lists the positions of positive terms.
A339839 allows nonsquarefree semiprimes.
A339887 is the non-strict version.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A013929 cannot be factored into distinct primes.
A293511 are a product of distinct squarefree numbers in exactly one way.
A320663 counts non-isomorphic multiset partitions into singletons or pairs.
A339840 cannot be factored into distinct primes or semiprimes.
A339841 have exactly one factorization into primes or semiprimes.
The following count factorizations:
- A001055 into all positive integers > 1.
- A050320 into squarefree numbers.
- A050326 into distinct squarefree numbers.
- A320655 into semiprimes.
- A320656 into squarefree semiprimes.
- A320732 into primes or semiprimes.
- A322353 into distinct semiprimes.
- A339742 [this sequence] into distinct primes or squarefree semiprimes.
- A339839 into distinct primes or semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A000569 counts graphical partitions (A320922).
- A058696 counts all partitions of 2n (A300061).
- A209816 counts multigraphical partitions (A320924).
- A339656 counts loop-graphical partitions (A339658).
-
The following count partitions/factorizations of even length and give their Heinz numbers:
- A027187/A339846 has no additional conditions (A028260).
- A338914/A339562 can be partitioned into edges (A320911).
- A338916/A339563 can be partitioned into distinct pairs (A320912).
- A339559/A339564 cannot be partitioned into distinct edges (A320894).
- A339560/A339619 can be partitioned into distinct edges (A339561).
Cf. A000070, A001221, A005117, A320893, A320923, A338899, A339113, A339617, A353471.

Programs

  • Mathematica
    sqps[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sqps[n/d],Min@@#>d&]],{d,Select[Divisors[n],PrimeQ[#]||SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Table[Length[sqps[n]],{n,100}]
  • PARI
    A353471(n) = (numdiv(n)==2*omega(n));
A339742(n, u=(1+n)) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (dA353471(d), s += A339742(n/d, d))); (s)); \\ Antti Karttunen, May 02 2022

Formula

a(n) = Sum_{d|n squarefree} A339661(n/d).

Extensions

More terms from Antti Karttunen, May 02 2022
Previous Showing 11-20 of 25 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.