login
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

%I #64 Mar 26 2022 17:46:23

%S 1,1,2,5,15,51,191,773,3336,15207,72697,362447,1876392,10051083,

%T 55544661,315899245,1845139684,11048651523,67719859612,424287619507,

%U 2714074517843,17706680249505,117704101959444,796546613501759,5483490237025393,38372546811580251

%N 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.

%C Original name was: The 'AND' Motzkin Numbers.

%C 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.)

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

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

%C 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

%C 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

%H Alois P. Heinz, <a href="/A275605/b275605.txt">Table of n, a(n) for n = 0..400</a>

%H Benedict Irwin, <a href="https://www.authorea.com/users/5445/articles/139066/_show_article">Integer Sequences by Counting Rules</a>.

%H Zhicong Lin, <a href="https://arxiv.org/abs/1706.07213">Restricted inversion sequences and enhanced 3-noncrossing partitions</a>, arXiv:1706.07213 [math.CO], 2017.

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

%e 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.

%e 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.

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

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

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

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

%p end:

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

%p seq(a(n), n=0..30); # _Alois P. Heinz_, May 26 2017

%t SIZ = 30;MAX = 100000;

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

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

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

%t 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 *)

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

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

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 23 2017, after _Alois P. Heinz_ *)

%o /* C, much quicker than MMA with -O3 - _Benedict W. J. Irwin_, 15 Nov 2016 */

%o #include <stdio.h>

%o int main(){

%o int N=25; //max digits

%o int j, s[N], sum;

%o long long int i=0;

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

%o while(1){

%o sum=0;

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

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

%o s[0]++;

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

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

%o s[j]=0;

%o s[j+1]+=1;

%o }

%o }

%o i++;

%o }

%o return 0;

%o }

%Y Cf. A000108, A000110, A001006.

%Y Column k=2 of A287641.

%K nonn

%O 0,3

%A _Benedict W. J. Irwin_, Nov 14 2016

%E Edited by _Franklin T. Adams-Watters_, May 26 2017

%E More terms and new name from _Alois P. Heinz_, May 26 2017