OFFSET
0,4
COMMENTS
From Gus Wiseman, Jun 24 2020: (Start)
Equivalently, a(n) is number of (1,1)-matching sequences of length n that cover an initial interval of positive integers. For example, the a(2) = 1 and a(3) = 7 sequences are:
(1,1) (1,1,1)
(1,1,2)
(1,2,1)
(1,2,2)
(2,1,1)
(2,1,2)
(2,2,1)
Missing from this list are:
(1,2) (1,2,3)
(2,1) (1,3,2)
(2,1,3)
(2,3,1)
(3,1,2)
(3,2,1)
(End)
LINKS
Wikipedia, Weak ordering
Wikipedia, Permutation pattern
FORMULA
a(n) = A000670(n) - n!. - corrected by Eugene McDonnell, May 12 2000
a(n) = Sum_{j=0..n-1} Sum_{i=0..n-1} (-1)^(j-i)*C(j, i)*i^n. - Peter Luschny, Jul 22 2014
MATHEMATICA
a[n_] := Sum[(-1)^(j-i)*Binomial[j, i]*i^n, {i, 0, n-1}, {j, 0, n-1}]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Feb 26 2016, after Peter Luschny *)
PROG
(Sage)
def A019472(n):
return add(add((-1)^(j-i)*binomial(j, i)*i^n for i in range(n)) for j in range(n))
[A019472(n) for n in range(21)] # Peter Luschny, Jul 22 2014
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
Robert Ware (bware(AT)wam.umd.edu)
STATUS
approved