A146994 a(n) = (n+1)^2/4 + (floor((n+5)/6) - 1/4) * ((n+1) mod 2).

1, 3, 4, 7, 9, 13, 16, 22, 25, 32, 36, 44, 49, 59, 64, 75, 81, 93, 100, 114, 121, 136, 144, 160, 169, 187, 196, 215, 225, 245, 256, 278, 289, 312, 324, 348, 361, 387, 400, 427, 441, 469, 484, 514, 529, 560, 576, 608, 625, 659, 676, 711, 729, 765, 784, 822, 841

Offset: 1

Author

Mitch Phillipson, Manda Riehl, and Tristan Williams, Nov 04 2008

Keywords

• easy
• nonn

Comments

This sum appears when calculating the number of elements of S_3 wreath C_k which avoid 12. We use a nonstandard ordering, where we consider an element of S_3 wreath C_k to be a permutation sigma of S_3 with each sigma_i colored one of k colors. We then create a string au with au_i being defined as sigma_i times its color (where, e.g., the 3rd color has value 3). We then consider the reduced string of au identically to reducing permutations as done in standard pattern avoidance. When calculating the number of these reduced strings which avoid 12, we encounter this sequence as one of our subcases.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• T. Mansour, Pattern Avoidance in Coloured Permutations, Séminaire Lotharingien de Combinatoire, 46, 2001.
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,1,-1,-1,1).

Crossrefs

Cf. A000290, A010892, A057078.

Programs

Magma

[(n mod 2) eq 0 select n*(n+2)/4 + Floor((n+5)/6) else (n+1)^2/4: n in [1..60]]; // G. C. Greubel, Jan 09 2020

Maple

a := n -> `if`(irem(n,2)=1,(n+1)^2/4, ((n+1)^2-1)/4 + floor((n+5)/6)): seq(a(n), n=1..57); # Peter Luschny, Feb 01 2015

Mathematica

LinearRecurrence[{1,1,-1,0,0,1,-1,-1,1},{1,3,4,7,9,13,16,22,25},60] (* Harvey P. Dale, Dec 17 2012 *)
Table[If[EvenQ[n], n*(n+2)/4 + Floor[(n+5)/6], (n+1)^2/4], {n, 60}] (* G. C. Greubel, Jan 09 2020 *)

PARI

a(n) = if(n%2==0, n*(n+2)/4 + (n+5)\6, (n+1)^2/4);
vector(60, n, a(n)) \\ G. C. Greubel, Jan 09 2020

Sage

def a(n):
    if (mod(n,2)==0): return n*(n+2)/4 + floor((n+5)/6)
    else: return (n+1)^2/4
[a(n) for n in (1..60)] # G. C. Greubel, Jan 09 2020

Formula

a(2*n-1) = n^2 for n >= 1.

a(2*n) = n*(n+1) + floor((2*n+5)/6) for n >= 0.

From R. J. Mathar, Nov 21 2008: (Start)

a(n) = (-4*A057078(n) - 4*A010892(n+1) + 6*n^2 + 14*n + 7 + (-1)^n*(2n+1))/24.

a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9).

G.f.: x*(1 + 2*x + x^3 + x^4 + x^5)/((1 + x + x^2)*(1 - x + x^2)*(1+x)^2*(1-x)^3). (End)

Extensions

More terms from R. J. Mathar, Nov 21 2008

Name corrected and partial edit by Peter Luschny, Feb 01 2015