A352665
Maximum number of induced copies of the 4-node path in an n-node graph.
Original entry on oeis.org
0, 0, 0, 1, 5, 9, 16, 32, 48, 80, 112, 160
Offset: 1
All optimal graphs (i.e., n-node graphs having a(n) induced copies of P_4) for 4 <= n <= 9 are listed below. Since P_4 is self-complementary, the optimal graphs come in complementary pairs. Here, ECB(n_1, ..., n_k) denotes the empty cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging k clusters of n_1, ..., n_k nodes, respectively, in a cycle, and joining all pairs of nodes in neighboring clusters with edges.
n = 4: P_4 (self-complementary).
n = 5: C_5 (self-complementary).
n = 6: ECB(1, 1, 1, 1, 2) and its complement.
n = 7: 8 optimal graphs, among them ECB(1, 1, 1, 2, 2) and ECB(1, 1, 2, 1, 2), and their complements. In graph6 format, the optimal graphs are "F?o~_", "FCY^_", "FCpv?", "FCxv?", "FCxvO", "FQjRo", "FQyuo", and "FQyvO".
n = 8: The antiprism graph and its complement (the Wagner graph).
n = 9: 22 optimal graphs, among them all graphs that are supergraphs of ECB(1, 2, 2, 2, 2) and subgraphs of its complement (10 graphs altogether), and the 1-skeletons of the Johnson solids J10 (the gyroelongated square pyramid) and J51 (the triaugmented triangular prism) and their complements. In graph6 format, the optimal graphs are "H?bF`xw", "H?o}^_}", "H?o}^bp", "H?q`qjo", "H?q`v`[", "H?rF`zo", "H?rF`zq", "HCRbdO{", "HCXfczo", "HCXfczq", "HCXk~a]", "HCXk~bo", "HCXk~bp", "HCY^fXy", "HCrb`qi", "HCrb`rc", "HEhuTxm", "HEhutxm", "HQjUjqm", "HQyurjU", "HQyurji", and "HQyurzU".
- Chaim Even-Zohar and Nati Linial, A Note on the inducibility of 4-vertex graphs, Graphs and Combinatorics 31 (2015), 1367-1380; arXiv version, arXiv:1312.1205 [math.CO], 2013-2014.
- Falk Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 43e7869.
- Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.
a(10)-a(12) added using tinygraph by
Falk Hüffner, Apr 07 2022
A302647
a(n) = (2*n^2*(n^2 - 3) - (2*n^2 + 1)*(-1)^n + 1)/64.
Original entry on oeis.org
0, 0, 2, 6, 18, 36, 72, 120, 200, 300, 450, 630, 882, 1176, 1568, 2016, 2592, 3240, 4050, 4950, 6050, 7260, 8712, 10296, 12168, 14196, 16562, 19110, 22050, 25200, 28800, 32640, 36992, 41616, 46818, 52326, 58482, 64980, 72200, 79800, 88200, 97020, 106722
Offset: 1
- Eric Weisstein's World of Mathematics, Barbell Graph.
- Eric Weisstein's World of Mathematics, Graph Crossing Number.
- Index entries for linear recurrences with constant coefficients, signature (2,2,-6,0,6,-2,-2,1).
- Index entries for sequences related to partitions.
Positive terms are the third column of the triangle in
A145118.
-
[(1/2)*Floor(n/2)*(1+Floor(n/2))*(Floor(n/2)-n)*(1-n+Floor(n/2)): n in [1..45]]; // Vincenzo Librandi, Apr 11 2018
-
Table[(1/2)*Floor[n/2]*(1 + Floor[n/2])*(Floor[n/2] - n)*(1 - n + Floor[n/2]), {n, 100}]
LinearRecurrence[{2, 2, -6, 0, 6, -2, -2, 1}, {0, 0, 2, 6, 18, 36, 72, 120}, 20] (* Eric W. Weisstein, May 17 2023 *)
Table[(1 - (-1)^n - 2 (3 + (-1)^n) n^2 + 2 n^4)/64, {n, 20}] (* Eric W. Weisstein, May 17 2023 *)
CoefficientList[Series[-2 x^2 (1 + x + x^2)/((-1 + x)^5 (1 + x)^3), {x, 0, 20}], x] (* Eric W. Weisstein, May 17 2023 *)
A007333
An upper bound on the biplanar crossing number of the complete graph on n nodes.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 12, 18, 37, 53, 75, 100, 152, 198, 256, 320, 430, 530, 650, 780, 980, 1165, 1380, 1610, 1939, 2247, 2597, 2968, 3472, 3948, 4480, 5040, 5772, 6468, 7236, 8040, 9060, 10035, 11100, 12210, 13585, 14905, 16335, 17820, 19624, 21362
Offset: 1
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Colin Barker, Table of n, a(n) for n = 1..1000
- A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280.
- A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280. [Annotated scanned copy]
- Index entries for linear recurrences with constant coefficients, signature (2,-1,0,3,-6,3,0,-3,6,-3,0,1,-2,1).
-
LinearRecurrence[{2,-1,0,3,-6,3,0,-3,6,-3,0,1,-2,1},{0,0,0,0,0,0,0,0,4,7,12,18,37,53},70] (* Harvey P. Dale, Feb 13 2022 *)
-
concat([0,0,0,0,0,0,0,0], Vec(x^9*(4 - x + 2*x^2 + x^3 + x^4) / ((1 - x)^5*(1 + x)^3*(1 + x^2)^3) + O(x^40))) \\ Colin Barker, Feb 02 2020
A011845
a(n) = floor( binomial(n,8)/9).
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 18, 55, 143, 333, 715, 1430, 2701, 4862, 8398, 13996, 22610, 35530, 54479, 81719, 120175, 173586, 246675, 345345, 476905, 650325, 876525, 1168700, 1542684, 2017356, 2615091, 3362260, 4289780, 5433721, 6835972, 8544965, 10616471
Offset: 0
- Index entries for linear recurrences with constant coefficients, signature (8,-28,56,-70,56,-28,8,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,-8,28,-56,70,-56,28,-8,1).
A331575
a(n) is the number of subsets of {1..n} that contain 4 even and 4 odd numbers.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 25, 75, 225, 525, 1225, 2450, 4900, 8820, 15876, 26460, 44100, 69300, 108900, 163350, 245025, 353925, 511225, 715715, 1002001, 1366365, 1863225, 2484300, 3312400, 4331600, 5664400, 7282800, 9363600, 11860560, 15023376, 18779220, 23474025, 28997325
Offset: 0
a(9)=5 and the 5 subsets are {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,8,9}, {1,2,3,4,6,7,8,9}, {1,2,4,5,6,7,8,9}, {2,3,4,5,6,7,8,9}.
- Colin Barker, Table of n, a(n) for n = 0..1000
- Index entries for linear recurrences with constant coefficients, signature (2,6,-14,-14,42,14,-70,0,70,-14,-42,14,14,-6,-2,1).
Cf.
A288876 (even bisection, shifted).
-
[IsEven(n) select Binomial((n div 2),4)^2 else Binomial((n-1) div 2,4)*Binomial((n+1) div 2,4): n in [0..41]]; // Marius A. Burtea, Jan 21 2020
-
a:= n-> ((b, q)-> b(q, 4)*b(n-q, 4))(binomial, iquo(n, 2)):
seq(a(n), n=0..50); # Alois P. Heinz, Jan 30 2020
-
a[n_] := If[OddQ[n], Binomial[(n - 1)/2, 4]*Binomial[(n + 1)/2, 4], Binomial[n/2, 4]^2]; Array[a, 42, 0] (* Amiram Eldar, Jan 21 2020 *)
LinearRecurrence[{2,6,-14,-14,42,14,-70,0,70,-14,-42,14,14,-6,-2,1},{0,0,0,0,0,0,0,0,1,5,25,75,225,525,1225,2450},50] (* Harvey P. Dale, Jul 20 2025 *)
-
a(n) = if (n%2, binomial((n-1)/2,4)*binomial((n+1)/2,4), binomial(n/2,4)^2); \\ Michel Marcus, Jan 21 2020
-
concat([0,0,0,0,0,0,0,0], Vec(x^8*(1 + 3*x + 9*x^2 + 9*x^3 + 9*x^4 + 3*x^5 + x^6) / ((1 - x)^9*(1 + x)^7) + O(x^40))) \\ Colin Barker, Jan 21 2020
A172101
Triangle, read by rows, given by [0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, ...] DELTA [1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, ...] where DELTA is the operator defined in A084938.
Original entry on oeis.org
1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 4, 2, 1, 0, 1, 3, 6, 6, 3, 1, 0, 1, 3, 9, 9, 9, 3, 1, 0, 1, 4, 12, 18, 18, 12, 4, 1, 0, 1, 4, 16, 24, 36, 24, 16, 4, 1, 0, 1, 5, 20, 40, 60, 60, 40, 20, 5, 1, 0, 1, 5, 25, 50, 100, 100, 100, 50, 25, 5, 1, 0, 1, 6, 30, 75, 150, 200, 200, 150, 75, 30, 6, 1
Offset: 0
Triangle begins :
1;
0, 1;
0, 1, 1;
0, 1, 1, 1;
0, 1, 2, 2, 1;
0, 1, 2, 4, 2, 1;
0, 1, 3, 6, 6, 3, 1;
0, 1, 3, 9, 9, 9, 3, 1;
0, 1, 4, 12, 18, 18, 12, 4, 1;
0, 1, 4, 16, 24, 36, 24, 16, 4, 1;
0, 1, 5, 20, 40, 60, 60, 40, 20, 5, 1;
0, 1, 5, 25, 50, 100, 100, 100, 50, 25, 5, 1;
0, 1, 6, 30, 75, 150, 200, 200, 150, 75, 30, 6, 1;
-
[n eq 0 select 1 else (&*[Binomial(Floor((n-j)/2), Floor((k-j)/2)): j in [0..1]]): k in [0..n], n in [0..15]]; // G. C. Greubel, Apr 08 2022
-
T[n_, k_]:= Product[Binomial[Floor[(n-j)/2], Floor[(k-j)/2]], {j,0,1}];
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 08 2022 *)
-
def A172101(n,k):
if (n==0): return 1
else: return product(binomial( (n-j)//2, (k-j)//2 ) for j in (0..1))
flatten([[A172101(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Apr 08 2022
A303231
Total volume of all rectangular prisms with dimensions q, p+q and |q-p| such that p and q are prime, n = p+q and p < q.
Original entry on oeis.org
0, 0, 0, 0, 15, 0, 105, 80, 315, 280, 0, 168, 1287, 1232, 2145, 3136, 0, 2664, 4845, 6320, 6783, 11176, 0, 11088, 12075, 17888, 0, 14448, 0, 17640, 24273, 27776, 29667, 62560, 0, 61632, 0, 28272, 50505, 76720, 0, 99120, 68757, 141944, 79335, 163024, 0
Offset: 1
-
Table[n*Sum[(n - i) (n - 2 i) (PrimePi[i] - PrimePi[i - 1]) (PrimePi[n - i] - PrimePi[n - i - 1]), {i, Floor[(n - 1)/2]}], {n, 80}]
-
a(n) = n*sum(i=1, (n-1)\2, (n-i)*(n-2*i)*isprime(i)*isprime(n-i)); \\ Michel Marcus, Apr 21 2018
A331576
a(n) is the number of subsets of {1..n} that contain 5 even and 5 odd numbers.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 36, 126, 441, 1176, 3136, 7056, 15876, 31752, 63504, 116424, 213444, 365904, 627264, 1019304, 1656369, 2576574, 4008004, 6012006, 9018009, 13117104, 19079424, 27029184, 38291344, 53018784, 73410624, 99628704, 135210384, 180280512, 240374016, 315490896
Offset: 0
a(11)=6 and the 6 subsets are {1,2,3,4,5,6,7,8,9,10}, {1,2,3,4,5,6,7,8,10,11}, {1,2,3,4,5,6,8,9,10,11}, {1,2,3,4,6,7,8,9,10,11}, {1,2,4,5,6,7,8,9,10,11}, {2,3,4,5,6,7,8,9,10,11}.
- Colin Barker, Table of n, a(n) for n = 0..1000
- Index entries for linear recurrences with constant coefficients, signature (2,8,-18,-27,72,48,-168,-42,252,0,-252,42,168,-48,-72,27,18,-8,-2,1).
-
[IsOdd(n) select Binomial((n-1) div 2,5)*Binomial((n+1) div 2,5) else Binomial(n div 2,5)^2: n in [0..41]]; // Marius A. Burtea, Jan 21 2020
-
a:= n-> ((b, q)-> b(q, 5)*b(n-q, 5))(binomial, iquo(n, 2)):
seq(a(n), n=0..50); # Alois P. Heinz, Jan 30 2020
-
a[n_] := If[OddQ[n], Binomial[(n - 1)/2, 5]*Binomial[(n + 1)/2, 5], Binomial[n/2, 5]^2]; Array[a, 42, 0] (* Amiram Eldar, Jan 21 2020 *)
-
concat([0,0,0,0,0,0,0,0,0,0], Vec(x^10*(1 + 4*x + 16*x^2 + 24*x^3 + 36*x^4 + 24*x^5 + 16*x^6 + 4*x^7 + x^8) / ((1 - x)^11*(1 + x)^9) + O(x^40))) \\ Colin Barker, Jan 21 2020
A307891
Rectilinear crossing number A014540(n) - crossing number A000241(n) of complete graph on n nodes.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 3, 4, 9, 6, 15, 14, 21, 22, 37, 30, 53, 52, 69, 74, 102, 96
Offset: 1
For 8 nodes the crossing number is 18 and the rectilinear crossing number is 19. The difference for 8 nodes is 1. Thus a(8)=1.
Comments