A214167 -id:A214167 - cp's OEIS frontend

A006342 Coloring a circuit with 4 colors.

1, 1, 4, 10, 31, 91, 274, 820, 2461, 7381, 22144, 66430, 199291, 597871, 1793614, 5380840, 16142521, 48427561, 145282684, 435848050, 1307544151, 3922632451, 11767897354, 35303692060, 105911076181, 317733228541, 953199685624, 2859599056870, 8578797170611

Offset: 0

N. J. A. Sloane, Simon Plouffe

Also equal to the number of set partitions of {1,2,...,n+2} with at most 4 parts such that each part does not contain both i,i+1 for 1<=iMike Zabrocki, Sep 08 2020

Also a(n) equals the number of color-complete multipoles with n terminals (that is, having all the states allowed by the Parity Lemma). - Miquel A. Fiol, May 27 2024

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
F. R. Bernhart, Topics in Graph Theory Related to the Five Color Conjecture, Ph.D. Dissertation, Kansas State Univ., 1974.
F. R. Bernhart, Fundamental chromatic numbers, Unpublished. (Annotated scanned copy)
F. R. Bernhart & N. J. A. Sloane, Correspondence, 1977
G. D. Birkhoff, D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60, (1946). 355-451.
Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, arXiv preprint arXiv:1104.4323 [hep-th], 2011.
M. A. Fiol and J. Vilaltella, Some results on the structure of multipoles in the study of snarks, Electron. J. Combin. 22(1) (2015), #P1.45.
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
Index entries for linear recurrences with constant coefficients, signature (3,1,-3).

A214142, A214167

[3*3^n/8+1/4+3*(-1)^n/8: n in [0..30]]; // Vincenzo Librandi, Aug 20 2011

A006342:=-(-1+2*z)/(z-1)/(3*z-1)/(z+1); # conjectured by Simon Plouffe in his 1992 dissertation
a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2]-1 od: seq(a[n], n=1..26); # Zerinvary Lajos, Apr 28 2008

CoefficientList[Series[(1-2 x)/((1-x^2) (1-3 x)),{x,0,30}],x] (* or *) LinearRecurrence[{3,1,-3},{1,1,4},30] (* Harvey P. Dale, Aug 16 2016 *)

Vec((1 - 2*x) / ((1 - x)*(1 + x)*(1 - 3*x)) + O(x^30)) \\ Colin Barker, Nov 07 2017

G.f.: (1 - 2 x ) / (( 1 - x^2 ) ( 1 - 3 x )).
Binomial transform of A002001 (with interpolated zeros). Partial sums of A054878. E.g.f.: exp(x)(3*cosh(2*x) + 1)/4; a(n) = 3*3^n/8 + 1/4 + 3(-1)^n/8 = Sum_{k=0..n} (3^k + 3(-1)^k)/4. - Paul Barry, Sep 03 2003
a(n) = 2*a(n-1) + 3*a(n-2) - 1, n > 1. - Gary Detlefs, Jun 21 2010
a(n) = a(n-1) + A054878(n-2). - Yuchun Ji, Sep 12 2017
From Colin Barker, Nov 07 2017: (Start)
a(n) = (3^(n+1) + 5) / 8 for n even.
a(n) = (3^(n+1) - 1) / 8 for n odd.
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) for n > 2.
(End)
a(n) = 3*a(n-1) + (3*(-1)^n - 1)/2 for n > 0. - Yuchun Ji, Dec 05 2019

A261137 Number of set partitions B'_t(n) of {1,2,...,t} into at most n parts, so that no part contains both 1 and t, or both i and i+1 with 1 <= i < t; triangle B'_t(n), t>=0, 0<=n<=t, read by rows.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 3, 4, 0, 0, 0, 5, 10, 11, 0, 0, 1, 11, 31, 40, 41, 0, 0, 0, 21, 91, 147, 161, 162, 0, 0, 1, 43, 274, 568, 694, 714, 715, 0, 0, 0, 85, 820, 2227, 3151, 3397, 3424, 3425, 0, 0, 1, 171, 2461, 8824, 14851, 17251, 17686, 17721, 17722

Offset: 0

Mark Wildon, Aug 10 2015

B'_t(n) is the number of sequences of t non-identity top-to-random shuffles that leave a deck of n cards invariant.
B't(n) = <chi^t, 1{Sym_n}> where chi is the degree n-1 constituent of the natural permutation character of the symmetric group Sym_n. This gives a combinatorial interpretation of B'_t(n) using sequences of box moves on Young diagrams.
B'_t(t) is the number of set partitions of a set of size t into parts of size at least 2 (A000296); this is also the number of cyclically spaced partitions of a set of size t.
B'_t(n) = B'_t(t) if n > t.

			Triangle starts:
  1;
  0, 0;
  0, 0, 1;
  0, 0, 0,  1;
  0, 0, 1,  3,   4;
  0, 0, 0,  5,  10,   11;
  0, 0, 1, 11,  31,   40,   41;
  0, 0, 0, 21,  91,  147,  161,  162;
  0, 0, 1, 43, 274,  568,  694,  714,  715;
  0, 0, 0, 85, 820, 2227, 3151, 3397, 3424, 3425;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3), (2007), p 265, E_4.

Cf. A000296, A261139.

For columns n=3-8 see: A001045, A006342, A214142, A214167, A214188, A214239.

g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h),
       add(`if`(j=l, 0, g(t-1, j, max(h,j))), j=1..h+1))
    end:
B:= t-> (p-> seq(add(coeff(p, x, j), j=0..i), i=0..t))(g(t, 0$2)):
seq(B(t), t=0..12);  # Alois P. Heinz, Aug 10 2015

StirPrimedGF[0, x_] := 1; StirPrimedGF[1, x_] := 0;
StirPrimedGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - j*x), {j, 1, n - 1}];
StirPrimed[0, 0] := 1; StirPrimed[0, _] := 0;
StirPrimed[t_, n_] := Coefficient[Series[StirPrimedGF[n, x], {x, 0, t}], x^t];
BPrimed[t_, n_] := Sum[StirPrimed[t, m], {m, 0, n}]
(* Second program: *)
g[t_, l_, h_] := g[t, l, h] = If[t == 0, If[l == 1, 0, x^h], Sum[If[j == l, 0, g[t - 1, j, Max[h, j]]], {j, 1, h + 1}]];
B[t_] := Function[p, Table[Sum[Coefficient[p, x, j], {j, 0, i}], {i, 0, t}] ][g[t, 0, 0]];
Table[B[t], {t, 0, 12}] // Flatten (* Jean-François Alcover, May 20 2016, after Alois P. Heinz *)

B't(n) = Sum{i=0..n} A261139(t,i).

cp's OEIS Frontend

A006342 Coloring a circuit with 4 colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula