

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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



FORMULA

a(n) = A000670(n)  n!.  corrected by Eugene McDonnell, May 12 2000
a(n) = Sum_{j=0..n1} Sum_{i=0..n1} (1)^(ji)*C(j, i)*i^n.  Peter Luschny, Jul 22 2014


MATHEMATICA

a[n_] := Sum[(1)^(ji)*Binomial[j, i]*i^n, {i, 0, n1}, {j, 0, n1}]; Table[a[n], {n, 0, 21}] (* JeanFrançois Alcover, Feb 26 2016, after Peter Luschny *)


PROG

(Sage)
return add(add((1)^(ji)*binomial(j, i)*i^n for i in range(n)) for j in range(n))


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.


KEYWORD

nonn,easy,nice


AUTHOR

Robert Ware (bware(AT)wam.umd.edu)


STATUS

approved



