login
a(n) = number of set partitions of {1, 2, ..., n} whose blocks consist only of elements that differ by two or less (that is, have only the forms {i}, {i,i+1}, {i,i+2}, or {i,i+1,i+2}).
7

%I #68 Jul 04 2024 21:03:32

%S 1,1,2,5,10,20,42,87,179,370,765,1580,3264,6744,13933,28785,59470,

%T 122865,253838,524428,1083466,2238435,4624595,9554390,19739321,

%U 40781336,84254032,174068400,359624425,742982225,1534997482,3171296957,6551883314,13536157460

%N a(n) = number of set partitions of {1, 2, ..., n} whose blocks consist only of elements that differ by two or less (that is, have only the forms {i}, {i,i+1}, {i,i+2}, or {i,i+1,i+2}).

%C (1) Bryce Duncan and I found this sequence while studying a graph invariant we call the Bell number. For a simple graph G = (V,E), we define B(G) to be the number of partitions P of V in which each block of P is an independent set of G. The sequence considered here results from choosing V = {1, 2, ..., n} and E = {(i,j) : |i - j| > 2. (The classical Bell numbers B(n) come from the edgeless graph on n vertices.)

%C (2) The constant r in the formula is the dominant root of the characteristic equation of a linear homogeneous recurrence relation that also defines {a(n)}. (This recurrence relation, along with initial conditions, appears in the Mathematica program given below. The formula for a(n) is analogous to one version of the Binet formula for the Fibonacci numbers, namely F(n) = the integer nearest to (1/sqrt(5)) p^n where p is the golden mean. The shifted Fibonacci numbers F(n+1) are also graphical Bell numbers: replace the condition |i - j| > 2 with |i - j| > 1 to obtain them.

%C (3) Bell numbers for simple graphs satisfy the deletion-contraction identity B(G) = B(G\e) - B(G/e), but not the product identity B(G union H) = B(G)B(H) for disjoint graphs G and H. However, we do have B(B join H) = B(G)B(H) for the join of graphs G and H. The join graph G join H results from adding to their disjoint union, all possible edges that join a vertex of G to a vertex of H.

%C Diagonal sums of triangle A158687. - _Paul Barry_, Mar 24 2009

%C a(n) is the number of compositions (ordered partitions) of n into parts 1, 2, 3, and 4 where there are two kinds of part 3. - _Joerg Arndt_, Sep 16 2016

%C a(n) is the number of ways to tile a skew double-strip of n cells using squares, "double", and "triangular triple" tiles. Here is the skew double-strip corresponding to n=12, with 12 cells:

%C ___ ___ ___ ___ ___ ___

%C | | | | | | |

%C _|___|___|___|___|_ _|___|

%C | | | | | | |

%C |___|___|___|___|___|___|,

%C and here are the three possible "double" tiles and two possible "triangular triple" tiles:

%C ___ ___ ___ _______

%C | | | | | | | |

%C _| _| |_ |_ _______ _| |_ |_ _|

%C | | | | | | | | | |

%C |___|, |___|, |_______|, |_______|, |___|

%C As an example, here is one of the b(12) = 3264 ways to tile the skew double-strip of 12 cells:

%C ___ ___ _______ _______

%C | | | | | |

%C _|___|_ |__ _| |_ _|

%C | | | | |

%C |_______|___|___|___ ___|. - _Greg Dresden_ and Ruotong Li, Jun 12 2024

%D Herbert S. Wilf, Generatingfunctiononogy (2nd Edition), Academic Press 1990, pp. 1 - 10 and pp. 20 - 23.

%D Arthur T. Benjamin and Jennifer J. Quinn, Proofs that Really Count, Dolciani Mathematical Expositions (MAA), (2003), p. 1. (A relevant combinatorial interpretation of Fibonacci numbers.)

%H Alois P. Heinz, <a href="/A129847/b129847.txt">Table of n, a(n) for n = 0..1000</a>

%H Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, <a href="https://arxiv.org/abs/2312.05145">Cyclic permutations avoiding patterns in both one-line and cycle forms</a>, arXiv:2312.05145 [math.CO], 2023. See p. 2.

%H B. Duncan and R. Peele, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Peele/peele5.html">Bell and Stirling numbers for graphs</a>, JIS 12 (2009), Article 09.7.1.

%H W. Kuszmaul, <a href="http://arxiv.org/abs/1509.08216">Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations</a>, arXiv preprint arXiv:1509.08216 [cs.DM], 2015.

%H W. Kuszmaul, <a href="http://dx.doi.org/10.1090/mcom/3216">Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations</a>, Mathematics of Computation 87 (2018), 987-1011.

%F a(n) = the integer nearest to s r^n, where r = 2.0659948920 ... and s = 0.53979687305... . (More information in comment (2).)

%F a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..n-2k} C(n-j-k,k)*C(2k,j). - _Paul Barry_, Mar 24 2009

%F G.f.: 1/(1 - x - x^2 - 2*x^3 - x^4). - _Colin Barker_, May 02 2012

%F a(n) = a(n-1) + a(n-2) + 2*(n-3) + a(n-4) with a(0) = a(1) = 1, a(2) = 2, a(3) = 5. - _Taras Goy_, Aug 04 2017

%F a(2*n) = a(n)^2 - a(n-1)^2 + a(n-2)^2 + 2*a(n-1)*(a(n+1)-a(n)). - _Greg Dresden_, Jul 03 2024

%e a(4) = 10, with set partitions {{1},{2},{3}, {4}}; {{1,2}, {3}, {4}}; {{1,3}, {2}, {4}}; {{1}, {2,3}, {4}}; {{1}, {2,4}, {3}}; {{1}, {2}, {3,4}}; {{1,2,3}, {4}}; {{1}, {2,3,4}}; {{1,2}, {3,4}} and {{1,3}, {2,4}}.

%p a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|2|1|1>>^n)[4, 4]:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Sep 15 2016

%t a[1] = 1; a[2] = 2; a[3] = 5; a[4] = 10

%t a[n_] := a[n] = a[n-1] + a[n-2] + 2 a[n-3] + a[n-4]

%t Table[a[n],{n,1,30}]

%Y Cf. A000110, A000045, A141073, A158687, A276893.

%Y Column k=3 of A276719.

%K nonn,easy

%O 0,3

%A Rhodes Peele (rpeele(AT)mail.aum.edu), May 22 2007

%E a(0)=1 prepended by _Alois P. Heinz_, Sep 15 2016