A168178 -id:A168178 - cp's OEIS frontend

A277504 Array read by descending antidiagonals: T(n,k) is the number of unoriented strings with n beads of k or fewer colors.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 6, 1, 0, 1, 5, 10, 18, 10, 1, 0, 1, 6, 15, 40, 45, 20, 1, 0, 1, 7, 21, 75, 136, 135, 36, 1, 0, 1, 8, 28, 126, 325, 544, 378, 72, 1, 0, 1, 9, 36, 196, 666, 1625, 2080, 1134, 136, 1, 0, 1, 10, 45, 288, 1225, 3996, 7875, 8320, 3321, 272, 1, 0

Offset: 0

Jean-François Alcover, Oct 18 2016

From Petros Hadjicostas, Jul 07 2018: (Start)
Column k of this array is the "BIK" (reversible, indistinct, unlabeled) transform of k,0,0,0,....
Consider the input sequence (c_k(n): n >= 1) with g.f. C_k(x) = Sum_{n>=1} c_k(n)*x^n. Let a_k(n) = BIK(c_k(n): n >= 1) be the output sequence under Bower's BIK transform. It can proved that the g.f. of BIK(c_k(n): n >= 1) is A_k(x) = (1/2)*(C_k(x)/(1-C_k(x)) + (C_k(x^2) + C_k(x))/(1-C_k(x^2))). (See the comments for sequence A001224.)
For column k of this two-dimensional array, the input sequence is defined by c_k(1) = k and c_k(n) = 0 for n >= 1. Thus, C_k(x) = k*x, and hence the g.f. of column k is (1/2)*(C_k(x)/(1-C_k(x)) + (C_k(x^2) + C_k(x))/(1-C_k(x^2))) = (1/2)*(k*x/(1-k*x) + (k*x^2 + k*x)/(1-k*x^2)) = (2 + (1-k)*x - 2*k*x^2)*k*x/(2*(1-k*x^2)*(1-k*x)).
Using the first form the g.f. above and the expansion 1/(1-y) = 1 + y + y^2 + ..., we can easily prove J.-F. Alcover's formula T(n,k) = (k^n + k^((n + mod(n,2))/2))/2.
(End)

			Array begins with T(0,0):
1 1   1     1      1       1        1         1         1          1 ...
0 1   2     3      4       5        6         7         8          9 ...
0 1   3     6     10      15       21        28        36         45 ...
0 1   6    18     40      75      126       196       288        405 ...
0 1  10    45    136     325      666      1225      2080       3321 ...
0 1  20   135    544    1625     3996      8575     16640      29889 ...
0 1  36   378   2080    7875    23436     58996    131328     266085 ...
0 1  72  1134   8320   39375   140616    412972   1050624    2394765 ...
0 1 136  3321  32896  195625   840456   2883601   8390656   21526641 ...
0 1 272  9963 131584  978125  5042736  20185207  67125248  193739769 ...
0 1 528 29646 524800 4884375 30236976 141246028 536887296 1743421725 ...
...

See A005418.

Robert A. Russell, Antidiagonals n=0..52, flattened (antidiagonals 1..50 from Andrew Howroyd)
C. G. Bower, Transforms (2)

Columns 0-6 are A000007, A000012, A005418(n+1), A032120, A032121, A032122, A056308.
Rows 0-20 are A000012, A001477, A000217 (triangular numbers), A002411 (pentagonal pyramidal numbers), A037270, A168178, A071232, A168194, A071231, A168372, A071236, A168627, A071235, A168663, A168664, A170779, A170780, A170790, A170791, A170801, A170802.
Main diagonal is A275549.
Transpose is A284979.
Cf. A284871, A284949.
Cf. A003992 (oriented), A293500 (chiral), A321391 (achiral).

[[n le 0 select 1 else ((n-k)^k + (n-k)^Ceiling(k/2))/2: k in [0..n]]: n in [0..15]]; // G. C. Greubel, Nov 15 2018

Table[If[n>0, ((n-k)^k + (n-k)^Ceiling[k/2])/2, 1], {n, 0, 15}, {k, 0, n}] // Flatten (* updated Jul 10 2018 *) (* Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018 *)

for(n=0,15, for(k=0,n, print1(if(n==0,1, ((n-k)^k + (n-k)^ceil(k/2))/2), ", "))) \\ G. C. Greubel, Nov 15 2018

T(n,k) = {(k^n + k^ceil(n/2)) / 2} \\ Andrew Howroyd, Sep 13 2019

T(n,k) = [n==0] + [n>0] * (k^n + k^ceiling(n/2)) / 2. [Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018]
G.f. for column k: (1 - binomial(k+1,2)*x^2) / ((1-k*x)*(1-k*x^2)). - Petros Hadjicostas, Jul 07 2018 [Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018]
From Robert A. Russell, Nov 13 2018: (Start)
T(n,k) = (A003992(k,n) + A321391(n,k)) / 2.
T(n,k) = A003992(k,n) - A293500(n,k) = A293500(n,k) + A321391(n,k).
G.f. for row n: (Sum_{j=0..n} S2(n,j)*j!*x^j/(1-x)^(j+1) + Sum_{j=0..ceiling(n/2)} S2(ceiling(n/2),j)*j!*x^j/(1-x)^(j+1)) / 2, where S2 is the Stirling subset number A008277.
G.f. for row n>0: x*Sum_{k=0..n-1} A145882(n,k) * x^k / (1-x)^(n+1).
E.g.f. for row n: (Sum_{k=0..n} S2(n,k)*x^k + Sum_{k=0..ceiling(n/2)} S2(ceiling(n/2),k)*x^k) * exp(x) / 2, where S2 is the Stirling subset number A008277.
T(0,k) = 1; T(1,k) = k; T(2,k) = binomial(k+1,2); for n>2, T(n,k) = k*(T(n-3,k)+T(n-2,k)-k*T(n-1,k)).
For k>n, T(n,k) = Sum_{j=1..n+1} -binomial(j-n-2,j) * T(n,k-j). (End)

Array transposed for greater consistency by Andrew Howroyd, Apr 04 2017

Origin changed to T(0,0) by Robert A. Russell, Nov 13 2018

A155977 a(n) = n^5 + n^3.

Original entry on oeis.org

0, 2, 40, 270, 1088, 3250, 7992, 17150, 33280, 59778, 101000, 162382, 250560, 373490, 540568, 762750, 1052672, 1424770, 1895400, 2482958, 3208000, 4093362, 5164280, 6448510, 7976448, 9781250, 11898952, 14368590, 17232320, 20535538

Offset: 0

Vincenzo Librandi, Feb 01 2009

Sequence occurs in the binomial identity Sum_{k = 0..n} a(k)* binomial(n,k)/binomial(n+k,k) = n^3. - Peter Bala, Feb 12 2019

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A000578, A002522, A168178.

List([0..30], n-> n^5 + n^3); # G. C. Greubel, Sep 02 2019

[n^5 + n^3: n in [0..30]] // Vincenzo Librandi, Feb 03 2012

seq(n^5 + n^3, n=0..30); # G. C. Greubel, Sep 02 2019

Table[n^5 + n^3, {n,0,30}] (* Vladimir Joseph Stephan Orlovsky, Apr 18 2011 *)
CoefficientList[Series[2x(1+14x+30x^2+14x^3+x^4)/(1-x)^6, {x,0,30}], x] (* Vincenzo Librandi, Feb 05 2013 *)
LinearRecurrence[{6,-15,20,-15,6,-1}, {0,2,40,270,1088,3250}, 30] (* Harvey P. Dale, Jan 18 2015 *)

a(n)=n^5+n^3 \\ Charles R Greathouse IV, Dec 28 2011

[n^5 + n^3 for n in (0..30)] # G. C. Greubel, Sep 02 2019

a(n) = 2*A168178(n).
a(n) = A000578(n)*A002522(n). - Vincenzo Librandi, Feb 03 2012
G.f.: 2*x*(1 + 14*x + 30*x^2 + 14*x^3 + x^4)/(1-x)^6. - Vincenzo Librandi, Feb 05 2013
E.g.f.: x*(2 + 18*x + 26*x^2 + 10*x^3 + x^4)*exp(x). - G. C. Greubel, Sep 02 2019

A285522 Array read by antidiagonals: T(m,n) = number of circulant digraphs up to Cayley isomorphism on n vertices with edges colored according to step value using a maximum of m-1 colors.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 6, 4, 1, 1, 6, 18, 10, 5, 1, 1, 20, 24, 40, 15, 6, 1, 1, 14, 135, 70, 75, 21, 7, 1, 1, 48, 130, 544, 165, 126, 28, 8, 1, 1, 52, 648, 700, 1625, 336, 196, 36, 9, 1, 1, 140, 1137, 4480, 2635, 3996, 616, 288, 45, 10, 1

Offset: 1

Andrew Howroyd, Apr 20 2017

For the base case of m=2 the sequence counts circulant digraphs up to Cayley isomorphism. Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other. For squarefree n this is the only way that two circulant graphs can be isomorphic. (See Liskovets reference for a proof.)
Alternatively, the number of mappings with domain {1..n-1} and codomain {1..m} up to equivalence. Mappings A and B are equivalent if there is a d, prime to n, such that A(i) = B(i*d mod n) for i in {1..n-1}. This sequence differs from A132191 only in that sequence also includes 0 in the domain which introduces an extra factor of m into the results since zero multiplied by anything is zero.
All column sequences are polynomials of order n-1 and these are the cycle index polynomials.
This sequence is also related to A075195(n, m) which counts necklaces and A285548(m, n) which is the sequence described in the Titsworth reference. In particular, A075195 is the analogous array with equivalence determined through the additive group instead of by multiplication whereas A285548 allows for both addition and multiplication.

			Table starts:
\n  1 2  3   4    5    6    7     8      9      10
m\ ---------------------------------------------------
1 | 1 1  1   1    1    1    1     1      1       1 ...
2 | 1 2  3   6    6   20   14    48     52     140 ...
3 | 1 3  6  18   24  135  130   648   1137    4995 ...
4 | 1 4 10  40   70  544  700  4480  11056   65824 ...
5 | 1 5 15  75  165 1625 2635 20625  65425  489125 ...
6 | 1 6 21 126  336 3996 7826 72576 280596 2521476 ...
...
Case n=10:
Only 1, 3, 7, 9 are prime to 10.
Multiplication modulo 10 is described by the following multiplication table.
  1, 2, 3, 4, 5, 6, 7, 8, 9  => (1)(2)(3)(4)(5)(6)(7)(8)(9) => m^9
  3, 6, 9, 2, 5, 8, 1, 4, 7  => (1397)(2684)(5)             => m^3
  7, 4, 1, 8, 5, 2, 9, 6, 3  => (1793)(2486)(5)             => m^3
  9, 8, 7, 6, 5, 4, 3, 2, 1  => (19)(28)(37)(46)(5)         => m^5
Each row of the multiplication table can be viewed as a permutation and together these form a commutative group on 4 elements. In this case the group is isomorphic to the cyclic group C_4. Each permutation can be represented in cycle notation. (shown above to the right of the corresponding multiplication table row). In order to count the equivalence classes using Polya's enumeration theorem only the number of cycles in each permutation is needed.
This gives the cycle index polynomial (1/4)*(m^9 + m^5 + 2*m^3). Putting m = 1..4 gives 1, 140, 4995, 65824.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
Eric Weisstein's World of Mathematics, Circulant Graph.
Wikipedia, Polya enumeration theorem.

Row 2 is A056391.
Columns include A002411, A006528, A168178, A006565, A282613, A054624.
Cf. A132191, A075195, A285548, A002729.

A132191[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #] &], 0], {k, 1, n}];
T[m_, n_] := A132191[m, n]/m;
Table[T[m - n + 1, n], {m, 1, 11}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017 *)

a(n,x)=sum(k=1, n, if(gcd(k, n)==1, x^(sumdiv(n, d, eulerphi(d)/znorder(Mod(k, d)))-1), 0))/eulerphi(n);
for(m=1, 6, for(n=1, 10, print1( a(n,m), ", ") ); print(); );

T(m, n) = A132191(m, n) / m.

A321672 Number of chiral pairs of rows of length 5 using up to n colors.

Original entry on oeis.org

0, 0, 12, 108, 480, 1500, 3780, 8232, 16128, 29160, 49500, 79860, 123552, 184548, 267540, 378000, 522240, 707472, 941868, 1234620, 1596000, 2037420, 2571492, 3212088, 3974400, 4875000, 5931900, 7164612, 8594208, 10243380, 12136500

Offset: 0

Robert A. Russell, Nov 16 2018

			For a(0)=0 and  a(1)=0, there are no chiral rows using fewer than two colors. For a(2)=12, the chiral pairs are AAAAB-BAAAA, AAABA-ABAAA, AAABB-BBAAA, AABAB-BABAA, AABBA-ABBAA, AABBB-BBBAAA, ABAAB-BAABA, ABABB-BBABA, ABBAB-BABBA, ABBBB-BBBBA, BAABB-BBAAB, and BABBB-BBBAB.

Index entries for linear recurrences with constant coefficients, signature (6, -15, 20, -15, 6, -1).

Row 5 of A293500.

Cf. A000584 (oriented), A168178 (unoriented), A000578 (achiral).

Table[(n^5-n^3)/2,{n,0,40}]
LinearRecurrence[{6, -15, 20, -15, 6, -1}, {0, 0, 12, 108, 480, 1500}, 40]

a(n)=(n^5-n^3)/2 \\ Charles R Greathouse IV, Oct 21 2022

a(n) = (n^5 - n^3) / 2.
a(n) = (A000584(n) - A000578(n)) / 2.
a(n) = A000584(n) - A168178(n) = A168178(n) - A000578(n).
G.f.: (Sum_{j=1..5} S2(5,j)*j!*x^j/(1-x)^(j+1) - Sum_{j=1..3} S2(3,j)*j!*x^j/(1-x)^(j+1)) / 2, where S2 is the Stirling subset number A008277.
G.f.: x * Sum_{k=1..4} A145883(5,k) * x^k / (1-x)^6.
E.g.f.: (Sum_{k=1..5} S2(5,k)*x^k - Sum_{k=1..3} S2(3,k)*x^k) * exp(x) / 2, where S2 is the Stirling subset number A008277.
For n>5, a(n) = Sum_{j=1..6} -binomial(j-7,j) * a(n-j).

A331528 a(n) = n^2 * (n+1)^2 * (n^2+n+1) / 12.

Original entry on oeis.org

0, 1, 21, 156, 700, 2325, 6321, 14896, 31536, 61425, 111925, 193116, 318396, 505141, 775425, 1156800, 1683136, 2395521, 3343221, 4584700, 6188700, 8235381, 10817521, 14041776, 18030000, 22920625, 28870101, 36054396, 44670556, 54938325, 67101825, 81431296, 98224896

Offset: 0

Seiichi Manyama, Jan 19 2020

Let b(n,k) = Sum_{j=0..n} (-1)^(n-j)* j^k * binomial(n,j) * binomial(n+j,j).
b(n,0) = 1.
b(n,1) = 1/1! * n   * (n+1).
b(n,2) = 1/2! * n^2 * (n+1)^2.
b(n,3) = 1/3! * n^2 * (n+1)^2 * (n^2+n+1) (= 2*a(n)).
b(n,4) = 1/4! * n^3 * (n+1)^3 * (n^2+n+4).
b(n,5) = 1/5! * n^2 * (n+1)^2 * (n^6+3*n^5+13*n^4+21*n^3+18*n^2+8*n-4).
b(n,6) = 1/6! * n^3 * (n+1)^3 * (n^2+n+4) * (n^4+2*n^3+17*n^2+16*n-6).

Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A002378 (b(n,1)), A163102 (b(n,2)), A168178 (first differences).

[n^2*(n+1)^2*(n^2+n+1)/12:n in [0..32]]; // Marius A. Burtea, Jan 19 2020

R:=PowerSeriesRing(Integers(), 33); [0] cat (Coefficients(R!( x*(x^4+14*x^3+30*x^2+14*x+1)/(1-x)^7))); // Marius A. Burtea, Jan 19 2020

a[n_] := (n*(n+1))^2 * (n^2+n+1) / 12; Array[a, 33, 0] (* Amiram Eldar, May 05 2021 *)

PARI
```
{a(n) = n^2*(n+1)^2*(n^2+n+1)/12}
```

G.f.: x * (x^4+14*x^3+30*x^2+14*x+1)/(1-x)^7.

cp's OEIS Frontend

A277504 Array read by descending antidiagonals: T(n,k) is the number of unoriented strings with n beads of k or fewer colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A155977 a(n) = n^5 + n^3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A285522 Array read by antidiagonals: T(m,n) = number of circulant digraphs up to Cayley isomorphism on n vertices with edges colored according to step value using a maximum of m-1 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A321672 Number of chiral pairs of rows of length 5 using up to n colors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A331528 a(n) = n^2 * (n+1)^2 * (n^2+n+1) / 12.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Mathematica

PARI

Formula