A273461 -id:A273461 - cp's OEIS frontend

A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.

1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, 273, 441, 714, 1156, 1870, 3025, 4895, 7921, 12816, 20736, 33552, 54289, 87841, 142129, 229970, 372100, 602070, 974169, 1576239, 2550409, 4126648, 6677056, 10803704, 17480761, 28284465, 45765225, 74049690, 119814916

Offset: 0

N. J. A. Sloane

Number of compositions of n into 1's, 3's and 4's. - Len Smiley, May 08 2001
The sum of any two alternating terms (terms separated by one term) produces a number from the Fibonacci sequence. (e.g. 4+9=13, 9+25=34, 6+15=21, etc.) Taking square roots starting from the first term and every other term after, we get the Fibonacci sequence. - Sreyas Srinivasan (sreyas_srinivasan(AT)hotmail.com), May 02 2002
(1 + x + 2*x^2 + x^3)/(1 - x - x^3 - x^4) = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 15*x^5 + 25*x^6 + 40*x^7 + ... is the g.f. for the number of binary strings of length where neither 101 nor 111 occur. [Lozansky and Rousseau] Or, equivalently, where neither 000 nor 010 occur.
Equivalently, a(n+2) is the number of length-n binary strings with no two set bits with distance 2; see fxtbook link. - Joerg Arndt, Jul 10 2011
a(n) is the number of words written with the letters "a" and "b", with the following restriction: any "a" must be followed by at least two letters, the second of which is a "b". - Bruno Petazzoni (bpetazzoni(AT)ac-creteil.fr), Oct 31 2005. [This is also equivalent to the previous two conditions.]
Let a(0) = 1, then a(n) = partial products of Product_{n>2} (F(n)/F(n-1))^2 = 1*1*2*2*(3/2)*(3/2)*(5/3)*(5/3)*(8/5)*(8/5)*.... E.g., a(7) = 15 = 1*1*1*2*2*(3/2)*(3/2)*(5/3). - Gary W. Adamson, Dec 13 2009
Number of permutations satisfying -k <= p(i) - i <= r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1}. - Vladimir Baltic, Mar 07 2012
The 2-dimensional version, which counts sets of pairs no two of which are separated by graph-distance 2, is A273461. - Gus Wiseman, Nov 27 2019
a(n+1) is the number of multus bitstrings of length n with no runs of 4 ones. - Steven Finch, Mar 25 2020

			G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 6*x^5 + 9*x^6 + 15*x^7 + 25*x^8 + 40*x^9 + ...
From _Gus Wiseman_, Nov 27 2019: (Start)
The a(2) = 1 through a(7) = 15 subsets with no two elements differing by 2:
  {}  {}   {}     {}     {}     {}
      {1}  {1}    {1}    {1}    {1}
           {2}    {2}    {2}    {2}
           {1,2}  {3}    {3}    {3}
                  {1,2}  {4}    {4}
                  {2,3}  {1,2}  {5}
                         {1,4}  {1,2}
                         {2,3}  {1,4}
                         {3,4}  {1,5}
                                {2,3}
                                {2,5}
                                {3,4}
                                {4,5}
                                {1,2,5}
                                {1,4,5}
(End)

E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see pp. 157 and 172.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 16, 18.
D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
Said Amrouche and Hacène Belbachir, Unimodality and linear recurrences associated with rays in the Delannoy triangle, Turkish Journal of Mathematics (2019) Vol. 44, 118-130.
Joerg Arndt, Matters Computational (The Fxtbook), section 14.10.1, p.320.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
V. Baltic, Applications of the finite state automata for counting restricted permutations and variations, Yug. J. Oper. Res. 22 (2012) 183-198, Sec. 3
G. E. Bergum and V. E. Hoggatt, Jr., A combinatorial problem involving recursive sequences and tridiagonal matrices, Fib. Quart., 16 (1978), 113-118.
M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461.
K. Edwards, A Pascal-like triangle related to the tribonacci numbers, Fib. Q., 46/47 (2008/2009), 18-25.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
T. Guardia and D. Jiménez, Fiboquadratic Sequences and Extensions of the Cassini Identity Raised From the Study of Rithmomachia, arXiv preprint arXiv:1509.03177 [math.HO], 2015-2016.
John Konvalina, Yi-Hsin Liu, subsets without q-separation and binomial products of Fibonacci numbers, J. Comb. Theo. A 57 (2) (1991) 306-310, T_n.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for sequences related to Chebyshev polynomials.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.
Diagonal sums of number triangle A059259.
Cf. A000032, A000034, A000045, A001654, A007598, A209398.
Numbers whose binary expansion has no subsequence (1,0,1) are A048716.
Cf. A003242, A005251, A027383, A167606, A261041, A273461, A329860, A329871.

a006498 n = a006498_list !! n
a006498_list = 1 : 1 : 1 : 2 : zipWith (+) (drop 3 a006498_list)
   (zipWith (+) (tail a006498_list) a006498_list)
-- Reinhard Zumkeller, Apr 07 2012

[ n eq 1 select 1 else n eq 2 select 1 else n eq 3 select 1 else n eq 4 select 2 else Self(n-1)+Self(n-3)+ Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 20 2011

LinearRecurrence[{1,0,1,1},{1,1,1,2},50] (* Harvey P. Dale, Jul 13 2011 *)
Table[Fibonacci[Floor[n/2] + 2]^Mod[n, 2]*Fibonacci[Floor[n/2] + 1]^(2 - Mod[n, 2]), {n, 0, 40}] (* David Nacin, Feb 29 2012 *)
a[ n_] := Fibonacci[ Quotient[ n+2, 2]] Fibonacci[ Quotient[ n+3, 2]] (* Michael Somos, Jan 19 2014 *)
Table[Length[Select[Subsets[Range[n]],!MatchQ[#,{_,x_,_,y_,_}/;x+2==y]&]],{n,10}] (* Gus Wiseman, Nov 27 2019 *)

{a(n) = fibonacci( (n+2)\2 ) * fibonacci( (n+3)\2 )} /* Michael Somos, Mar 10 2004 */

PARI
```
Vec(1/(1-x-x^3-x^4)+O(x^66))
```

def a(n, adict={0:1, 1:1, 2:1, 3:2}):
    if n in adict:
        return adict[n]
    adict[n]=a(n-1)+a(n-3)+a(n-4)
    return adict[n] # David Nacin, Mar 07 2012

G.f.: 1 / ((1 + x^2) * (1 - x - x^2)); a(2*n) = F(n+1)^2, a(2*n - 1) = F(n+1)*F(n). a(n) = a(-4-n) * (-1)^n. - Michael Somos, Mar 10 2004
The g.f. -(1+z+2*z^2+z^3)/((z^2+z-1)*(1+z^2)) for the truncated version 1, 2, 4, 6, 9, 15, 25, 40, ... was given in the Simon Plouffe thesis of 1992. [edited by R. J. Mathar, May 13 2008]
From Vladeta Jovovic, May 03 2002: (Start)
a(n) = round((-(1/5)*sqrt(5) - 1/5)*(-2*1/(-sqrt(5)+1))^n/(-sqrt(5)+1) + ((1/5)*sqrt(5) - 1/5)*(-2*1/( sqrt(5)+1))^n/(sqrt(5)+1)).
G.f.: 1/(1-x-x^2)/(1+x^2). (End)
a(n) = (-i)^n*Sum{k=0..n} U(n-2k, i/2) where i^2=-1. - Paul Barry, Nov 15 2003
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*F(n-2k+1). - Paul Barry, Oct 12 2007
F(floor(n/2) + 2)^(n mod 2)*F(floor(n/2) + 1)^(2 - (n mod 2)) where F(n) is the n-th Fibonacci number. - David Nacin, Feb 29 2012
a(2*n - 1) = A001654(n), a(2*n) = A007598(n+1). - Michael Somos, Mar 10 2004
a(n+1)*a(n+3) = a(n)*a(n+2) + a(n+1)*a(n+2) for all n in Z. - Michael Somos, Jan 19 2014
a(n) = round(1/(1/F(n+2) + 2/F(n+3))), where F(n) = A000045, and 0.5 is rounded to 1. - Richard R. Forberg, Aug 04 2014
5*a(n) = (-1)^floor(n/2)*A000034(n+1) + A000032(n+2). - R. J. Mathar, Sep 16 2017
a(n) = Sum_{j=0..floor(n/3)} Sum_{k=0..j} binomial(n-3j,k)*binomial(j,k)*2^k. - Tony Foster III, Sep 18 2017
E.g.f.: (2*cos(x) + sin(x) + exp(x/2)*(3*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Mar 12 2024

A261041 Number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in different parts.

Original entry on oeis.org

1, 2, 4, 10, 29, 97, 366, 1534, 7050, 35167, 188835, 1084180, 6618472, 42756208, 291120551, 2081922515, 15590248868, 121920095674, 993343650912, 8414029179365, 73953763887277, 673316834487162, 6340176007793060, 61657373569634586, 618445940056365121

Offset: 0

Alois P. Heinz, Aug 09 2015

nonn

From Gus Wiseman, Nov 25 2019: (Start)
Conjecture: Also the number of set partitions of {1, ..., n + 1} where, if x and x + 2 belong to the same block, then so does x + 1. For example, the a(0) = 1 through a(3) = 10 set partitions are:
  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}
         {{1},{2}}  {{1},{2,3}}    {{1},{2,3,4}}
                    {{1,2},{3}}    {{1,2},{3,4}}
                    {{1},{2},{3}}  {{1,2,3},{4}}
                                   {{1,4},{2,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{2,3},{4}}
                                   {{1,2},{3},{4}}
                                   {{1,4},{2},{3}}
                                   {{1},{2},{3},{4}}
(End)

			For n=3 the a(3) = 10 partitions are {}, 1, 2, 3, 1|2, 13, 1|3, 2|3, 13|2, 1|2|3.
From _Gus Wiseman_, Nov 25 2019: (Start)
The a(0) = 1 through a(3) = 10 set partitions:
  {}  {}     {}         {}
      {{1}}  {{1}}      {{1}}
             {{2}}      {{2}}
             {{1},{2}}  {{3}}
                        {{1,3}}
                        {{1},{2}}
                        {{1},{3}}
                        {{2},{3}}
                        {{1,3},{2}}
                        {{1},{2},{3}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..576
Notamathematician et al., Generating function for A261041, MathOverflow, 2024.

Cf. A000110, A003242, A114901, A247100, A261134, A261489, A261492, A273461, A274174.

Partial sums of A376077.

g:= proc(n, l, t) option remember; `if`(n=0, 1, add(`if`(l>0
      and j=l, 0, g(n-1, j, `if`(j=t, t+1, t))), j=0..t))
    end:
a:= n-> g(n, 0, 1):
seq(a(n), n=0..30);

g[n_, l_, t_] := g[n, l, t] = If[n==0, 1, Sum[If[l>0 && j==l, 0, g[n-1, j, If[j==t, t+1, t]]], {j, 0, t}]]; a[n_] := g[n, 0, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 04 2017, translated from Maple *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[Join@@sps/@Subsets[Range[n]],!MemberQ[#,{_,x_,y_,_}/;x+1==y]&]],{n,0,6}] (* Gus Wiseman, Nov 25 2019 *)

a261041(n) = sum(k=0,n, sum(j=0,k,stirling(k,j,2)) * sum(j=0,(n-k)\2, binomial(k+j-1,j))); \\ Max Alekseyev, Sep 08 2024

From Max Alekseyev, Sep 08 2024: (Start)
a(n) = Sum_{k=0..n} A000110(k) * Sum_{j=0..[(n-k)/2]} binomial(k+j-1,j).
G.f.: 1/(1-x) * Sum_{k>=0} A000110(k) * (x/(1-x^2))^k. (End)

A329871 Number of static n X n placements of water source-blocks in Minecraft.

Original entry on oeis.org

1, 2, 10, 55, 754, 18853, 82931, 70143802, 11087020614, 3243227117597, 1772826333285009, 1806938280429412270, 3430002591378184399879, 12137184871791092506807847, 80047171080361800628780500638, 983838070049011459232146327319193

Offset: 0

Gus Wiseman, Nov 26 2019

nonn

In Minecraft worlds, a source block of water can be reacted with another source block, two blocks away, linearly or diagonally. This reaction creates a third "infinite" source block in the unoccupied intermediate block or blocks, so called because if the intermediate water source is destroyed or picked up by a player using a bucket, it will immediately regenerate itself.

A placement of water at several positions in an n X n board is said to be static if no infinite water sources are created that are not already present. In particular, the total quantity of water in the system is held constant.

EthosLab, Minecraft - Tutorial: Water
Gus Wiseman, The a(3) = 55 static placements of water source-blocks (black = water).
Christopher Cormier, C# Program

Dominates A273461.
The one-dimensional case is A005251.
Cf. A002416, A006498, A027624, A114901.

vdist[v_,w_]:=Total[Abs[v-w]];
flowdown[prs_]:=Union[prs,With[{ovs=Select[Subsets[prs,{2}],vdist@@#==2&]},Union@@Function[{v,w},Select[Tuples[{Range[Min@@Union[First/@prs],Max@@Union[First/@prs]],Range[Min@@Union[Last/@prs],Max@@Union[Last/@prs]]}],vdist[v,#]==1&&vdist[w,#]==1&]]@@@ovs]];
Table[Length[Select[Subsets[Tuples[Range[n],2]],flowdown[#]==#&]],{n,0,3}]

a(5)-a(6) from Christopher Cormier, Dec 10 2019

a(7)-a(15) from Christopher Cormier, Dec 19 2019

cp's OEIS Frontend

A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

Python

Formula

A261041 Number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in different parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A329871 Number of static n X n placements of water source-blocks in Minecraft.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions