Julian Allagan - cp's OEIS frontend

A384988 a(n) = Stirling2(n,2)^2 + Stirling2(n,3).

0, 1, 10, 55, 250, 1051, 4270, 17095, 68050, 270451, 1075030, 4276735, 17030650, 67881451, 270777790, 1080817975, 4316294050, 17244046051, 68912400550, 275457464815, 1101251874250, 4403270396251, 17607863991310, 70415790601255, 281616141147250, 1126323450484051

Offset: 1

Julian Allagan, Jun 14 2025

Also, one third of the number of proper vertex colorings of the n-complete tripartite graph using exactly 5 interchangeable colors.

The complete 3-partite graph K(n,n,n) has 3n vertices partitioned into three sets of size n each, with edges between every pair of vertices from different sets. 3*a(n) = 0 for n < 2 because we need at least 2 vertices per partition to create 5 nonempty independent sets.

			3*a(2) = 3 because K(2,2,2) can be partitioned into 5 nonempty independent sets in exactly 3 ways.

Vincenzo Librandi, Table of n, a(n) for n = 1..500
Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press.
Eric Weisstein's World of Mathematics, Complete Multipartite Graph.
Eric Weisstein's World of Mathematics, Stirling Number of the Second Kind.
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Cf. A000392, A000453, A060867, A385432.

[(6 - 3*2^(n+1) + 2*3^(n-1) + 4^n)/4: n in [1..30]]; // Vincenzo Librandi, Jul 24 2025

Table[(StirlingS2[n, 3] + StirlingS2[n, 2]^2), {n, 1, 20}]

3*a(n) = 2^(2*n - 2) + (1/2)*3^(n - 1) - 3*2^(n - 1) + 3/2 for n >= 1.
G.f.: 1/(4*(1 - 4*x)) + 1/(6*(1 - 3*x)) - 3/(2*(1 - 2*x)) + 3/(2*(1 - x)).
a(n) = A385432(n, 5) / 3 = A060867(n-1) + A000392(n).
From Stefano Spezia, Jun 14 2025: (Start)
a(n) = (6 - 3*2^(n+1) + 2*3^(n-1) + 4^n)/4.
E.g.f.: (exp(x) - 1)^2*(3*exp(2*x) + 8*exp(x) - 5)/12. (End)
a(n) = A000453(n+2) -10*A000453(n). - R. J. Mathar, Jul 20 2025

A385432 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete tripartite graph using exactly k interchangeable colors, 3 <= k <= 3*n.

Original entry on oeis.org

1, 1, 3, 3, 1, 1, 9, 30, 45, 30, 9, 1, 1, 21, 165, 598, 1032, 939, 471, 129, 18, 1, 1, 45, 750, 5655, 19653, 36465, 39250, 25560, 10278, 2545, 375, 30, 1, 1, 93, 3153, 46726, 295905, 978588, 1881306, 2232798, 1704405, 858530, 288768, 64743, 9495, 870, 45, 1, 1, 189, 12810, 364875, 3988530, 21976122, 69388462, 134794821, 1

Offset: 1

Julian Allagan, Jun 28 2025

Permuting the colors does not change the coloring. T(n,k) is the number of ways to partition the vertices of the n-complete tripartite graph into k independent sets.

			Triangle begins (n >= 1, k >= 3):
  n = 1: [1]
  n = 2: [1, 3, 3, 1]
  n = 3: [1, 9, 30, 45, 30, 9, 1]
  n = 4: [1, 21, 165, 598, 1032, 939, 471, 129, 18, 1]
  n = 5: [1, 45, 750, 5655, 19653, 36465, 39250, 25560, 10278, 2545, 375, 30, 1]
  n = 6: [1, 93, 3153, 46726, 295905, 978588, 1881306, 2232798, 1704405, 858530, 288768, 64743, 9495, 870, 45, 1]...

Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press.
Eric Weisstein's World of Mathematics, Complete Multipartite Graph.
Eric Weisstein's World of Mathematics, Stirling Number of the Second Kind.

Column k=3 is A384988.

T(n, k) = sum(j1=1, k-2, sum(j2=1, k-j1-1, my(j3 = k - j1 - j2); if(j3 >= 1, stirling(n, j1, 2)*stirling(n, j2, 2)*stirling(n, j3, 2))));
for(n=1, 8, print(vector(3*n - 2, k, T(n, k + 2))))

T(n,k)=Sum[StirlingS2[n, j1] * StirlingS2[n, j2] * StirlingS2[n, k - j1 - j2],{j1, 1, k - 2}, {j2, 1, k - j1 - 1}]

A385437 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph with a perfect matching removed using exactly k interchangeable colors, for n >= 1 and 2 <= k <= 2n.

Original entry on oeis.org

1, 2, 4, 1, 1, 10, 20, 9, 1, 1, 18, 92, 146, 80, 16, 1, 1, 35, 355, 1146, 1492, 850, 220, 25, 1, 1, 68, 1336, 7590, 17831, 19740, 11052, 3230, 490, 36, 1, 1, 133, 5026, 47278, 181251, 332039, 320763, 172788, 53417, 9520, 952, 49, 1, 1, 262, 19097, 287126, 1710016, 4809728, 7204912, 6180858, 3177106, 1003940, 196728, 23660, 1680, 64, 1

Offset: 1

Julian Allagan, Jun 28 2025

Permuting the colors does not change the coloring. T(n,k) is the number of ways to partition the vertex set of the n-complete bipartite graph with a perfect matching removed into k nonempty independent sets, for n >= 1 and 2 <= k <= 2n. T(n,2) = 1 for all n >= 1, corresponding to the partition into the two vertex sets. T(n,2n) = 1 for all n >= 1, corresponding to the partition where each vertex forms its own independent set.

			Triangle begins (n >= 1, k >= 2):
  n = 1:  [1]
  n = 2:  [2, 4, 1]
  n = 3:  [1, 10, 20, 9, 1]
  n = 4:  [1, 18, 92, 146, 80, 16, 1]
  n = 5:  [1, 35, 355, 1146, 1492, 850, 220, 25, 1]
  n = 6:  [1, 68, 1336, 7590, 17831, 19740, 11052, 3230, 490, 36, 1]
  n = 7:  [1, 133, 5026, 47278, 181251, 332039, 320763, 172788, 53417, 9520, 952, 49, 1]...
For n=2, k=3: T(2,3) = 4. The graph K_{2,2} - M has vertices {a_1, a_2, b_1, b_2} with edges {a_1,b_2}, {a_2,b_1}, {a_2,b_2}, {a_1,b_1} (assuming the perfect matching M = {{a_1,b_1}, {a_2,b_2}} is removed). The 4 ways to partition into 3 independent sets are: {{a_1},{a_2},{b_1,b_2}}, {{a_1},{b_1},{a_2,b_2}}, {{a_2},{b_2},{a_1,b_1}}, {{b_1},{b_2},{a_1,a_2}}.

Eric Weisstein's World of Mathematics, Independent Vertex Set.

T(n, k) = sum(s=0, n, binomial(n, s)*sum(j=0, k - n + s, stirling(s, j, 2)*stirling(s, k - n + s - j, 2)));
for(n=1, 10, print(vector(2*n - 1, k, T(n, k + 1))))

T(n,k) = Sum[Binomial[n, s]*Sum[StirlingS2[s, j]*StirlingS2[s, k - n + s - j], {j, 0, k - n + s}], {s, 0, n}].

A384981 Number of proper vertex colorings of the n-complete bipartite graph using exactly 5 interchangeable colors.

Original entry on oeis.org

0, 0, 6, 86, 770, 5710, 38626, 248766, 1558290, 9603470, 58604546, 355460446, 2147773810, 12945690030, 77907271266, 468366848126, 2813865797330, 16897768573390, 101444650414786, 608899287739806, 3654318951308850, 21929599650541550, 131592320786851106, 789612753560503486

Offset: 1

Julian Allagan, Jun 14 2025

The complete bipartite graph K(n,n) has 2n vertices partitioned into two sets of size n each, with edges between every pair of vertices from different sets. a(n) = 0 for n < 3 because K(n,n) with n < 3 cannot be partitioned into 5 nonempty independent sets. a(n) counts ways to create exactly 3 additional independent sets beyond the original 2-partite sets by splitting some of the 2-partite sets.

			a(3) = 6 because K(3,3) can be partitioned into 5 nonempty independent sets in exactly 6 ways.

Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Index entries for linear recurrences with constant coefficients, signature (16,-95,260,-324,144).

Column 5 of A384968.

Cf. A008277, A384980.

Table[2StirlingS2[n, 4] + 2StirlingS2[n, 3]StirlingS2[n, 2], {n, 1, 30}]

a(n) = Sum_{j = 1..4} Stirling2(n, j) * Stirling2(n, 5-j).
a(n) = 6^(n - 1) - (5/3)*2^(2*n - 2) - 2*3^(n - 1) + 2^(n + 1) - 4/3 for n >= 1.
G.f.: x*(1/(1 - 6*x) - (5/3)/(1 - 4*x) - 2/(1 - 3*x) + 4/(1 - 2*x) - (4/3)/(1 - x)).
E.g.f.: (exp(x) - 1)^3*(2*exp(3*x) + 6*exp(2*x) + 7*exp(x) - 3)/12. - Stefano Spezia, Jun 15 2025

A384980 Number of proper vertex colorings of the n-complete bipartite graph using exactly 4 interchangeable colors.

Original entry on oeis.org

0, 1, 11, 61, 275, 1141, 4571, 18061, 71075, 279781, 1103531, 4363261, 17292275, 68670421, 273152891, 1087959661, 4337751875, 17308485061, 69105848651, 276038071261, 1102994217875, 4408498475701, 17623550326811, 70462853802061, 281757339138275, 1126747061234341, 4506141224763371

Offset: 1

Julian Allagan, Jun 14 2025

The complete bipartite graph K(n,n) has 2n vertices partitioned into two sets of size n each, with edges between every pair of vertices from different sets. a(n) counts the number of proper vertex colorings using exactly 4 colors; these are also the number of 4 partitions of the vertices of the 2n vertices. a(n) = 0 for n < 2.

			a(3) = 11 because K(3,3) has vertices {a1,a2,a3,b1,b2,b3} and there are 11 ways to color properly 6 vertices using all 4 colors.

Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Column 4 of A384968.

Cf. A384981.

Table[2*StirlingS2[n, 3] + StirlingS2[n, 2]^2, {n, 1, 50}]

a(n) = 2*stirling(n,3,2) + stirling(n,2,2)^2

a(n) = Sum_{j = 1..3} Stirling2(n, j) * Stirling2(n, 4-j).
a(n)= (4^n)/4 + (3^n)/3 - 2^(n + 1) + 2.
G.f.: (1/4) * 1/(1 - 4*x) + (1/3) * 1/(1 - 3*x) - 2 * 1/(1 - 2*x) + 2 / (1 - x).
From Stefano Spezia, Jun 14 2025: (Start)
a(n) = 2 - 2^(n+2) + 3^n + 4^n.
E.g.f.: exp(x)*(2 - 4*exp(x) + exp(2*x) + exp(3*x)). (End)

A381863 Number of triples of triangles that are pairwise edge-disjoint in the complete graph K_n.

Original entry on oeis.org

120, 1575, 10080, 44380, 154000, 451990, 1170400, 2748460, 5965960, 12137125, 23383360, 43006600, 75988640, 129645740, 214472000, 345209480, 542187800, 832980995, 1254434720, 1855122500, 2698295600, 3865397250, 5460218400, 7613778900, 10490025000

Offset: 6

Julian Allagan, Mar 08 2025

			a(6) = 120 gives the number of triples of edge-disjoint triangles in K_6.

Julian Allagan, Edge-Disjoint Triangle Packings in Complete Graphs: Recurrence Relations and Closed Formulas. A revised proof version is to submitted to a Journal.

Andrew Howroyd, Table of n, a(n) for n = 6..1000
Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1).

Cf. A381862, A054647.

a[n_] := 120*Binomial[n, 6] + 735*Binomial[n, 7] + 840*Binomial[n, 8] + 280*Binomial[n, 9];
sequenceValues = Table[a[n], {n, 6, 30}]

a(n) = 120*binomial(n, 6) + 735*binomial(n, 7) + 840*binomial(n, 8) + 280*binomial(n, 9).

G.f.: 5*x^6*(24 + 75*x - 54*x^2 + 11*x^3)/(1 - x)^10.

A381862 Number of pairs of triangles that are pairwise edge-disjoint in the complete graph K_n.

Original entry on oeis.org

15, 100, 385, 1120, 2730, 5880, 11550, 21120, 36465, 60060, 95095, 145600, 216580, 314160, 445740, 620160, 847875, 1141140, 1514205, 1983520, 2567950, 3289000, 4171050, 5241600, 6531525, 8075340, 9911475, 12082560, 14635720, 17622880, 21101080, 25132800, 29786295

Offset: 5

Julian Allagan, Mar 08 2025

In other words, the number of unordered pairs of triangles that share at most 1 vertex in the complete graph K_n.

			a(5) = 15 because there are 15 unordered pairs of triangles that share 1 vertex.
a(6) = 100 = 90 + 10 because there are 90 = 15*binomial(6,5) unordered pairs of triangles that share 1 vertex and 10 = 10*binomial(6,6) unordered pairs of triangles that do not share a vertex.

Julian Allagan, Edge-Disjoint Triangle Packings in Complete Graphs: Recurrence Relations and Closed Formulas. Submitted to Journal of Integer Sequences.

Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A381863, A054647.

a[n_]:=n*(n-1)*(n-2)*(n-3)*(n-4)*(n+4)/72; Array[a,33,5] (* Stefano Spezia, Mar 09 2025 *)

def A381862(n): return n*(n*(n*(n*(n*(n-6)-5)+90)-176)+96)//72 # Chai Wah Wu, Mar 18 2025

a(n) = 10*binomial(n,6) + 3*n*binomial(n-1,4).
a(n) = n*(n-1)*(n-2)*(n-3)*(n-4)*(n+4)/72.
G.f.: 5*x^5*(3 - x)/(1 - x)^7. - Stefano Spezia, Mar 09 2025

A349418 a(n) is the Wiener index of a tridon on n vertices.

Original entry on oeis.org

16, 28, 46, 71, 104, 146, 198, 261, 336, 424, 526, 643, 776, 926, 1094, 1281, 1488, 1716, 1966, 2239, 2536, 2858, 3206, 3581, 3984, 4416, 4878, 5371, 5896, 6454, 7046, 7673, 8336, 9036, 9774, 10551, 11368, 12226, 13126, 14069, 15056, 16088, 17166, 18291, 19464, 20686

Offset: 5

Julian Allagan, Nov 16 2021

A tridon on n vertices is a caterpillar that is obtained by adding 2 distinct pendant vertices to the first (or last) internal vertex of a path on n >= 3 vertices.

			For n=5, a(5)=16 gives the Wiener index of a star graph on 5 vertices. Also, for n=6, a(6)=28 gives the Wiener index of a tridon graph on 6 vertices.
    *
*____\*____*____*
     /
    *

Cf. A349416 (broom), A349417 (sling).

Table[(1/6)*n^3 - (19/6)*n + 11, {n, 1, 100}]

a(n) = (1/6)*n^3 - (19/6)*n + 11.

A349417 a(n) is the Wiener index of a sling on n+1 vertices.

Original entry on oeis.org

9, 18, 32, 52, 79, 114, 158, 212, 277, 354, 444, 548, 667, 802, 954, 1124, 1313, 1522, 1752, 2004, 2279, 2578, 2902, 3252, 3629, 4034, 4468, 4932, 5427, 5954, 6514, 7108, 7737, 8402, 9104, 9844, 10623, 11442, 12302, 13204, 14149, 15138, 16172, 17252, 18379, 19554, 20778

Offset: 3

Julian Allagan, Nov 16 2021

A sling on n+1 vertices is a caterpillar that is obtained by adding 1 pendant vertex to the first (or last) internal vertex of a path on n >= 3 vertices.

			For n=3, a(3)=9 gives the Wiener index of a star graph on 4 vertices. For n=4, a(4)=18 gives the Wiener index of a sling graph on 5 vertices.
   *
*__\*__*__*

Cf. A349416 (broom), A349418 (tridon).

Essentially same as A005581(n)+2.

Table[n^3/6 + n^2/2 - 2n/3 + 2, {n, 3, 102}]

a(n) = n^3/6 + n^2/2 - 2n/3 + 2.

A349416 a(n) is the Wiener index of a broom on 2n vertices of which n+2 are pendant.

Original entry on oeis.org

25, 54, 100, 167, 259, 380, 534, 725, 957, 1234, 1560, 1939, 2375, 2872, 3434, 4065, 4769, 5550, 6412, 7359, 8395, 9524, 10750, 12077, 13509, 15050, 16704, 18475, 20367, 22384, 24530, 26809, 29225, 31782, 34484, 37335, 40339, 43500, 46822, 50309, 53965, 57794, 61800, 65987

Offset: 3

Julian Allagan, Nov 16 2021

A broom on 2n vertices is a caterpillar that is obtained by adding n pendant vertices to the first (or last) internal vertex of a path on n >= 3 vertices.

			For n=3 the value a(3)=25 gives the Wiener index of a star graph on 6 vertices. For n=4, a(4)=54 gives the Wiener index of a broom graph on 8 vertices (6 of which are leaves).
  *     *
   \   /
*__ \*/___*___*
    / \
   /   \
  *     *

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A349417 (sling), A349418 (tridon).

nterms=50;Table[2n^3/3+n^2/2+5n/6,{n,3,nterms+2}] (* Paolo Xausa, Nov 22 2021 *)

a(n) = 2n^3/3 + n^2/2 + 5n/6.

cp's OEIS Frontend

User: Julian Allagan

A384988 a(n) = Stirling2(n,2)^2 + Stirling2(n,3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A385432 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete tripartite graph using exactly k interchangeable colors, 3 <= k <= 3*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A385437 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph with a perfect matching removed using exactly k interchangeable colors, for n >= 1 and 2 <= k <= 2n.

Views

Author

Keywords

Comments

Examples

Links

Programs

PARI

Formula

A384981 Number of proper vertex colorings of the n-complete bipartite graph using exactly 5 interchangeable colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A384980 Number of proper vertex colorings of the n-complete bipartite graph using exactly 4 interchangeable colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A381863 Number of triples of triangles that are pairwise edge-disjoint in the complete graph K_n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A381862 Number of pairs of triangles that are pairwise edge-disjoint in the complete graph K_n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica