login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A339617 Number of non-graphical integer partitions of 2n. 21
0, 1, 3, 6, 13, 25, 46, 81, 141, 234, 383, 615, 968, 1503, 2298, 3468, 5176, 7653, 11178, 16212, 23290, 33218, 46996, 66091, 92277, 128122, 176787, 242674, 331338, 450279, 608832, 819748, 1098907, 1467122, 1951020, 2584796, 3411998 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. See A209816 for multigraphical partitions, A000070 for non-multigraphical partitions. Graphical partitions are counted by A000569.

The following are equivalent characteristics for any positive integer n:

(1) the prime indices of n can be partitioned into distinct strict pairs (a set of edges);

(2) n can be factored into distinct squarefree semiprimes;

(3) the prime signature of n is graphical.

LINKS

Table of n, a(n) for n=0..36.

Eric Weisstein's World of Mathematics, Graphical partition.

FORMULA

a(n) + A000569(n) = A000041(2*n).

EXAMPLE

The a(1) = 1 through a(4) = 13 partitions:

  (2)  (4)    (6)      (8)

       (2,2)  (3,3)    (4,4)

       (3,1)  (4,2)    (5,3)

              (5,1)    (6,2)

              (3,2,1)  (7,1)

              (4,1,1)  (3,3,2)

                       (4,2,2)

                       (4,3,1)

                       (5,2,1)

                       (6,1,1)

                       (3,3,1,1)

                       (4,2,1,1)

                       (5,1,1,1)

For example, the partition (2,2,2,2) is not counted under a(4) because there are three possible graphs with the prescribed degrees:

  {{1,2},{1,3},{2,4},{3,4}}

  {{1,2},{1,4},{2,3},{3,4}}

  {{1,3},{1,4},{2,3},{2,4}}

MATHEMATICA

prptns[m_]:=Union[Sort/@If[Length[m]==0, {{}}, Join@@Table[Prepend[#, m[[ipr]]]&/@prptns[Delete[m, List/@ipr]], {ipr, Select[Prepend[{#}, 1]&/@Select[Range[2, Length[m]], m[[#]]>m[[#-1]]&], UnsameQ@@m[[#]]&]}]]];

strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];

Table[Length[Select[strnorm[2*n], Select[prptns[#], UnsameQ@@#&]=={}&]], {n, 0, 5}]

CROSSREFS

A006881 lists squarefree semiprimes.

A320656 counts factorizations into squarefree semiprimes.

A339659 counts graphical partitions of 2n into k parts.

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).

- A339656 counts loop-graphical partitions (A339658).

- A339617 [this sequence] 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, A007717, A025065, A320921, A320922, A338899, A339564, A339619, A339660, A339661.

Sequence in context: A047183 A047194 A048039 * A131913 A182808 A285461

Adjacent sequences:  A339614 A339615 A339616 * A339618 A339619 A339620

KEYWORD

nonn

AUTHOR

Gus Wiseman, Dec 13 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 04:43 EDT 2021. Contains 345157 sequences. (Running on oeis4.)