cp's OEIS Frontend

A019472 Weak preference orderings of n alternatives, i.e., orderings that have indifference between at least two alternatives.

%I A019472 #31 Jun 27 2020 21:27:05
%S A019472 0,0,1,7,51,421,3963,42253,505515,6724381,98618763,1582715773,
%T A019472 27612565995,520631327581,10554164679243,228975516609853,
%U A019472 5294731892093355,130015079601039901,3379132289551117323,92679942218919579133,2675254894236207563115,81073734056332364441821
%N A019472 Weak preference orderings of n alternatives, i.e., orderings that have indifference between at least two alternatives.
%C A019472 From _Gus Wiseman_, Jun 24 2020: (Start)
%C A019472 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:
%C A019472   (1,1)  (1,1,1)
%C A019472          (1,1,2)
%C A019472          (1,2,1)
%C A019472          (1,2,2)
%C A019472          (2,1,1)
%C A019472          (2,1,2)
%C A019472          (2,2,1)
%C A019472 Missing from this list are:
%C A019472   (1,2)  (1,2,3)
%C A019472   (2,1)  (1,3,2)
%C A019472          (2,1,3)
%C A019472          (2,3,1)
%C A019472          (3,1,2)
%C A019472          (3,2,1)
%C A019472 (End)
%H A019472 Wikipedia, <a href="https://en.wikipedia.org/wiki/Weak_ordering">Weak ordering</a>
%H A019472 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A019472 Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F A019472 a(n) = A000670(n) - n!. - corrected by Eugene McDonnell, May 12 2000
%F A019472 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
%t A019472 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_ *)
%o A019472 (Sage)
%o A019472 def A019472(n):
%o A019472     return add(add((-1)^(j-i)*binomial(j, i)*i^n for i in range(n)) for j in range(n))
%o A019472 [A019472(n) for n in range(21)] # _Peter Luschny_, Jul 22 2014
%Y A019472 Cf. A000670, A052875.
%Y A019472 (1,1)-avoiding patterns are counted by A000142.
%Y A019472 (1,2)-matching patterns are counted by A056823.
%Y A019472 (1,1)-matching compositions are counted by A261982.
%Y A019472 (1,1)-matching compositions are ranked by A335488.
%Y A019472 Patterns matched by patterns are counted by A335517.
%Y A019472 Cf. A056986, A333217, A335454, A335456, A335515.
%K A019472 nonn,easy,nice
%O A019472 0,4
%A A019472 Robert Ware (bware(AT)wam.umd.edu)