A060488 Number of 4-block ordered tricoverings of an unlabeled n-set.

4, 13, 28, 50, 80, 119, 168, 228, 300, 385, 484, 598, 728, 875, 1040, 1224, 1428, 1653, 1900, 2170, 2464, 2783, 3128, 3500, 3900, 4329, 4788, 5278, 5800, 6355, 6944, 7568, 8228, 8925, 9660, 10434, 11248, 12103, 13000, 13940, 14924, 15953, 17028, 18150, 19320

Offset: 3

Author

Vladeta Jovovic, Mar 20 2001

Keywords

• nonn
• easy

Comments

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering.

If Y is a 4-subset of an n-set X then, for n>=6, a(n-3) is the number of 3-subsets of X having at most one element in common with Y. - Milan Janjic, Dec 08 2007

Also the number of balls in a triangular pyramid of which all balls located on the edges have been removed such that the remaining pyramid's edges each consist of two adjacent balls. The layers of pyramids of this form start (from the top) 3, 7, 12, 18, 25, 33,... (A055998) with one smaller additional layer 1, 3, 6, 10, 15, 21,... (A000217) at the bottom. Thus, a(n) = A000217(n) + Sum_{k=1..n} A055998(k). Example: a(4) = (3+7+12+18)+10 = 50. - K. G. Stier, Dec 12 2012

Links

• Vincenzo Librandi, Table of n, a(n) for n = 3..1000
• Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 11.
• Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Crossrefs

Essentially the same as A026054. - Vladeta Jovovic, Jun 15 2006

Column k=4 of A060492.

Cf. A060091, A060491.

Fourth column (m=3) of (1, 4)-Pascal triangle A095666.

Programs

Magma

[(n-2)*(n-1)*(n+9)/6: n in [3..60]]; // Vincenzo Librandi, Jun 15 2011

Mathematica

Table[ 3 (n - 1) (n - 2)/2! + n (n - 1) (n - 2)/3!, {n, 3, 62}] (* Vladimir Joseph Stephan Orlovsky, Jun 14 2011 *)
Table[(n-2)(n-1)(n+9)/6,{n,3,50}] (* or *) LinearRecurrence[{4,-6,4,-1}, {4,13,28,50},50] (* Harvey P. Dale, Jul 21 2012 *)

PARI

a(n)=(n-2)*(n-1)*(n+9)/6 \\ Charles R Greathouse IV, Jun 14 2011

Formula

a(n) = binomial(n+3, 3) - 6*binomial(n+1, 1) + 8*binomial(n, 0) - 3*binomial(n-1, -1).

G.f.: -y^3*(-4+3*y)/(-1+y)^4.

E.g.f. for ordered k-block tricoverings of an unlabeled n-set is exp(-x+x^2/2+x^3/3*y/(1-y)) * sum(k>=0, 1/(1-y)^binomial(k, 3)*exp(-x^2/2*1/(1-y)^n)*x^k/k! ).

a(n) = (n+9)*binomial(n-1, 2)/3.

a(n) = (n-2)*(n-1)*(n+9)/6. - Zak Seidov, Jun 15 2006

a(3)=4, a(4)=13, a(5)=28, a(6)=50, a(n) = 4*a(n-1)-6*a(n-2)+ 4*a(n-3)- a(n-4). - Harvey P. Dale, Jul 21 2012