A016753 Expansion of 1/((1-3*x)*(1-4*x)*(1-5*x)).

1, 12, 97, 660, 4081, 23772, 133057, 724260, 3863761, 20308332, 105558817, 544039860, 2785713841, 14192221692, 72020501377, 364354427460, 1838822866321, 9262446387852, 46585947584737

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

As (0,0,1,12,97,...) this is the fourth binomial transform of cosh(x)-1. It is the binomial transform of A016269, when this has two leading zeros. Its e.g.f. is then exp(4x)cosh(x) - exp(4x). - Paul Barry, May 13 2003

This gives the third column of the Sheffer triangle A143495 (3-restricted Stirling2 numbers). See the e.g.f. below, and A193685 for comments on the general case. - Wolfdieter Lang, Oct 08 2011

From Kevin Long, Mar 25 2017: (Start)

In the power set poset 2^(n+2), a(n) gives the number of size 3 subposets {A,B,C} such that A subset of C, B subset of C, and A||B. By symmetry, it also counts the size 3 subposets {A,B,C} such that C subset of A, C subset of B, and A||B.

By the power set poset, I mean the subsets of [n+2] ordered by inclusion. A||B means A and B are incomparable.

The result can be proved by showing that the formula holds. 5^n counts triples (A,B,C) of subsets of [n] where A subset of C and B subset of C, since for each x in [n], it is either in C only, in A and C, in B and C, in all three, or in none. However, this also counts the cases where A subset of B and where B subset of A, and we want A||B.

Each case can be counted by 4^n, since if A subset of B⊆C, then each element x of [n] is either in all three, in B and C, in only C, or in none. Hence we subtract 2*4^n from 5^n. These two cases intersect, however, when A = B subset of C, which can be counted by 3^n, since each element x of [n] can be either in all three sets, in only C, or in none.

For the purposes of inclusion-exclusion, we add these sets back in to get 5^n-2*4^n+3^n to count all triples (A,B,C) where A subset of C, B subset of C, and A||B. We want sets, not triples, so this double-counts the sets since interchanging A and B give the same set, so we divide this by 2. Hence the formula for a(n) counts these subposets for 2^(n+2). (End)

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (12,-47,60).

Crossrefs

Cf. A000244, A005061, A016753, A132495, A193685, A245019.

Programs

Magma

[(5^(n+2) - 2*4^(n+2) + 3^(n+2))/2: n in [0..30]]; // G. C. Greubel, Sep 15 2018

Mathematica

CoefficientList[ Series[ 1/((1 - 3x)(1 - 4x)(1 - 5x)), {x, 0, 25} ], x ]
LinearRecurrence[{12,-47,60}, {1, 12, 97}, 30] (* G. C. Greubel, Sep 15 2018 *)

PARI

Vec(1/((1-3*x)*(1-4*x)*(1-5*x))+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

Formula

a(n) = 5^(n+2)/2 - 4^(n+2) + 3^(n+2)/2. - Paul Barry, May 13 2003

If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*stirling2(k,j)*x^(m-k) then a(n-2) = f(n,2,3), (n >= 2). - Milan Janjic, Apr 26 2009

a(n) = 9*a(n-1) - 20*a(n-2) + 3^n, n >= 2. - Vincenzo Librandi, Mar 20 2011

O.g.f.: 1/((1-3*x)*(1-4*x)*(1-5*x)).

E.g.f.: (d^2/dx^2) (exp(3*x)*((exp(x)-1)^2)/2!). - Wolfdieter Lang, Oct 08 2011

a(n) = A245019(n+2)/2. - Kevin Long, Mar 24 2017