Displaying 1-10 of 18 results found.
Number of partitions of n into 3 or more parts.
(Formerly M1046)
+10
37
0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, 127, 168, 222, 288, 375, 480, 616, 781, 990, 1243, 1562, 1945, 2422, 2996, 3703, 4550, 5588, 6826, 8332, 10126, 12292, 14865, 17958, 21618, 25995, 31165, 37317, 44562
COMMENTS
Number of (n+1)-vertex spider graphs: trees with n+1 vertices and exactly 1 vertex of degree at least 3 (i.e. branching vertex). There is a trivial bijection with the objects described in the definition. - Emeric Deutsch, Feb 22 2014 Also the number of graphical partitions of 2n into n parts. - Gus Wiseman, Jan 08 2021
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978).
FORMULA
Let P(n,i) denote the number of partitions of n into i parts. Then a(n) = Sum_{i=3..n} P(n,i). - Thomas Wieder, Feb 01 2007
EXAMPLE
a(6)=7 because there are three partitions of n=6 with i=3 parts: [4, 1, 1], [3, 2, 1], [2, 2, 2] and two partitions with i=4 parts: [3, 1, 1, 1], [2, 2, 1, 1] and one partition with i=5 parts: [2, 1, 1, 1, 1] and one partition with i=6 parts: [1, 1, 1, 1, 1, 1].
The a(3) = 1 through a(7) = 11 graphical partitions of 2n into n parts:
(222) (2222) (22222) (222222) (2222222)
(3221) (32221) (322221) (3222221)
(33211) (332211) (3322211)
(42211) (333111) (3332111)
(422211) (4222211)
(432111) (4322111)
(522111) (4331111)
(4421111)
(5222111)
(5321111)
(6221111)
(End)
MAPLE
with(combinat);
for i from 1 to 15 do pik(i, 3) od;
pik:= proc(n::integer, k::integer)
local i, Liste, Result;
if k > n or n < 0 or k < 1 then
return fail
end if;
Result := 0;
for i from k to n do
Liste:= PartitionList(n, i);
#print(Liste);
Result := Result + nops(Liste);
end do;
return Result;
end proc;
PartitionList := proc (n, k)
# Authors: Herbert S. Wilf and Joanna Nordlicht. Source: Lecture Notes
# "East Side West Side, ..." University of Pennsylvania, USA, 2002.
# Available at: http://www.cis.upenn.edu/~wilf/lecnotes.html
# Calculates the partition of n into k parts.
# E.g. PartitionList(5, 2) --> [[4, 1], [3, 2]].
local East, West;
if n < 1 or k < 1 or n < k then
RETURN([])
elif n = 1 then
RETURN([[1]])
else if n < 2 or k < 2 or n < k then
West := []
else
West := map(proc (x) options operator, arrow;
[op(x), 1] end proc, PartitionList(n-1, k-1)) end if;
if k <= n-k then
East := map(proc (y) options operator, arrow;
map(proc (x) options operator, arrow; x+1 end proc, y) end proc, PartitionList(n-k, k))
else East := [] end if;
RETURN([op(West), op(East)])
end if;
end proc;
ZL :=[S, {S = Set(Cycle(Z), 3 <= card)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=1..41); # Zerinvary Lajos, Mar 25 2008 B:=[S, {S = Set(Sequence(Z, 1 <= card), card >=3)}, unlabelled]: seq(combstruct[count](B, size=n), n=1..41); # Zerinvary Lajos, Mar 21 2009
MATHEMATICA
Length /@ Table[Select[Partitions[n], Length[#] > 2 &], {n, 20}] (* Eric W. Weisstein, May 16 2007 *) Table[Count[Length /@ Partitions[n], _?(# > 2 &)], {n, 20}] (* Eric W. Weisstein, May 16 2017 *) Length /@ Table[IntegerPartitions[n, {3, n}], {n, 20}] (* Eric W. Weisstein, May 16 2017 *)
PROG
(PARI) a(n) = numbpart(n) - (n+2)\2; /* Joerg Arndt, Apr 03 2013 */
CROSSREFS
A008284 counts partitions by sum and length.
A027187 counts partitions of even length.
A309356 ranks simple covering graphs.
The following count vertex-degree partitions and give their Heinz numbers:
Products of distinct squarefree semiprimes.
+10
25
1, 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 60, 62, 65, 69, 74, 77, 82, 84, 85, 86, 87, 90, 91, 93, 94, 95, 106, 111, 115, 118, 119, 122, 123, 126, 129, 132, 133, 134, 140, 141, 142, 143, 145, 146, 150, 155, 156, 158, 159, 161, 166
COMMENTS
First differs from A320911 in lacking 36. 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 strict pairs (a set of edges);
(2) n can be factored into distinct squarefree semiprimes;
(3) the prime signature of n is graphical.
EXAMPLE
The sequence of terms together with their prime indices begins:
1: {} 55: {3,5} 91: {4,6}
6: {1,2} 57: {2,8} 93: {2,11}
10: {1,3} 58: {1,10} 94: {1,15}
14: {1,4} 60: {1,1,2,3} 95: {3,8}
15: {2,3} 62: {1,11} 106: {1,16}
21: {2,4} 65: {3,6} 111: {2,12}
22: {1,5} 69: {2,9} 115: {3,9}
26: {1,6} 74: {1,12} 118: {1,17}
33: {2,5} 77: {4,5} 119: {4,7}
34: {1,7} 82: {1,13} 122: {1,18}
35: {3,4} 84: {1,1,2,4} 123: {2,13}
38: {1,8} 85: {3,7} 126: {1,2,2,4}
39: {2,6} 86: {1,14} 129: {2,14}
46: {1,9} 87: {2,10} 132: {1,1,2,5}
51: {2,7} 90: {1,2,2,3} 133: {4,8}
For example, the number 1260 can be factored into distinct squarefree semiprimes in two ways, (6*10*21) or (6*14*15), so 1260 is in the sequence. The number 69300 can be factored into distinct squarefree semiprimes in seven ways:
(6*10*15*77)
(6*10*21*55)
(6*10*33*35)
(6*14*15*55)
(6*15*22*35)
(10*14*15*33)
(10*15*21*22),
so 69300 is in the sequence. A complete list of all strict factorizations of 24 is: (2*3*4), (2*12), (3*8), (4*6), (24), all of which contain at least one number that is not a squarefree semiprime, so 24 is not in the sequence.
MATHEMATICA
sqs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[sqs[n/d], Min@@#>d&]], {d, Select[Divisors[n], SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Select[Range[100], sqs[#]!={}&]
CROSSREFS
A309356 is a kind of universal embedding.
A320911 lists all (not just distinct) products of squarefree semiprimes.
A339560 counts the partitions with these Heinz numbers.
A339661 has nonzero terms at these positions.
A320656 counts factorizations into squarefree semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
The following count partitions of even length and give their Heinz numbers:
- A339560 can be partitioned into distinct strict pairs ( A339561 [this sequence]). Cf. A001055, A001221, A002100, A007717, A030229, A112798, A320655, A320893, A338899, A338903, A339563, A339659.
Number of graphical partitions (degree-vectors for simple graphs with n vertices, or possible ordered row-sum vectors for a symmetric 0-1 matrix with diagonal values 0).
(Formerly M1250)
+10
24
1, 1, 2, 4, 11, 31, 102, 342, 1213, 4361, 16016, 59348, 222117, 836315, 3166852, 12042620, 45967479, 176005709, 675759564, 2600672458, 10029832754, 38753710486, 149990133774, 581393603996, 2256710139346, 8770547818956, 34125389919850, 132919443189544, 518232001761434, 2022337118015338, 7898574056034636, 30873421455729728
COMMENTS
In other words, a(n) is the number of graphic sequences of length n, where a graphic sequence is a sequence of numbers which can be the degree sequence of some graph.
In the article by A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, "Parallel enumeration of degree sequences of simple graphs II", in Table 4 on page 260 the values a(30) = 7898574056034638 and a(31) = 30873429530206738 are incorrect due to the incorrect Gz(30) = 5876236938019300 and Gz(31) = 22974847474172100. - Wang Kai, Jun 05 2016
REFERENCES
R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978).
LINKS
Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Table of n, a(n) for n = 0..1651 (Terms 1 through 31 were computed by various authors; terms 32 through 34 by Axel Kohnert and Wang Kai; terms 35 to 79 by Wang Kai) A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae, Informatica, 4, 2 (2012), 260-288. - From N. J. A. Sloane, Feb 15 2013
FORMULA
G.f. = 1 + x + 2*x^2 + 4*x^3 + 11*x^4 + 31*x^5 + 102*x^6 + 342*x^7 + 1213*x^8 + ...
a(n) ~ c * 4^n / n^(3/4) for some constant c > 0. Computational estimates suggest c ≈ 0.099094. - Tom Johnston, Jan 18 2023
EXAMPLE
For n = 3, there are 4 different graphic sequences possible: 0 0 0; 1 1 0; 2 1 1; 2 2 2. - Daan van Berkel (daan.v.berkel.1980(AT)gmail.com), Jun 25 2010
The a(0) = 1 through a(4) = 11 sorted degree sequences:
() (0) (0,0) (0,0,0) (0,0,0,0)
(1,1) (0,1,1) (0,0,1,1)
(1,1,2) (0,1,1,2)
(2,2,2) (0,2,2,2)
(1,1,1,1)
(1,1,1,3)
(1,1,2,2)
(1,2,2,3)
(2,2,2,2)
(2,2,3,3)
(3,3,3,3)
For example, the graph {{2,3},{2,4}} has degrees (0,2,1,1), so (0,1,1,2) is counted under a(4).
(End)
MATHEMATICA
Table[Length[Union[Sort[Table[Count[Join@@#, i], {i, n}]]&/@Subsets[Subsets[Range[n], {2}]]]], {n, 0, 5}] (* Gus Wiseman, Dec 31 2020 *)
CROSSREFS
Counting the positive partitions by sum gives A000569, ranked by A320922. The covering case (no zeros) is A095268. Non-graphical partitions are counted by A339617 and ranked by A339618. A320921 counts connected graphical partitions.
A322353 counts factorizations into distinct semiprimes.
A339659 counts graphical partitions of 2n into k parts.
A339661 counts factorizations into distinct squarefree semiprimes.
EXTENSIONS
More terms from Torsten Sillke, torsten.sillke(AT)lhsystems.com, using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.
a(19) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 19 2007
a(30) and a(31) corrected by Wang Kai, Jun 05 2016
Products of distinct primes or squarefree semiprimes.
+10
23
1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 55, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 84
COMMENTS
First differs from A212167 in lacking 1080, with prime indices {1,1,1,2,2,2,3}. First differs from A335433 in lacking 72 (see example). 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 and strict pairs, i.e., into a set of half-loops and edges;
(2) n can be factored into distinct primes or squarefree semiprimes;
(3) the prime signature of n is half-loop-graphical.
EXAMPLE
The sequence of terms together with their prime indices begins:
1: {} 20: {1,1,3} 39: {2,6}
2: {1} 21: {2,4} 41: {13}
3: {2} 22: {1,5} 42: {1,2,4}
5: {3} 23: {9} 43: {14}
6: {1,2} 26: {1,6} 44: {1,1,5}
7: {4} 28: {1,1,4} 45: {2,2,3}
10: {1,3} 29: {10} 46: {1,9}
11: {5} 30: {1,2,3} 47: {15}
12: {1,1,2} 31: {11} 50: {1,3,3}
13: {6} 33: {2,5} 51: {2,7}
14: {1,4} 34: {1,7} 52: {1,1,6}
15: {2,3} 35: {3,4} 53: {16}
17: {7} 36: {1,1,2,2} 55: {3,5}
18: {1,2,2} 37: {12} 57: {2,8}
19: {8} 38: {1,8} 58: {1,10}
For example, we have 36 = (2*3*6), so 36 is in the sequence. On the other hand, a complete list of all strict factorizations of 72 is: (2*3*12), (2*4*9), (2*36), (3*4*6), (3*24), (4*18), (6*12), (8*9), (72). Since none of these consists of only primes or squarefree semiprimes, 72 is not in the sequence. A complete list of all factorizations of 1080 into primes or squarefree semiprimes is:
(2*2*2*3*3*3*5)
(2*2*2*3*3*15)
(2*2*3*3*3*10)
(2*2*3*3*5*6)
(2*2*3*6*15)
(2*3*3*6*10)
(2*3*5*6*6)
(2*6*6*15)
(3*6*6*10)
(5*6*6*6)
Since none of these is strict, 1080 is not in the sequence.
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&]}]];
Select[Range[100], sqps[#]!={}&]
CROSSREFS
See link for additional cross-references.
Allowing only primes gives A013929. Positions of positive terms in A339742. Allowing squares of primes gives the complement of A339840. Unlabeled multiset partitions of this type are counted by A339888. A002100 counts partitions into squarefree semiprimes.
A339841 have exactly one factorization into primes or semiprimes.
Cf. A001221, A005117, A028260, A030229, A050320, A112798, A309356, A320663, A320893, A320924, A338899.
Products of primes of squarefree semiprime index ( A322551).
+10
19
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
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}}.
EXAMPLE
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}}
MATHEMATICA
sqfsemiQ[n_]:=SquareFreeQ[n]&&PrimeOmega[n]==2;
Select[Range[1000], FreeQ[If[#==1, {}, FactorInteger[#]], {p_, k_}/; !sqfsemiQ[PrimePi[p]]]&]
CROSSREFS
These primes (of squarefree semiprime index) are listed by A322551. The strict (squarefree) case is A309356. The prime instead of squarefree semiprime version:
The nonprime instead of squarefree semiprime version:
The semiprime instead of squarefree semiprime version:
A002100 counts partitions into squarefree semiprimes.
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).
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).
Irregular triangle read by rows where T(n,k) is the number of graphical partitions of 2n into k parts, 0 <= k <= 2n.
+10
16
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
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.
EXAMPLE
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
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}]
CROSSREFS
A259873 is the left half of the triangle.
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:
- A321728 is conjectured to count non-half-loop-graphical partitions of n. Cf. A000219, A002100, A006881, A007717, A025065, A320656, A320894, A338914, A338916, A339561, A339661.
Products of primes of semiprime index ( A106349).
+10
15
1, 7, 13, 23, 29, 43, 47, 49, 73, 79, 91, 97, 101, 137, 139, 149, 161, 163, 167, 169, 199, 203, 227, 233, 257, 269, 271, 293, 299, 301, 313, 329, 343, 347, 373, 377, 389, 421, 439, 443, 449, 467, 487, 491, 499, 511, 529, 553, 559, 577, 607, 611, 631, 637, 647
COMMENTS
A semiprime ( A001358) is a product of any two prime numbers. Also MM-numbers of labeled multigraphs with loops (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}}.
EXAMPLE
The sequence of terms together with the corresponding multigraphs begins (A..F = 10..15):
1: 149: (34) 313: (36)
7: (11) 161: (11)(22) 329: (11)(23)
13: (12) 163: (18) 343: (11)(11)(11)
23: (22) 167: (26) 347: (29)
29: (13) 169: (12)(12) 373: (1C)
43: (14) 199: (19) 377: (12)(13)
47: (23) 203: (11)(13) 389: (45)
49: (11)(11) 227: (44) 421: (1D)
73: (24) 233: (27) 439: (37)
79: (15) 257: (35) 443: (1E)
91: (11)(12) 269: (28) 449: (2A)
97: (33) 271: (1A) 467: (46)
101: (16) 293: (1B) 487: (2B)
137: (25) 299: (12)(22) 491: (1F)
139: (17) 301: (11)(14) 499: (38)
MAPLE
N:= 1000: # for terms up to N
SP:= {}: p:= 1:
for i from 1 do
p:= nextprime(p);
if 2*p > N then break fi;
Q:= map(t -> p*t, select(isprime, {2, seq(i, i=3..min(p, N/p), 2)}));
SP:= SP union Q;
od:
SP:= sort(convert(SP, list)):
PSP:= map(ithprime, SP):
R:= {1}:
for p in PSP do
Rp:= {}:
for k from 1 while p^k <= N do
Rpk:= select(`<=`, R, N/p^k);
Rp:= Rp union map(`*`, Rpk, p^k);
od;
R:= R union Rp;
od:
MATHEMATICA
semiQ[n_]:=PrimeOmega[n]==2;
Select[Range[100], FreeQ[If[#==1, {}, FactorInteger[#]], {p_, k_}/; !semiQ[PrimePi[p]]]&]
CROSSREFS
These primes (of semiprime index) are listed by A106349. The strict (squarefree) case is A340020. The prime instead of semiprime version:
The nonprime instead of semiprime version:
The squarefree semiprime instead of semiprime version:
A006881 lists squarefree semiprimes.
A037143 lists primes and semiprimes (and 1).
A101048 counts partitions into semiprimes.
A302242 is the weight of the multiset of multisets with MM-number n.
A305079 is the number of connected components for MM-number n.
A320892 lists even-omega non-products of distinct semiprimes.
A320911 lists products of squarefree semiprimes (Heinz numbers of A338914).
A320912 lists products of distinct semiprimes (Heinz numbers of A338916).
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).
Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.
+10
14
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
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
FORMULA
a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - Tom Johnston, Jan 18 2023
EXAMPLE
a(4) = 7 because a 4-vertex graph with no isolated vertices can have degree sequence 1111, 2211, 2222, 3111, 3221, 3322 or 3333.
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)
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 *)
CROSSREFS
Counting the same partitions by sum gives A000569. Allowing isolated nodes gives A004251. Graphical partitions are ranked by A320922. A339659 is a triangle counting graphical partitions.
EXTENSIONS
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
MM-numbers of labeled graphs with half-loops, without isolated vertices.
+10
14
1, 3, 5, 11, 13, 15, 17, 29, 31, 33, 39, 41, 43, 47, 51, 55, 59, 65, 67, 73, 79, 83, 85, 87, 93, 101, 109, 123, 127, 129, 137, 139, 141, 143, 145, 149, 155, 157, 163, 165, 167, 177, 179, 187, 191, 195, 199, 201, 205, 211, 215, 219, 221, 233, 235, 237, 241, 249
COMMENTS
Here a half-loop is an edge with only one vertex, to be distinguished from a full loop, which has two equal 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}}. Also products of distinct primes whose prime indices are either themselves prime or a squarefree semiprime ( A006881).
EXAMPLE
The sequence of terms together with their corresponding multisets of multisets (edge sets) begins:
1: {} 55: {{2},{3}} 137: {{2,5}}
3: {{1}} 59: {{7}} 139: {{1,7}}
5: {{2}} 65: {{2},{1,2}} 141: {{1},{2,3}}
11: {{3}} 67: {{8}} 143: {{3},{1,2}}
13: {{1,2}} 73: {{2,4}} 145: {{2},{1,3}}
15: {{1},{2}} 79: {{1,5}} 149: {{3,4}}
17: {{4}} 83: {{9}} 155: {{2},{5}}
29: {{1,3}} 85: {{2},{4}} 157: {{12}}
31: {{5}} 87: {{1},{1,3}} 163: {{1,8}}
33: {{1},{3}} 93: {{1},{5}} 165: {{1},{2},{3}}
39: {{1},{1,2}} 101: {{1,6}} 167: {{2,6}}
41: {{6}} 109: {{10}} 177: {{1},{7}}
43: {{1,4}} 123: {{1},{6}} 179: {{13}}
47: {{2,3}} 127: {{11}} 187: {{3},{4}}
51: {{1},{4}} 129: {{1},{1,4}} 191: {{14}}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[1000], And[SquareFreeQ[#], And@@(PrimeQ[#]||(SquareFreeQ[#]&&PrimeOmega[#]==2)&/@primeMS[#])]&]
CROSSREFS
The version with full loops covering an initial interval is A320461. The case covering an initial interval is A340018. The version with full loops is A340020. A006450 lists primes of prime index.
A106349 lists primes of semiprime index.
A257994 counts prime prime indices.
A302242 is the weight of the multiset of multisets with MM-number n.
A302494 lists MM-numbers of sets of sets, with connected case A328514.
A309356 lists MM-numbers of simple graphs.
A322551 lists primes of squarefree semiprime index.
A330944 counts nonprime prime indices.
A339112 lists MM-numbers of multigraphs with loops.
A339113 lists MM-numbers of multigraphs.
Cf. A000040, A000720, A001222, A005117, A056239, A076610, A112798, A289509, A302590, A305079, A326788.
BII-numbers of simple labeled graphs.
+10
13
0, 4, 16, 20, 32, 36, 48, 52, 256, 260, 272, 276, 288, 292, 304, 308, 512, 516, 528, 532, 544, 548, 560, 564, 768, 772, 784, 788, 800, 804, 816, 820, 2048, 2052, 2064, 2068, 2080, 2084, 2096, 2100, 2304, 2308, 2320, 2324, 2336, 2340, 2352, 2356, 2560, 2564
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. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges. Also numbers whose binary indices all belong to A018900.
EXAMPLE
The sequence of all simple labeled graphs together with their BII-numbers begins:
0: {}
4: {{1,2}}
16: {{1,3}}
20: {{1,2},{1,3}}
32: {{2,3}}
36: {{1,2},{2,3}}
48: {{1,3},{2,3}}
52: {{1,2},{1,3},{2,3}}
256: {{1,4}}
260: {{1,2},{1,4}}
272: {{1,3},{1,4}}
276: {{1,2},{1,3},{1,4}}
288: {{2,3},{1,4}}
292: {{1,2},{2,3},{1,4}}
304: {{1,3},{2,3},{1,4}}
308: {{1,2},{1,3},{2,3},{1,4}}
512: {{2,4}}
516: {{1,2},{2,4}}
528: {{1,3},{2,4}}
532: {{1,2},{1,3},{2,4}}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Select[Range[0, 100], SameQ[2, ##]&@@Length/@bpe/@bpe[#]&]
CROSSREFS
Cf. A000120, A006125, A006129, A018900, A048793, A062880, A070939, A309356 (same for MM-numbers), A322551, A326031, A326702.
Search completed in 0.036 seconds
|