login
A019472
Weak preference orderings of n alternatives, i.e., orderings that have indifference between at least two alternatives.
15
0, 0, 1, 7, 51, 421, 3963, 42253, 505515, 6724381, 98618763, 1582715773, 27612565995, 520631327581, 10554164679243, 228975516609853, 5294731892093355, 130015079601039901, 3379132289551117323, 92679942218919579133, 2675254894236207563115, 81073734056332364441821
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)
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
(1,1)-avoiding patterns are counted by A000142.
(1,2)-matching patterns are counted by A056823.
(1,1)-matching compositions are counted by A261982.
(1,1)-matching compositions are ranked by A335488.
Patterns matched by patterns are counted by A335517.
Sequence in context: A332936 A222849 A273055 * A219306 A246572 A230883
KEYWORD
nonn,easy,nice
AUTHOR
Robert Ware (bware(AT)wam.umd.edu)
STATUS
approved