A050534 -id:A050534 - cp's OEIS frontend

A245796 T(n,k) is the number of labeled graphs of n vertices and k edges that have endpoints, where an endpoint is a vertex with degree 1.

0, 1, 3, 3, 6, 15, 16, 12, 10, 45, 110, 195, 210, 120, 20, 15, 105, 435, 1320, 2841, 4410, 4845, 3360, 1350, 300, 30, 21, 210, 1295, 5880, 19887, 51954, 106785, 171360, 208565, 186375, 120855, 56805, 19110, 4410, 630, 42

Offset: 1

Chai Wah Wu, Aug 01 2014

The length of the rows are 1,1,2,4,7,11,16,22,...: (1+(n-1)*(n-2)/2) = A152947(n).
T(n,k) = 0 if k > (n-1)*(n-2)/2 + 1.
Let j = (n-1)*(n-2)/2.  For i >=0, n >= 4+i, T(n,j-i+1) = n*(n-1)*binomial(j,i).
For k <= 3, T(n,k) is equal to the number of labeled bipartite graphs with n vertices and k edges.  In particular, T(n,1) = A000217(n-1), T(n,2) = A050534(n) and T(n,3) = A053526(n).

			Triangle starts:
..0
..1
..3......3
..6.....15.....16.....12
.10.....45....110....195....210....120.....20
.15....105....435...1320...2841...4410...4845...3360...1350....300.....30
...

Chai Wah Wu, Graphs whose normalized Laplacian matrices are separable as density matrices in quantum mechanics, arXiv:1407.5663 [quant-ph], 2014.

Sum of n-th row is A245797(n).

Cf. A000217, A050534, A053526, A152947.

A253942 a(n) = 3*binomial(n+1, 5).

Original entry on oeis.org

3, 18, 63, 168, 378, 756, 1386, 2376, 3861, 6006, 9009, 13104, 18564, 25704, 34884, 46512, 61047, 79002, 100947, 127512, 159390, 197340, 242190, 294840, 356265, 427518, 509733, 604128, 712008, 834768, 973896, 1130976, 1307691, 1505826, 1727271, 1974024, 2248194

Offset: 4

Serhat Bulut, Jan 20 2015

For a set of integers {1,2,...,n}, a(n) is the sum of the 2 smallest elements of each subset with 4 elements, which is 3*binomial(n+1, 5) (for n >= 4), hence a(n) = 3*binomial(n+1, 5) = 3*A000389(n+1).

			For A={1,2,3,4}, the only subset with 4 elements is {1,2,3,4}; sum of 2 minimum elements of this subset: a(4) = 1+2 = 3 = 3*binomial(4+1, 5).
For A={1,2,3,4,5}, the subsets with 4 elements are {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}; sum of 2 smallest elements of each subset: a(5) = (1+2)+(1+2)+(1+2)+(1+3)+(2+3) = 18 = 3*binomial(5+1, 5).

Colin Barker, Table of n, a(n) for n = 4..1000
Serhat Bulut and Oktay Erkan Temizkan, Subset Sum Problem [Dead link]
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A000389.

[3*Binomial(n+1, 5): n in [4..40]]; // Vincenzo Librandi, Feb 14 2015

a253942[n_] := Drop[Plus @@ Flatten[Part[#, 1 ;; 2] & /@ Subsets[Range@ #, {4}]] & /@ Range@ n, 3]; a253942[28] (* Michael De Vlieger, Jan 20 2015 *)
Table[3 Binomial[n + 1, 5], {n, 4, 35}] (* Vincenzo Librandi, Feb 14 2015 *)

a(n) = 3*binomial(n+1, 5); \\ Michel Marcus, Jan 20 2015

Vec(3*x^4/(x-1)^6 + O(x^100)) \\ Colin Barker, Jan 20 2015

a(n) = 3*A000389(n+1).
a(n) = (n-3)*(n-2)*(n-1)*n*(1+n)/40. - Colin Barker, Jan 20 2015
G.f.: 3*x^4 / (x-1)^6. - Colin Barker, Jan 20 2015
E.g.f.: x^4*(x+5)*exp(x)/40. - G. C. Greubel, Nov 25 2017
a(n) = Sum_{k=3..n-1} A050534(k). - Ivan N. Ianakiev, Oct 08 2023

A271023 Number T(n,k) of set partitions of [n] having exactly k pairs (i,j) with i=0, 0<=k<=n*(n-1)/2 read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 0, 1, 1, 6, 3, 4, 0, 0, 1, 1, 10, 15, 10, 10, 0, 5, 0, 0, 0, 1, 1, 15, 45, 35, 60, 0, 25, 15, 0, 0, 6, 0, 0, 0, 0, 1, 1, 21, 105, 140, 210, 105, 105, 105, 0, 35, 21, 21, 0, 0, 0, 7, 0, 0, 0, 0, 0, 1, 1, 28, 210, 476, 665, 840, 350, 700, 210

Offset: 0

Alois P. Heinz, Mar 28 2016

			T(3,0) = 1: 1|2|3.
T(3,1) = 3: 12|3, 13|2, 1|23.
T(3,3) = 1: 123.
Triangle T(n,k) begins:
  1;
  1;
  1,  1;
  1,  3,  0,  1;
  1,  6,  3,  4,  0, 0,  1;
  1, 10, 15, 10, 10, 0,  5,  0, 0, 0, 1;
  1, 15, 45, 35, 60, 0, 25, 15, 0, 0, 6, 0, 0, 0, 0, 1;

Alois P. Heinz, Rows n = 0..40, flattened

Columns k=0-2 give: A000012, A161680, A050534(n-1) for n>0.
Row sums give A000110.
Cf. A105488, A161680, A271024.

b:= proc(n, l) option remember; `if`(n=0, x^
      add(j*(j-1)/2, j=l), b(n-1, [l[], 1])+
      add(b(n-1, subsop(j=l[j]+1, l)), j=1..nops(l)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [])):
seq(T(n), n=0..10);

b[n_, l_] := b[n, l] = If[n == 0, x^Sum[j*(j-1)/2, {j, l}], b[n-1, Append[l, 1]] + Sum[b[n-1, ReplacePart[l, j -> l[[j]]+1]], {j, 1, Length[l]}]];
T[n_] := CoefficientList[b[n, {}], x];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 29 2022, after Alois P. Heinz *)

T(n,k) = A271024(n,n*(n-1)/2-k).

Sum_{k=0..n*(n-1)/2} k * T(n,k) = A105488(n+2) for n > 1.

A053528 Number of bipartite graphs with 5 edges on nodes {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 60, 1701, 14952, 81228, 331884, 1116675, 3256407, 8500734, 20306286, 45093048, 94189095, 186736368, 353904096, 644842674, 1134910242, 1936817820, 3215467584, 5207403663, 8245956642, 12793342716, 19481177100, 29161079805, 42967291185, 62393475690

Offset: 0

N. J. A. Sloane, Jan 16 2000

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.5.

T. D. Noe, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (11,-55,165,-330,462,-462,330,-165,55,-11,1).

Column k=5 of A117279.

Cf. A000217 (1 edge), A050534 (2 edges), A053526 (3 edges), A053527 (4 edges).

List([0..30], n-> Binomial(n,5)*(n^5 +5*n^4 +5*n^3 -85*n^2 -374*n -960)/32) # G. C. Greubel, May 15 2019

[Binomial(n,5)*(n^5 +5*n^4 +5*n^3 -85*n^2 -374*n -960)/32: n in [0..30]]; // G. C. Greubel, May 15 2019

Table[Binomial[n,5]*(n^5 +5*n^4 +5*n^3 -85*n^2 -374*n -960)/32, {n,0,30}] (* G. C. Greubel, May 15 2019 *)

{a(n) = binomial(n,5)*(n^5 +5*n^4 +5*n^3 -85*n^2 -374*n -960)/32}; \\ G. C. Greubel, May 15 2019

[binomial(n,5)*(n^5 +5*n^4 +5*n^3 -85*n^2 -374*n -960)/32 for n in (0..30)] # G. C. Greubel, May 15 2019

a(n) = (n-4)*(n-3)*(n-2)*(n-1)*n*(n^5 + 5*n^4 + 5*n^3 - 85*n^2 - 374*n - 960)/3840.
G.f.: x^5*(60+1041*x-459*x^2+411*x^3-129*x^4+21*x^5)/(1-x)^11. - Colin Barker, May 08 2012
E.g.f.: x^5*(1920 + 7152*x + 3280*x^2 + 560*x^3 + 40*x^4 + x^5)*exp(x)/3840. - G. C. Greubel, May 15 2019

A073278 Triangle read by rows. The triangle is constructed from the coefficients of the n-th derivative of the normal probability distribution function.

Original entry on oeis.org

1, -1, 0, 1, 0, -1, -1, 0, 3, 0, 1, 0, -6, 0, 3, -1, 0, 10, 0, -15, 0, 1, 0, -15, 0, 45, 0, -15, -1, 0, 21, 0, -105, 0, 105, 0, 1, 0, -28, 0, 210, 0, -420, 0, 105, -1, 0, 36, 0, -378, 0, 1260, 0, -945, 0, 1, 0, -45, 0, 630, 0, -3150, 0, 4725, 0, -945, -1, 0, 55, 0, -990, 0, 6930, 0, -17325, 0, 10395, 0

Offset: 0

Robert G. Wilson v, Jul 23 2002

The n-th derivative of the normal probability distribution function will be a polynomial of n degrees times f(x) of which every other term is zero.
All coefficients are triangular numbers. The second nonzero diagonal are the triangular numbers (A000217), the third nonzero diagonal are the tritriangular numbers (A050534), etc.
If r(n,x) denotes the polynomial of integer coefficients for row n, then r(n+1,x) = diff(r(n,x), x) - x*r(n, x) is the polynomial for row n+1. This gives an effective method of computing the sequence without recourse to the exp function. - Sean A. Irvine, Nov 21 2024

			f(x) = 1/Sqrt(2*Pi) * e^(-x^2 /2). The polynomial involved in the seventh derivative of the f(x)/dx is (-x^7 + 21x^5 - 105x^3 + 105x). Therefore the seventh antidiagonal reads the coefficients as -1, 0, 21, 0, -105, 0, 105.
Triangle T(n, k) starts:
[0]  1;
[1] -1, 0;
[2]  1, 0,   -1;
[3] -1, 0,   3, 0;
[4]  1, 0,  -6, 0,    3;
[5] -1, 0,  10, 0,  -15, 0;
[6]  1, 0, -15, 0,   45, 0,  -15;
[7] -1, 0,  21, 0, -105, 0,  105, 0;
[8]  1, 0, -28, 0,  210, 0, -420, 0,  105;
[9] -1, 0,  36, 0, -378, 0, 1260, 0, -945, 0;

Samuel M. Selby, Editor-in-Chief, CRC Standard Mathematical Tables, 21st Edition, 1973, pp. 582.

Cf. A000085.

y = E^(-x^2/2); Flatten[ Table[ Reverse[ CoefficientList[ Dt[y, {x, n}]/y, x]], {n, 0, 11} ]]

a(n) is the coefficient list of the x's of the n-th d(e^(-x^2 /2)/dx.

Sum_{k=0..n} |T(n, k)| = A000085(n). - Peter Luschny, Jan 10 2023

A180118 a(n) = Sum_{k=1..n} (k+2)!/k! = Sum_{k=1..n} (k+2)*(k+1).

Original entry on oeis.org

0, 6, 18, 38, 68, 110, 166, 238, 328, 438, 570, 726, 908, 1118, 1358, 1630, 1936, 2278, 2658, 3078, 3540, 4046, 4598, 5198, 5848, 6550, 7306, 8118, 8988, 9918, 10910, 11966, 13088, 14278, 15538, 16870, 18276, 19758, 21318, 22958, 24680, 26486, 28378, 30358

Offset: 0

Gary Detlefs, Aug 10 2010

In general, sequences of the form a(n) = sum((k+x+2)!/(k+x)!,k=1..n) have a closed form a(n) = n*(11+12*x+3*x^2+3*x*n+6*n+n^2)/3.
This sequence is related to A033487 by A033487(n) = n*a(n)-sum(a(i), i=0..n-1). - Bruno Berselli, Jan 24 2011
The minimal number of multiplications (using schoolbook method) needed to compute the matrix chain product of a sequence of n+1 matrices having dimensions 1 X 2, 2 X 3, ..., (n+1) X (n+2), respectively. - Alois P. Heinz, Jan 27 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
B. Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
Wikipedia, Matrix chain multiplication
Wikipedia, Schoolbook matrix multiplication
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A005718, A033487, A050534.

[n*(n^2+6*n+11)/3: n in [0..45]]; // Vincenzo Librandi, Jun 15 2011

f[n_]:=n*(n^2 + 6 n + 11)/3; f[Range[0,60]] (* Vladimir Joseph Stephan Orlovsky, Feb 10 2011*)
CoefficientList[Series[2*x*(3 - 3*x + x^2)/(1 - x)^4, {x, 0, 50}], x] (* Vaclav Kotesovec, May 10 2019 *)
Table[Sum[(k+1)(k+2),{k,n}],{n,0,50}] (* or *) LinearRecurrence[{4,-6,4,-1},{0,6,18,38},50] (* Harvey P. Dale, Apr 21 2020 *)

a(n) = +4*a(n-1)-6*a(n-2)+4*a(n-3)-1*a(n-4) for n>=4.
a(n) = n*(n^2+6*n+11)/3.
From Bruno Berselli, Jan 24 2011:  (Start)
G.f.: 2*x*(3-3*x+x^2)/(1-x)^4. [corrected by Georg Fischer, May 10 2019]
Sum(a(k), k=0..n) = 2*A005718(n) for n>0. (End)

A188667 Ordered (2,2)-selections from the multiset {1,1,2,2,3,3,...,n,n}.

Original entry on oeis.org

0, 0, 3, 21, 72, 180, 375, 693, 1176, 1872, 2835, 4125, 5808, 7956, 10647, 13965, 18000, 22848, 28611, 35397, 43320, 52500, 63063, 75141, 88872, 104400, 121875, 141453, 163296, 187572, 214455, 244125, 276768, 312576, 351747, 394485, 441000

Offset: 0

Thomas Wieder, Apr 07 2011

Number of ordered (2,2)-selections which can be taken from the first 2n elements of A008619, the positive integers repeated.  Order does count among subselections, e.g. [[1,1],[2,2]] and [[2,2],[1,1]] are different (2,2)-selections. Order does not count within a subselection, e.g. [1,3] is equivalent to [3,1].
Many thanks to Alois P. Heinz, Joerg Arndt, and Olivier Gérard for pointing out bugs in earlier versions of this sequence and for their comments!
The number of (not ordered) (2,2)-selections from natural numbers repeated = A008619 is equal to A086602 (observed by Alois P. Heinz).
The number of ordered (1,1)-selections from natural numbers repeated = A008619 is equal to the squares = A000290.
The number of ordered (1,1)-selections from the natural numbers = A000027 ("[1,2,3,...,n]-multiset") is equal to the Oblong numbers = A002378.
The number of ordered (2,2)-selections from the natural numbers = A000027 ("[1,2,3,...,n]-multiset") is equal to A033487.
The number of (not ordered) (1,1)-selections from the natural numbers = A000027 ("[1,2,3,...,n]-multiset") is equal to the triangular numbers = A000217.
The number of (not ordered) (2,2)-selections from the natural numbers = A000027 ("[1,2,3,...,n]-multiset") is equal to the tritriangular numbers = A050534.
For n>0, the terms of this sequence are related to A014209 by a(n) = sum( i*A014209(i), i=0..n-1 ). [Bruno Berselli, Dec 20 2013]

			Example: For n=3 there are 21 ordered selections of the type (2,2):
[[1,1],[2,2]], [[1,2],[1,2]], [[2,2],[1,1]], [[1,2],[2,3]],
[[1,3],[2,2]], [[2,2],[1,3]], [[2,3],[1,2]], [[1,1],[2,3]],
[[1,2],[1,3]], [[1,3],[1,2]], [[2,3],[1,1]], [[1,1],[3,3]],
[[1,3],[1,3]], [[3,3],[1,1]], [[1,2],[3,3]], [[1,3],[2,3]],
[[2,3],[1,3]], [[3,3],[1,2]], [[2,2],[3,3]], [[2,3],[2,3]],
[[3,3],[2,2]].

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Quang T. Bach, Roshil Paudyal, Jeffrey B. Remmel, A Fibonacci analogue of Stirling numbers, arXiv:1510.04310 [math.CO], 2015 (see p. 28).
T. Wieder, Generation of all possible multiselections from a multiset, Progress in Applied Mathematics, 2(1) (2011), 61-66, DOI:10.3968/j.pam.1925252820110201.010. - Thomas Wieder, Oct 15 2011

Cf. A014209.

Table[n*(n + 4)*(n - 1)^2/4, {n, 0, 100}] (* Vincenzo Librandi, Oct 18 2012 *)

a(n) = n*(n+4)*(n-1)^2/4.

G.f.: 3*x^2*(x^2-2*x-1) / (x-1)^5.

A271040 Number of different 3 against 3 matches given n players.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 10, 70, 280, 840, 2100, 4620, 9240, 17160, 30030, 50050, 80080, 123760, 185640, 271320, 387600, 542640, 746130, 1009470, 1345960, 1771000, 2302300, 2960100, 3767400, 4750200, 5937750, 7362810, 9061920, 11075680, 13449040, 16231600, 19477920

Offset: 0

Elliott Line, Mar 29 2016

Given n players there are a(n) different ways of arranging those players in a 3 against 3 contest.

Number of ways to select two disjoint subsets of size 3 from a set of n elements. - Joerg Arndt, Mar 29 2016

			When there are 6 players, there are 10 different 3 against 3 matches that can be played: ABC v DEF, ABD v CEF, ABE v CDF, ABF v CDE, ACD v BEF, ACE v BDF, ACF v BDE, ADE v BCF, ADF v BCE, AEF v BCD.

Colin Barker, Table of n, a(n) for n = 0..1000
Sela Fried, Counting r X s rectangles in nondecreasing and Smirnov words, arXiv:2406.18923 [math.CO], 2024. See p. 9.
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A050534, the analogous situation for 2 against 2 matches.

LinearRecurrence[{7,-21,35,-35,21,-7,1},{0,0,0,0,0,0,10},40] (* Harvey P. Dale, Sep 17 2016 *)

concat(vector(6), Vec(10*x^6/(1-x)^7 + O(x^50))) \\ Colin Barker, Mar 29 2016

a(n)=binomial(n,3)*binomial(n-3,3)/2 \\ Charles R Greathouse IV, May 22 2018

a(n) = n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)/72.
a(n) = binomial(n,3) * binomial(n-3,3) / 2. - Joerg Arndt, Mar 29 2016
From Colin Barker, Mar 29 2016: (Start)
a(n) = 10*A000579(n).
a(n) = 7*a(n-1)-21*a(n-2)+35*a(n-3)-35*a(n-4)+21*a(n-5)-7*a(n-6)+a(n-7) for n>6.
G.f.: 10*x^6 / (1-x)^7.
(End)

A364725 Starting with a plane on which two parallel lines and two additional lines have been drawn such that the four lines form two non-congruent triangles, a(n) is the total number of lines on the plane after the n-th step, where each step consists of drawing lines that connect every intersection of two lines.

Original entry on oeis.org

4, 6, 7, 11, 69, 176404

Offset: 1

Colin Linzer, Aug 04 2023

Definition is better understood when looking at the "Doodle Sequence" Desmos graph.

Colin Linzer, Doodle Sequence (a desmos graph).

Cf. A050534, A365553.

A recursive formula for an upper bound:
a(n+1) <= (a(n)^4 - a(n)^2)/8 + (a(n) - a(n)^3)/4 which is equivalent to
a(n+1) <= binomial(binomial(a(n),2),2) (proven).
The proof of the above formula comes from the fact that if there are m lines on a graph, then there are at most (m^2-m)/2 intersections. If there are o points on a graph then at most (o^2-o)/2 lines that can be drawn between them, substituting and simplifying leads to the former upper limit.
A non-recursive formula for a lower bound:
a(n) >= 4 + 61*floor(n/5) + 2*[n>=1 (mod 6)] + [n>=2 (mod 6)] + 4*[n>=3 (mod 5)] + 50*[n==4 (mod 5)] (proven).
The proof for the latter formula comes from the fact that in term 6, the new lines form an object congruent to the initial position. That "replica" will "grow" at a rate that must be greater than or equal to that of the original due to the extra lines not part of it, and that it will also produce another objects congruent to the original that will produce another... This formula comes directly from the difference between the terms, so you start with four, then add 2, then 1 ... then when the replicas are produced every 5 terms, you repeat the process. The growth is actually quadratic or higher in order as there are multiple replicas created each time, but that is harder to calculate and has not been done yet.

a(6) from Jinyuan Wang, Aug 09 2023

Definition corrected by Colin Linzer, Sep 12 2023

A365553 Starting with a plane on which two parallel lines and two additional lines have been drawn such that the four lines form two noncongruent isosceles triangles, a(n) is the total number of intersections on the plane after the n-th step, where each step consists of drawing lines that connect every intersection of two lines. If more than 2 lines intersect at the same point it is only counted once.

Original entry on oeis.org

5, 6, 8, 20, 861

Offset: 1

Colin Linzer, Sep 08 2023

Definition is better understood when viewing the linked Desmos graph.

The parity of a term is the parity of the number of intersections along the median from the base of the isosceles triangles. This is because the median is an axis of symmetry of the plane, the number of intersections not on it must be even.

Colin Linzer, Doodle Sequence: Intersections (a Desmos graph).

Cf. A050534, A364725.

A recursive formula for an upper bound:
a(n+1) <= (a(n)^4 - a(n)^2)/8 + (a(n) - a(n)^3)/4 which is equivalent to
a(n+1) <= binomial(binomial(a(n),2),2) (proven).
The proof of the above formula comes from the fact that if there are o points on a graph, then at most (o^2-o)/2 lines that can be drawn between them. If there are m lines on a graph, then there are at most (m^2-m)/2 intersections between them; substituting and simplifying leads to the former upper limit.

cp's OEIS Frontend

A245796 T(n,k) is the number of labeled graphs of n vertices and k edges that have endpoints, where an endpoint is a vertex with degree 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A253942 a(n) = 3*binomial(n+1, 5).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A271023 Number T(n,k) of set partitions of [n] having exactly k pairs (i,j) with i=0, 0<=k<=n*(n-1)/2 read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A053528 Number of bipartite graphs with 5 edges on nodes {1..n}.

Views

Author

Keywords

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A073278 Triangle read by rows. The triangle is constructed from the coefficients of the n-th derivative of the normal probability distribution function.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Formula

A180118 a(n) = Sum_{k=1..n} (k+2)!/k! = Sum_{k=1..n} (k+2)*(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A188667 Ordered (2,2)-selections from the multiset {1,1,2,2,3,3,...,n,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica