login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A304972 Triangle read by rows of achiral color patterns (set partitions) for a row or loop of length n. T(n,k) is the number using exactly k colors (sets). 37
1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 10, 9, 3, 1, 1, 7, 19, 16, 12, 3, 1, 1, 15, 38, 53, 34, 18, 4, 1, 1, 15, 65, 90, 95, 46, 22, 4, 1, 1, 31, 130, 265, 261, 195, 80, 30, 5, 1, 1, 31, 211, 440, 630, 461, 295, 100, 35, 5, 1, 1, 63, 422, 1221, 1700, 1696, 1016, 515, 155, 45, 6, 1, 1, 63, 665, 2002 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

Two color patterns are equivalent if we permute the colors. Achiral color patterns must be equivalent if we reverse the order of the pattern.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Ira Gessel, What is the number of achiral color patterns for a row of n colors containing k different colors?, mathoverflow, Jan 30 2018.

FORMULA

T(n,k) = [n>1] * (k*T(n-2,k) + T(n-2,k-1) + T(n-2,k-2)) + [n<2 & n==k & n>=0].

T(2m-1,k) = A140735(m,k).

T(2m,k) = A293181(m,k).

T(n,k) = [k==0 & n==0] + [k==1 & n>0]

  + [k>1 & n==1 mod 2] * Sum_{i=0..(n-1)/2} (C((n-1)/2, i) * T(n-1-2i, k-1))

  + [k>1 & n==0 mod 2] * Sum_{i=0..(n-2)/2} (C((n-2)/2, i) * (T(n-2-2i, k-1)

  + 2^i * T(n-2-2i, k-2))) where C(n,k) is a binomial coefficient.

EXAMPLE

Triangle begins:

1;

1,   1;

1,   1,    1;

1,   3,    2,    1;

1,   3,    5,    2,     1;

1,   7,   10,    9,     3,     1;

1,   7,   19,   16,    12,     3,     1;

1,  15,   38,   53,    34,    18,     4,    1;

1,  15,   65,   90,    95,    46,    22,    4,    1;

1,  31,  130,  265,   261,   195,    80,   30,    5,    1;

1,  31,  211,  440,   630,   461,   295,  100,   35,    5,   1;

1,  63,  422, 1221,  1700,  1696,  1016,  515,  155,   45,   6,  1

1,  63,  665, 2002,  3801,  3836,  3156, 1556,  710,  185,  51,  6, 1;

1, 127, 1330, 5369, 10143, 13097, 10508, 6832, 2926, 1120, 266, 63, 7, 1;

For T(4,2)=3, the row patterns are AABB, ABAB, and ABBA.  The loop patterns are AAAB, AABB, and ABAB.

For T(5,3)=5, the color patterns for both rows and loops are AABCC, ABACA, ABBBC, ABCAB, and ABCBA.

MATHEMATICA

Ach[n_, k_] := Ach[n, k] = If[n < 2, Boole[n == k && n >= 0],

  k Ach[n - 2, k] + Ach[n - 2, k - 1] + Ach[n - 2, k - 2]]

Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten

Ach[n_, k_] := Ach[n, k] = Which[0==k, Boole[0==n], 1==k, Boole[n>0],

  OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],

  True, Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]

  + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]

Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten

PROG

(PARI)

Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}

{ my(A=Ach(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 18 2019

CROSSREFS

Columns 1-6 are A057427, A052551(n-2), A304973, A304974, A304975, A304976.

A305008 has coefficients that determine the function and generating function for each column.

Row sums are A080107.

Sequence in context: A087284 A262311 A242950 * A152176 A152175 A321620

Adjacent sequences:  A304969 A304970 A304971 * A304973 A304974 A304975

KEYWORD

nonn,tabl,easy,changed

AUTHOR

Robert A. Russell, May 22 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 21 11:42 EDT 2019. Contains 327253 sequences. (Running on oeis4.)