login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A019472 Weak preference orderings of n alternatives, i.e., orderings that have indifference between at least two alternatives. 13
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

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

Table of n, a(n) for n=0..21.

Wikipedia, Weak ordering

Wikipedia, Permutation pattern

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

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

Cf. A000670, A052875.

(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.

Cf. A056986, A333217, A335454, A335456, A335515.

Sequence in context: A332936 A222849 A273055 * A219306 A246572 A230883

Adjacent sequences:  A019469 A019470 A019471 * A019473 A019474 A019475

KEYWORD

nonn,easy,nice

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 14 12:04 EDT 2021. Contains 345025 sequences. (Running on oeis4.)