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)
