A209183 -id:A209183 - cp's OEIS frontend

A369923 Array read by antidiagonals: A(n,k) is the number of permutations of n copies of 1..k with values introduced in order and without cyclically adjacent elements equal.

0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 31, 22, 1, 0, 1, 293, 1415, 134, 1, 0, 1, 3326, 140343, 75843, 866, 1, 0, 1, 44189, 20167651, 83002866, 4446741, 5812, 1, 0, 1, 673471, 3980871156, 158861646466, 55279816356, 276154969, 40048, 1, 0

Offset: 1

Andrew Howroyd, Feb 05 2024

Also, T(n,k) is the number of generalized chord labeled loopless diagrams with k parts of K_n. See the Krasko reference for a full definition.

			Array begins:
n\k| 1 2    3         4              5                    6 ...
---+-----------------------------------------------------------
 1 | 0 1    1         1              1                    1 ...
 2 | 0 1    4        31            293                 3326 ...
 3 | 0 1   22      1415         140343             20167651 ...
 4 | 0 1  134     75843       83002866         158861646466 ...
 5 | 0 1  866   4446741    55279816356     1450728060971387 ...
 6 | 0 1 5812 276154969 39738077935264 14571371516350429940 ...
 ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 51 antidiagonals)
Evgeniy Krasko, Igor Labutin, and Alexander Omelchenko, Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs, arXiv:1709.03218 [math.CO], 2017.
Mathematics.StackExchange, Find the number of k 1's, k 2's, ... , k n's - total kn cards, Apr 08 2012.

Rows 2..6 are A003436, A348813, A348815, A348818, A348821.
Column 3 is A197657, column 4 appears to be A209183(n)/2.
Cf. A322013 (without linearly adjacent elements equal), A322093.

T[n_, k_] := If[k == 1, 0, Expand[(-1)^(k (n + 1))/(k - 1)! n Hypergeometric1F1[1 - n, 2, x]^k x^(k - 1)] /. x^p_ :> p!] (* Eric W. Weisstein, Feb 20 2025 *)

\\ compare with A322013.
q(n, x) = sum(i=1, n, (-1)^(n-i) * binomial(n-1, n-i) * x^i/i!)
T(n, k) = if(k > 1, subst(serlaplace(n*q(n, x)^k/x), x, 1)/(k-1)!, 0)

A208879 Number of words A(n,k), either empty or beginning with the first letter of the cyclic k-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet; 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, 1, 1, 1, 2, 3, 1, 1, 1, 2, 30, 10, 1, 1, 1, 2, 62, 560, 35, 1, 1, 1, 2, 114, 2830, 11550, 126, 1, 1, 1, 2, 202, 12622, 151686, 252252, 462, 1, 1, 1, 2, 346, 53768, 1754954, 8893482, 5717712, 1716, 1, 1

Offset: 0

Alois P. Heinz, Mar 02 2012

The first and the last letters are considered neighbors in a cyclic alphabet. The words are not considered cyclic here.

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 less than 2 or are in the set {1,k}.

			A(0,0) = A(n,0) = A(0,k) = 1: the empty word.
A(1,2) = 1 = |{ab}|.
A(1,3) = 2 = |{abc, acb}|.
A(1,4) = 2 = |{abcd, adcb}|.
A(2,2) = 3 = |{aabb, abab, abba}|.
A(2,4) = 62 = |{aabbccdd, aabbcdcd, aabbcddc, aabcbcdd, aabcddcb, aadcbbcd, aadcdcbb, aaddcbbc, aaddcbcb, aaddccbb, ababccdd, ababcdcd, ababcddc, abadcbcd, abadcdcb, abaddcbc, abaddccb, abbadccd, abbadcdc, abbaddcc, abbccdad, abbccdda, abbcdadc, abbcdcda, abcbadcd, abcbaddc, abcbcdad, abcbcdda, abccbadd, abccddab, abcdabcd, abcdadcb, abcdcbad, abcdcdab, abcddabc, abcddcba, adabbccd, adabbcdc, adabcbcd, adabcdcb, adadcbbc, adadcbcb, adadccbb, adcbabcd, adcbadcb, adcbbadc, adcbbcda, adcbcbad, adcbcdab, adccbbad, adccdabb, adcdabbc, adcdabcb, adcdcbab, adcdcbba, addabbcc, addabcbc, addabccb, addcbabc, addcbcba, addccbab, addccbba}|.
Square array A(n,k) begins:
  1,  1,   1,       1,         1,           1,             1, ...
  1,  1,   1,       2,         2,           2,             2, ...
  1,  1,   3,      30,        62,         114,           202, ...
  1,  1,  10,     560,      2830,       12622,         53768, ...
  1,  1,  35,   11550,    151686,     1754954,      19341130, ...
  1,  1, 126,  252252,   8893482,   276049002,    8151741752, ...
  1,  1, 462, 5717712, 552309938, 46957069166, 3795394507240, ...

Columns k=0+1, 2-6 give: A000012, A088218, A208881, A209183, A209184, A209185.
Rows n=0, 2 give: A000012, A208880.
Cf. A208673 (noncyclic alphabet).

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

b[args__] := b[args] = With[{n = Length[{args}]}, If[n<2 || {0} == Union[ {args}], 1, If[n==2, If[{args}[[1]]>0, b[{args}[[1]]-1, {args}[[2]] ], 0] + If[{args}[[2]]>0, b[{args}[[2]]-1, {args}[[1]] ], 0], If[{args}[[1]]>0, b[{args}[[1]]-1, Sequence @@ {args}[[2;;n]] ], 0] + If[{args}[[2]]>0, b[{args}[[2]]-1, Sequence @@ {args}[[3;;n]], {args}[[1]] ], 0]+ If[{args}[[n]]>0, b[{args}[[n]]-1, Sequence @@ Most[{args}]] ],0]] /. Null -> 0];
a[n_,k_]:= If[n==0 || k==0, 1, b[n-1, Sequence @@ Array[n&, k-1]]];
Table[Table[a[n, d-n], {n,0,d}], {d,0,9}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

A378241 Numbers of directed Hamiltonian cycles in the complete 4-partite graph K_{n,n,n,n}.

Original entry on oeis.org

6, 1488, 3667680, 37744330752, 1106491456512000, 74213488705904640000, 9872975878366503813120000, 2355966665497190945783808000000, 935825492908108988335792827924480000, 584053924678169568704863421815848960000000

Offset: 1

Zlatko Damijanic, Nov 20 2024

nonn

P. Horak and L. Tovarek, On Hamiltonian cycles of complete n-partite graphs, Mathematica Slovaca, vol. 29 (1979), 43-47.
Eric Weisstein's World of Mathematics, Complete k-Partite Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.

Cf. A209183, A234365, A369923, A377586.

Table[Sum[Sum[Sum[Sum[ (2n - i - j - 1)! 2^(2i) 3^j (n!)^4/(j!) * (3n - 3i - 3j - 2d)!/((2i + j - n + d)! (n - j - d)! (2n - 3i - 2j - d)!) * (2n - 2i - 2j - 2e)!/(e! (d - e)! (2n - 2i - 2j - d - e)! (n - i - j - d + e)! ((n - i - j - e)!)^2), {e, Max[0, i + j - n + d], Min[d, 2n - 2i - 2j - d]}], {d, Max[0, n - j - 2i], Min[n - j, 2n - 3i - 2j]}], {i, 0, Floor[2(n - j)/3]}], {j, 0, n}], {n, 1, 10}]
Table[(n!)^4 Expand[Hypergeometric1F1[1 - n, 2, x]^4 x^3] /. x^p_ :> p!, {n, 10}] (* Eric W. Weisstein, Feb 20 2025 *)

from math import factorial as fact
def a(n):
   # Using formula found in Horak et al.
   return sum(sum(sum(sum(
       fact(2*n-i-j-1)*pow(2,2*i)*pow(3,j)*pow(fact(n),4)//fact(j) *
       fact(3*n-3*i-3*j-2*d)//(fact(2*i+j-n+d)*fact(n-j-d)*fact(2*n-3*i-2*j-d)) *
       fact(2*n-2*i-2*j-2*e)//(fact(e)*fact(d-e)*fact(2*n-2*i-2*j-d-e)*fact(n-i-j-d+e)*pow(fact(n-i-j-e),2))
       for e in range(max(0,i+j-n+d), min(d,2*n-2*i-2*j-d)+1))
       for d in range(max(0,n-j-2*i), min(n-j,2*n-3*i-2*j)+1))
       for i in range(int(2*(n-j)/3)+1))
       for j in range(n+1))
print([a(n) for n in range(1,11)])

a(n) = 3!*(n-1)!*(n!)^3*A369923(n,4). - Andrew Howroyd, Nov 20 2024

a(n) = 2*A381326(n). - Eric W. Weisstein, Feb 20 2025

cp's OEIS Frontend

A369923 Array read by antidiagonals: A(n,k) is the number of permutations of n copies of 1..k with values introduced in order and without cyclically adjacent elements equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A208879 Number of words A(n,k), either empty or beginning with the first letter of the cyclic k-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

A378241 Numbers of directed Hamiltonian cycles in the complete 4-partite graph K_{n,n,n,n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula