|
| |
|
|
A016753
|
|
Expansion of 1/((1-3*x)*(1-4*x)*(1-5*x)).
|
|
3
|
|
|
|
1, 12, 97, 660, 4081, 23772, 133057, 724260, 3863761, 20308332, 105558817, 544039860, 2785713841, 14192221692, 72020501377, 364354427460, 1838822866321, 9262446387852, 46585947584737
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
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
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
|
|
|
|
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
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
|
|
|
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 *)
|
|
|
PROG
|
(Magma) [(5^(n+2) - 2*4^(n+2) + 3^(n+2))/2: n in [0..30]]; // G. C. Greubel, Sep 15 2018
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
