A110706 -id:A110706 - cp's OEIS frontend

A322093 Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where A(n,k) is the number of permutations of n copies of 1..k with no element equal to another within a distance of 1.

1, 2, 0, 6, 2, 0, 24, 30, 2, 0, 120, 864, 174, 2, 0, 720, 39480, 41304, 1092, 2, 0, 5040, 2631600, 19606320, 2265024, 7188, 2, 0, 40320, 241133760, 16438575600, 11804626080, 134631576, 48852, 2, 0, 362880, 29083420800, 22278418248240, 131402141197200, 7946203275000, 8437796016, 339720, 2, 0

Offset: 1

Seiichi Manyama, Nov 26 2018

			Square array begins:
   1, 2,    6,        24,           120,                 720, ...
   0, 2,   30,       864,         39480,             2631600, ...
   0, 2,  174,     41304,      19606320,         16438575600, ...
   0, 2, 1092,   2265024,   11804626080,     131402141197200, ...
   0, 2, 7188, 134631576, 7946203275000, 1210527140790855600, ...

Seiichi Manyama, Antidiagonals n = 1..52, flattened
Mathematics.StackExchange, Find the number of k 1's, k 2's, ... , k n's - total kn cards, Apr 08 2012.

Columns k=3 gives A110706.
Rows n=1..10 give A000142, A114938, A193638, A321633, A322126, A321382, A322095, A322096, A322145, A322146.
Main diagonal gives A321634.
Cf. A322013.

Table[Table[SeriesCoefficient[1/(1 - Sum[x[i]/(1 + x[i]), {i, 1, n}]), Sequence @@ Table[{x[i], 0, k}, {i, 1, n}]],{n, 1, 6}], {k, 1, 5}] (* Zlatko Damijanic, Nov 03 2024 *)

q(n,x) = sum(i=1, n, (-1)^(n-i) * binomial(n-1, n-i) * x^i/i!)
T(n,k) = subst(serlaplace(q(n,x)^k), x, 1) \\ Andrew Howroyd, Feb 03 2024

A(n,k) = k! * A322013(n,k).
Let q_n(x) = Sum_{i=1..n} (-1)^(n-i) * binomial(n-1, n-i) * x^i/i!.
A(n,k) = Integral_{0..infinity} (q_n(x))^k * exp(-x) dx.

A190917 Number of permutations of n copies of 1..3 introduced in order 1..3 with no element equal to another within a distance of 1.

Original entry on oeis.org

1, 1, 5, 29, 182, 1198, 8142, 56620, 400598, 2872754, 20824778, 152303410, 1122149800, 8319825040, 62017475600, 464452683432, 3492568119566, 26358270711370, 199565061455634, 1515311001158482, 11535716330003876, 88025068713285476, 673124069796140900

Offset: 0

R. H. Hardin, May 23 2011

nonn

			All solutions for n=2:
  1    1    1    1    1
  2    2    2    2    2
  3    3    3    3    1
  1    2    2    1    3
  3    3    1    2    2
  2    1    3    3    3

Seiichi Manyama, Table of n, a(n) for n = 0..1111 (terms 1..200 from R. H. Hardin)
R. J. Mathar, A class of multinomial permutations avoiding object clusters, vixra:1511.0015 (2015), sequence M_{3,m}/3!.

Column 3 of A322013.

Cf. A000012 (b=2), A190918 (b=4), A190920 (b=5), A190923 (b=6), A190927 (b=7), A190932 (b=8), A321987 (b=9), A322061 (b=10).

[(&+[Binomial(n-1, k)*(Binomial(n-1, k)*Binomial(2*n+1-2*k, n+1) + Binomial(n-1, k+1)*Binomial(2*n-2*k, n+1)): k in [0..Floor(n/2)]])/3: n in [1..25]]; // G. C. Greubel, Nov 24 2018

a:= proc(n) option remember; `if`(n<3, [1$2, 5][n+1],
      ((7*n-4)*a(n-1)+8*(n-2)^2*a(n-2)/(n+1))/n)
    end:
seq(a(n), n=0..22);  # Alois P. Heinz, Sep 09 2023

Table[(1/3)*Sum[Binomial[n-1, k]*(Binomial[n-1, k]*Binomial[2*n+1-2*k, n+1] + Binomial[n-1, k+1]*Binomial[2*n-2*k, n+1]), {k,0,Floor[n/2]}], {n,1,25}] (* G. C. Greubel, Nov 24 2018 *)

A190917(n) = sum(k=0, n\2, binomial(n-1, k)*(binomial(n-1, k)*binomial(2*n+1-2*k, n+1)+binomial(n-1, k+1)*binomial(2*n-2*k, n+1))) / 3; \\ Max Alekseyev, Dec 10 2017

[(1/3)*sum(binomial(n-1, k)*(binomial(n-1, k)*binomial(2*n+1-2*k, n+1) + binomial(n-1, k+1)*binomial(2*n-2*k, n+1))  for k in range(1+floor(n/2))) for n in (1..25)] # G. C. Greubel, Nov 24 2018

a(n) = A110706(n) / 6 for n >= 1.

n*(n+1)*a(n) - (n+1)*(7*n-4)*a(n-1) - 8*(n-2)^2*a(n-2) = 0. - R. J. Mathar, Nov 01 2015 from A110706

a(0)=1 prepended by Alois P. Heinz, Sep 09 2023

A110707 Number of linear arrangements of n blue, n red and n green items such that there are no adjacent items of the same color (first and last elements considered as adjacent).

Original entry on oeis.org

6, 24, 132, 804, 5196, 34872, 240288, 1688244, 12040188, 86892384, 633162360, 4650680640, 34390540320, 255773538240, 1911730760832, 14350853162676, 108139250403804, 817629606524112, 6200696697358344, 47152195812692664

Offset: 1

Max Alekseyev, Aug 04 2005

nonn

The number of linear arrangements is given by A110706 and the number of circular arrangements counted up to rotations is given by A110710.

Cf. A110706, A110710, A110711.

b = Binomial; a[n_] := 2*Sum[b[n-1, k]*(b[n-1, k]*(b[2*n+1-2*k, n+1] - 3* b[2*n-1-2*k, n+1]) + b[n-1, k+1]*(b[2*n-2*k, n+1] - 3*b[2*n-2*k-2, n+1]) ), {k, 0, n/2}]; Array[a, 20] (* Jean-François Alcover, Dec 04 2015, adapted from PARI *)

a(n) = 2 * sum(k=0,n\2, binomial(n-1,k) * ( binomial(n-1,k)*(binomial(2*n+1-2*k,n+1)-3*binomial(2*n-1-2*k,n+1)) + binomial(n-1,k+1)*(binomial(2*n-2*k,n+1)-3*binomial(2*n-2*k-2,n+1)) ))

a(n) = 2 * Sum[k=0..[n/2]] binomial(n-1, k) * ( binomial(n-1, k)*(binomial(2n+1-2k, n+1)-3*binomial(2n-1-2k, n+1)) + binomial(n-1, k+1)*(binomial(2n-2k, n+1)-3*binomial(2n-2k-2, n+1)) )
a(n) = A110706(n) - A110711(n)
a(n) = 2*A000172(n-1)+2*A000172(n) - Mark van Hoeij, Jul 14 2010
Conjecture: n^2*a(n) -3*n*(2*n-1)*a(n-1) -3*(n-1)*(5*n-12)*a(n-2) -8*(n-3)^2*a(n-3)=0. - R. J. Mathar, Jul 26 2014
a(n) ~ 3^(3/2) * 2^(3*n - 1) / (Pi*n). - Vaclav Kotesovec, Nov 09 2024

A110710 Number of ternary necklaces with n beads of each color and no adjacent beads of the same color (i.e., no substrings 00, 11, 22).

Original entry on oeis.org

1, 2, 5, 16, 70, 348, 1948, 11444, 70380, 445944, 2896590, 19186740, 129186596, 881808728, 6089851874, 42482906040, 298976142764, 2120377458900, 15141289233972, 108784152585236, 785869931659980, 5705406374249272

Offset: 0

Max Alekseyev, Aug 05 2005

nonn

The number of circular arrangements (counted up to rotations) of n blue, n red and n green items such that there are no adjacent items of the same color. The number of various linear arrangements is given by A110706, A110707 and A110711.

			For n=2 there are 5 necklaces: 010212, 012012, 012021, 012102, 021021.

G. C. Greubel, Table of n, a(n) for n = 0..1000
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to necklaces

Cf. A000358, A110706, A110707, A110711.

b = Binomial; A110707[n_] := 2*Sum[b[n - 1, k]*(b[n - 1, k]*(b[2*n + 1 - 2*k, n + 1] - 3*b[2*n - 1 - 2*k, n + 1]) + b[n - 1, k + 1]*(b[2*n - 2*k, n + 1] - 3*b[2*n - 2*k - 2, n + 1])), {k,0, n/2}]; a[n_] := DivisorSum[n, A110707[n/#]*EulerPhi[#]&]/(3n); a[0]=1; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Dec 04 2015, adapted from PARI *)

{ A110707(n) = 2 * sum(k=0,n\2, binomial(n-1,k) * (binomial(n-1,k)*(binomial(2*n+1-2*k,n+1)-3*binomial(2*n-1-2*k,n+1)) + binomial(n-1,k+1)*(binomial(2*n-2*k,n+1)-3*binomial(2*n-2*k-2,n+1)) )); A110710(n) = sumdiv(n,d,A110707(n\d)*eulerphi(d))\(3*n); }

a(n) = Sum_{d|n} A110707(n/d)*eulerphi(d) / (3n) for n>0, a(0)=1.

a(n) ~ sqrt(3) * 2^(3*n - 1) / (Pi * n^2). - Vaclav Kotesovec, Mar 20 2023

a(0)=1 prepended by Alois P. Heinz, Dec 04 2015

A141147 Number of linear arrangements of n blue, n red and n green items such that the first item is blue and there are no adjacent items of the same color (first and last elements considered as adjacent).

Original entry on oeis.org

2, 8, 44, 268, 1732, 11624, 80096, 562748, 4013396, 28964128, 211054120, 1550226880, 11463513440, 85257846080, 637243586944, 4783617720892, 36046416801268, 272543202174704, 2066898899119448, 15717398604230888

Offset: 1

Max Alekseyev, Jun 10 2008

nonn

Max Alekseyev, PARI scripts for various problems
L. Q. Eifler, K. B. Reid Jr., and D. P. Roselle, Sequences with adjacent elements unequal, Aequationes Mathematicae 6 (2-3), 1971.

Cf. A110706, A110707, A110710, A110711, A141146, A141148.

A141147 := n -> 2^n*hypergeom([n, (1-n)/2, -n/2],[1, 1],1);
seq(simplify(A141147(i)),i=1..20); # Peter Luschny, Jan 15 2012

{ a(n) = sum(k=0,n\2, binomial(n,2*k) * binomial(2*k,k) * binomial(n-1+k,k) * 2^(n-2*k) ) }

a(n) = A110707(n) / 3 = (A000172(n) + A000172(n-1)) * 2 / 3.
a(n) = Sum_{k=0..floor(n/2)} binomial(n,2k) * binomial(2k,k) * binomial(n-1+k,k) * 2^(n-2k).
a(n) = 2^n*Hypergeometric([n,(1-n)/2,-n/2],[1, 1],1). - Peter Luschny, Jan 15 2012
Recurrence: (3*n^3 + 13*n^2 + 16*n + 4)*a(n+2) = (21*n^3 + 73*n^2 + 74*n + 16)*a(n+1) + (24*n^3 + 32*n^2)*a(n). - Ralf Stephan, Feb 11 2014
a(n) = (1/n) * Sum_{k = floor(n/2)..n} k * binomial(n,k)^2 * binomial(2*k,n). - Peter Bala, Mar 19 2023

A209349 Number A(n,k) of initially rising meander words, where each letter of the cyclic k-ary alphabet occurs n times; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 5, 1, 0, 1, 1, 1, 9, 29, 1, 0, 1, 1, 1, 11, 100, 182, 1, 0, 1, 1, 1, 16, 182, 1225, 1198, 1, 0, 1, 1, 1, 19, 484, 3542, 15876, 8142, 1, 0, 1, 1, 1, 25, 902, 17956, 76258, 213444, 56620, 1, 0, 1

Offset: 0

Alois P. Heinz, Mar 06 2012

In a meander word letters of neighboring positions have to be neighbors in the alphabet, where in a cyclic alphabet the first and the last letters are considered neighbors too.  The words are not considered cyclic here.
A word is initially rising if it is empty or if it begins with the first letter of the alphabet that can only be followed by the second letter in this word position.
A(n,k) is also the number of (n*k-1)-step walks on k-dimensional cubic lattice from (1,0,...,0) to (n,n,...,n) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by 1 or are in the set {1,k}.

			A(0,0) = A(0,k) = A(n,0) = 1: the empty word.
A(1,1) = 1 = |{a}|.
A(2,1) = 0 = |{ }|.
A(2,2) = 1 = |{abab}|.
A(2,3) = 5 = |{abacbc, abcabc, abcacb, abcbac, abcbca}|.
A(1,4) = 1 = |{abcd}|.
A(2,4) = 9 = |{ababcdcd, abadcbcd, abadcdcb, abcbadcd, abcbcdad, abcdabcd, abcdadcb, abcdcbad, abcdcdab}|.
Square array A(n,k) begins:
1,  1,  1,    1,      1,       1,        1, ...
1,  1,  1,    1,      1,       1,        1, ...
1,  0,  1,    5,      9,      11,       16, ...
1,  0,  1,   29,    100,     182,      484, ...
1,  0,  1,  182,   1225,    3542,    17956, ...
1,  0,  1, 1198,  15876,   76258,   749956, ...
1,  0,  1, 8142, 213444, 1753522, 33779344, ...

Alois P. Heinz, Antidiagonals n = 0..15, flattened

Rows n=0+1, 2-3 give: A000012, A209350, A240954.

Columns k=0+2, 3-7 give: A000012, A190917 = A110706/6, A060150 = A088218^2, A209351, A209352, A209353.

b:= proc() option remember; local n; n:= nargs;
     `if`({args}={0}, 1,
       `if`(args[2]>0, b(args[2]-1, args[i]$i=3..n, args[1]), 0)+
       `if`(n>2 and args[n]>0, b(args[n]-1, args[i]$i=1..n-1), 0))
    end:
A:= (n, k)-> `if`(n<2, 1, `if`(k<2, 1-k, b((n-1)$2, n$(k-2)))):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[args_List] := b[args] = Module[{n = Length[args]}, If[Union[args] == {0}, 1, If[args[[2]] > 0, b[Join[{args[[2]] - 1}, args[[3 ;; n]], { args[[1]]}]], 0] + If[n > 2 && args[[n]] > 0, b[Join[{args[[n]] - 1}, args[[1 ;; n - 1]]]], 0]]]; A[n_, k_] := If[n < 2, 1, If[k < 2, 1 - k, b[Join[{n - 1, n - 1}, Array[n&, k - 2]]]]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jan 21 2015, after Alois P. Heinz *)

A110711 Number of linear arrangements of n blue, n red and n green items such that first and last elements have the same color but there are no adjacent items of the same color.

Original entry on oeis.org

0, 6, 42, 288, 1992, 13980, 99432, 715344, 5196336, 38056284, 280658100, 2082218160, 15528409920, 116331315360, 874985339760, 6604555554720, 50010373864416, 379760762209692, 2891169309592548, 22062102167330592

Offset: 1

Max Alekseyev, Aug 04 2005

nonn

The number of linear arrangements is given by A110706 (first and last elements are not adjacent) and A110707 (first and last elements are adjacent) and the number of circular arrangements (counted up to rotations) is given by A110710.

Cf. A110706, A110707, A110710.

ogf := 6*((x-2)*hypergeom([1/3,1/3],[1], 27*x^2/((8*x-1)*(x+1)^2)) + 2*hypergeom([1/3,1/3],[2], 27*x^2/((8*x-1)*(x+1)^2))) / ((1-2* x)*(1+x)^(2/3)*(1-8*x)^(1/3));
series(ogf, x=0, 30); # Mark van Hoeij, Jan 22 2013

a(n) = 6 * sum(k=0,n\2, binomial(n-1,k) * ( binomial(n-1,k)*binomial(2*n-1-2*k,n+1) + binomial(n-1,k+1)*binomial(2*n-2*k-2,n+1) ))

a(n) = 6 * Sum_{k=0..floor(n/2)} binomial(n-1, k) * ( binomial(n-1, k)*binomial(2n-1-2k, n+1) + binomial(n-1, k+1)*binomial(2n-2k-2, n+1) ).
a(n) = A110706(n) - A110707(n).
a(n) = ((n-3)*A000172(n-1) + n*A000172(n))/(n+1). - Mark van Hoeij, Jul 14 2010
Conjecture: -(n+1)*(n-2)*a(n) + (7*n^2 - 13*n + 4)*a(n-1) + 8*(n-2)^2*a(n-2) = 0. - R. J. Mathar, Nov 01 2015

A234633 Numbers of directed Hamiltonian paths in the complete tripartite graph K_{n,n,n}.

Original entry on oeis.org

6, 240, 37584, 15095808, 12420864000, 18233911296000, 43492335022080000, 157551157218115584000, 823642573772373884928000, 5970637844437187690496000000, 58120324656942369834270720000000, 739968068159742816891489484800000000

Offset: 1

Eric W. Weisstein, Dec 28 2013

nonn

Zlatko Damijanic, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Complete Tripartite Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Path.

Cf. A234365, A234616, A110706.

Table[2 n!^3 (Binomial[2 n + 1, n + 1] HypergeometricPFQ[{1 - n, 1 - n, 1/2 - n/2, -(n/2)}, {1, -(1/2) - n, -n}, 1] + (n - 1) Binomial[2 n, n + 1] HypergeometricPFQ[{1 - n, 2 - n, 1/2 - n/2, 1 - n/2}, {2, 1/2 - n, -n}, 1]), {n, 10}] (* Eric W. Weisstein, May 26 2017 *)

a(n) = n!^3 * A110706(n). - Andrew Howroyd, May 24 2017

a(7)-a(12) from Andrew Howroyd, May 24 2017

A321634 Number of arrangements of n 1's, n 2's, ..., n n's avoiding equal consecutive terms.

Original entry on oeis.org

1, 1, 2, 174, 2265024, 7946203275000, 12229789732207993835280, 12202002913678756821228939869239920, 10937192762438008527903830198163831816546577931520, 11655577382287102750765311537460065620507094071664576111302628243840

Offset: 0

Seiichi Manyama, Nov 15 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..26
Mathematics.StackExchange, Find the number of k 1's, k 2's, ... , k n's - total kn cards, Apr 08 2012.

Cf. A000142, A110706, A114938, A193638, A321633, A321666.

{a(n) = sum(i=n, n^2, i!*polcoef(sum(j=1, n, (-1)^(n-j)*binomial(n-1, j-1)*x^j/j!)^n, i))} \\ Seiichi Manyama, May 27 2019

a(n) ~ n^(n^2 - n/2 + 1) / ((2*Pi)^((n-1)/2) * exp(n - 5/12)). - Vaclav Kotesovec, Nov 24 2018

A141146 Number of linear arrangements of n blue, n red and n green items such that first and last elements are blue but there are no adjacent items of the same color.

Original entry on oeis.org

0, 2, 14, 96, 664, 4660, 33144, 238448, 1732112, 12685428, 93552700, 694072720, 5176136640, 38777105120, 291661779920, 2201518518240, 16670124621472, 126586920736564, 963723103197516, 7354034055776864, 56236603567496720

Offset: 1

Max Alekseyev, Jun 10 2008

nonn

Max Alekseyev, PARI scripts for various problems
L. Q. Eifler, K. B. Reid Jr., D. P. Roselle, Sequences with adjacent elements unequal, Aequationes Mathematicae 6 (2-3), 1971.

Cf. A110706, A110707, A110710, A110711, A141147, A141148.

{ a(n) = sum(k=0,n\2, binomial(n-1,2*k) * binomial(2*k,k) * binomial(n-1+k,k+1) * 2^(n-1-2*k) ) }

a(n) = A110711(n) / 3.
a(n) = Sum[k=0..[n/2]] binomial(n-1,2k) * binomial(2k,k) * binomial(n-1+k,k+1) * 2^(n-1-2k).
G.f.: (2*x-1)^2*(1-8*x)^(-4/3)*(x+1)^(-8/3)*hypergeom([4/3, 4/3],[2],27*x^2/((8*x-1)*(x+1)^2))-(1-8*x)^(-1/3)*(x+1)^(-2/3)*hypergeom([1/3, 1/3],[1],27*x^2/((8*x-1)*(x+1)^2)). - Mark van Hoeij, May 14 2013
Conjecture: -(n+1)*(n-2)*a(n) +(7*n^2-13*n+4)*a(n-1) +8*(n-2)^2*a(n-2)=0. - R. J. Mathar, Jul 23 2014

cp's OEIS Frontend

A322093 Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where A(n,k) is the number of permutations of n copies of 1..k with no element equal to another within a distance of 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A190917 Number of permutations of n copies of 1..3 introduced in order 1..3 with no element equal to another within a distance of 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A110707 Number of linear arrangements of n blue, n red and n green items such that there are no adjacent items of the same color (first and last elements considered as adjacent).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A110710 Number of ternary necklaces with n beads of each color and no adjacent beads of the same color (i.e., no substrings 00, 11, 22).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A141147 Number of linear arrangements of n blue, n red and n green items such that the first item is blue and there are no adjacent items of the same color (first and last elements considered as adjacent).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A209349 Number A(n,k) of initially rising meander words, where each letter of the cyclic k-ary alphabet occurs n times; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A110711 Number of linear arrangements of n blue, n red and n green items such that first and last elements have the same color but there are no adjacent items of the same color.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI