cp's OEIS Frontend

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.

%I A275605 #64 Mar 26 2022 17:46:23
%S A275605 1,1,2,5,15,51,191,773,3336,15207,72697,362447,1876392,10051083,
%T A275605 55544661,315899245,1845139684,11048651523,67719859612,424287619507,
%U A275605 2714074517843,17706680249505,117704101959444,796546613501759,5483490237025393,38372546811580251
%N 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.
%C A275605 Original name was: The 'AND' Motzkin Numbers.
%C A275605 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 A275605 If the "and" logical comparison is changed to "or", then that modified definition produces the Motzkin numbers A001006.
%C A275605 If the definition looks only at the next term, this generates the Catalan numbers A000108.
%C A275605 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 A275605 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 A275605 Alois P. Heinz, <a href="/A275605/b275605.txt">Table of n, a(n) for n = 0..400</a>
%H A275605 Benedict Irwin, <a href="https://www.authorea.com/users/5445/articles/139066/_show_article">Integer Sequences by Counting Rules</a>.
%H A275605 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 A275605 The sequence of numerals starts 0, 1, 10, 11, 12, 100, 101, 102, 110, 111, 112, 120, 121, 122, 123.
%e A275605 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 A275605 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 A275605 The values of 1, 10, 100, 1000, etc. make up the sequence.
%e A275605 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 A275605 b:= proc(n, i, j) option remember; `if`(n=0, 1,
%p A275605       add(b(n-1, max(j, k), k), k=1..i+1))
%p A275605     end:
%p A275605 a:= n-> b(n, 0$2):
%p A275605 seq(a(n), n=0..30);  # _Alois P. Heinz_, May 26 2017
%t A275605 SIZ = 30;MAX = 100000;
%t A275605 M = Table[0, {n, 1, SIZ + 2}];
%t A275605 For[i = 0, i <= MAX, i++,sum = 0;For[j = 1, j <= SIZ, j++,sum += M[[j]];]
%t A275605   If[sum == 1, Print[i]]M[[1]]++;
%t A275605 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 A275605 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 A275605 a[n_] := b[n, 0, 0];
%t A275605 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 23 2017, after _Alois P. Heinz_ *)
%o A275605 /* C, much quicker than MMA with -O3 - _Benedict W. J. Irwin_, 15 Nov 2016 */
%o A275605 #include <stdio.h>
%o A275605 int main(){
%o A275605   int N=25; //max digits
%o A275605   int j, s[N], sum;
%o A275605   long long int i=0;
%o A275605   for(j=0; j<N; j++) s[j]=0;
%o A275605   while(1){
%o A275605         sum=0;
%o A275605         for(j=0; j<N; j++) sum+=s[j];
%o A275605         if(sum==1){ printf("%lld, ", i); fflush(stdout); }
%o A275605         s[0]++;
%o A275605         for(j=0; j<N-2; j++){
%o A275605                 if( (s[j]>s[j+1]+1) && (s[j]>s[j+2]+1) ){
%o A275605                         s[j]=0;
%o A275605                         s[j+1]+=1;
%o A275605                 }
%o A275605         }
%o A275605         i++;
%o A275605   }
%o A275605   return 0;
%o A275605 }
%Y A275605 Cf. A000108, A000110, A001006.
%Y A275605 Column k=2 of A287641.
%K A275605 nonn
%O A275605 0,3
%A A275605 _Benedict W. J. Irwin_, Nov 14 2016
%E A275605 Edited by _Franklin T. Adams-Watters_, May 26 2017
%E A275605 More terms and new name from _Alois P. Heinz_, May 26 2017