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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275605 Number of set partitions of [n] such that j is member of block b only if b = 1 or at least one of j-1, j-2 is member of a block >= b-1. 2
1, 1, 2, 5, 15, 51, 191, 773, 3336, 15207, 72697, 362447, 1876392, 10051083, 55544661, 315899245, 1845139684, 11048651523, 67719859612, 424287619507, 2714074517843, 17706680249505, 117704101959444, 796546613501759, 5483490237025393, 38372546811580251 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Original name was: The 'AND' Motzkin Numbers.

This sequence consists of the place values from counting in a pattern where the digit is carried if the current place exceeds both the next place plus one and the place after that plus one. (Note that the place "after" a digit is equally described as the digit preceding it, since we write high-order digits first.)

If the "and" logical comparison is changed to "or", then that modified definition produces the Motzkin numbers A001006.

If the this definition looks only at the next term, this generates the Catalan numbers A000108.

This is the case k = 2 of a class of sequences, counting sequences where the k-th term is not more than one more than the maximum of the previous k values. The case k = 1 is the Catalan numbers. The limit as k goes to infinity is the Bell numbers A000110. A similar series limiting terms to no more than one more than the minimum of the previous k values has again the Catalan numbers for k = 1, the Motzkin numbers for k = 2, and continues from there. In this case the limit is the all-ones sequence. - Franklin T. Adams-Watters, Mar 14 2017

To get all the sequences of numerals of length n, take all the numerals of length strictly less than n, and pad them on the left with zeros to length n. - Franklin T. Adams-Watters, May 26 2017

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..400

Benedict Irwin, Integer Sequences by Counting Rules.

Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, arXiv:1706.07213 [math.CO], 2017.

EXAMPLE

The sequence of numerals starts 0, 1, 10, 11, 12, 100, 101, 102, 110, 111, 112, 120, 121, 122, 123.

To get the numeral following 12, we first increment the final digit: 13. But the digits before the 3 are 0 (implied) and 1, and 3 is greater than either of those by more than 1. So we set the last digit to 0, and increment the previous one: 20. Again, 2 is too large for the two implicit zeros in front of it, so we set it to 0 and increment the preceding digit, an implicit zero; so we get 100, which presents no problems.

The length 3 numerals come from the numerals less than 100: 0, 1, 10, 11, 12. Inserting leading zeros to length 3 gives 000, 001, 010, 011, 012.

The values of 1, 10, 100, 1000, etc. make up the sequence.

a(5) = 51 = 52 - 1 = A000110(5) - 1 counts all set partitions of [5] except: 134|2|5. - Alois P. Heinz, May 27 2017

MAPLE

b:= proc(n, i, j) option remember; `if`(n=0, 1,

      add(b(n-1, max(j, k), k), k=1..i+1))

    end:

a:= n-> b(n, 0$2):

seq(a(n), n=0..30);  # Alois P. Heinz, May 26 2017

MATHEMATICA

SIZ = 30; MAX = 100000;

M = Table[0, {n, 1, SIZ + 2}];

For[i = 0, i <= MAX, i++, sum = 0; For[j = 1, j <= SIZ, j++, sum += M[[j]]; ]

  If[sum == 1, Print[i]]M[[1]]++;

For[j = 1, j <= SIZ, j++, If[M[[j]] > M[[j + 1]] + 1 && M[[j]] > M[[j + 2]] + 1, M[[j]] = 0; M[[j + 1]]++]]] (* Benedict W. J. Irwin, Nov 14 2016 *)

b[n_, i_, j_] := b[n, i, j] = If[n==0, 1, Sum[b[n-1, Max[j, k], k], {k, 1, i+1} ] ];

a[n_] := b[n, 0, 0];

Table[a[n], {n, 0, 30}] (* Jean-Fran├žois Alcover, Jun 23 2017, after Alois P. Heinz *)

PROG

/* C, much quicker than MMA with -O3 - Benedict W. J. Irwin, 15 Nov 2016 */

#include <stdio.h>

int main(){

  int N=25; //max digits

  int j, s[N], sum;

  long long int i=0;

  for(j=0; j<N; j++) s[j]=0;

  while(1){

        sum=0;

        for(j=0; j<N; j++) sum+=s[j];

        if(sum==1){ printf("%lld, ", i); fflush(stdout); }

        s[0]++;

        for(j=0; j<N-2; j++){

                if( (s[j]>s[j+1]+1) && (s[j]>s[j+2]+1) ){

                        s[j]=0;

                        s[j+1]+=1;

                }

        }

        i++;

  }

  return 0;

}

CROSSREFS

Cf. A000108, A000110, A001006.

Column k=2 of A287641.

Sequence in context: A299968 A279556 A108307 * A193296 A304454 A287253

Adjacent sequences:  A275602 A275603 A275604 * A275606 A275607 A275608

KEYWORD

nonn

AUTHOR

Benedict W. J. Irwin, Nov 14 2016

EXTENSIONS

Edited by Franklin T. Adams-Watters, May 26 2017

More terms and new name from Alois P. Heinz, May 26 2017

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 January 19 09:35 EST 2020. Contains 331048 sequences. (Running on oeis4.)