Alain Goupil - cp's OEIS frontend

A331986 Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.

1, 4, 8, 84, 56, 136, 52, 216, 16, 1504, 2352, 1152, 1344, 123216, 82432, 11008, 308992

Offset: 1

Alain Goupil, Feb 03 2020

The maximum possible number of unit squares is given by A331968(n).
Equivalently, a(n) is the number of maximum length paths without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
For n > 1, a(n) is a multiple of 4 since a solution can have at most one symmetry considering rotations and reflections. - Andrew Howroyd, Feb 04 2020

			For n = 4 the number of snake-like polyominoes with 11 cells is 84.

Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360916.
Cf. A331968, A059525 (connected induced subgraphs), A099155.
Cf. A332920 (non-isomorphic snakes), A332921 (symmetric snakes).

a(15) from Andrew Howroyd, Feb 04 2020

a(16)-a(17) from Yi Yang, Oct 03 2022

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Original entry on oeis.org

1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182

Offset: 1

Alain Goupil, Feb 02 2020

These are similar to the snake-in-the-box problem for the hypercube Q_n (See A099155).
The number of solutions is given by A331986(n).
Equivalently, a(n) is the maximum number of vertices in a path without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
These numbers are part of the result of a computer program that counts the snake-like polyominoes in a rectangle of given size b X h by their length.
a(16) >= 161.

			For n=4, the maximum length of a snake-like polyomino that fits in a square of side 4 is 11 and there are 84 such snakes.
Maximum-length snakes for n = 1 to 4 are shown below.
   X    X X    X X X    X X X X
        X      X   X    X     X
               X   X    X     X
                        X   X X

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Alain Goupil, Illustration of initial terms
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360917.

Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359.

a(n) >= A047838(n+1).
For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - Elijah Beregovsky, May 11 2020
a(n) <= (2*n*(n+1)-1)/3. - Elijah Beregovsky, Nov 09 2020
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

a(15) from Andrew Howroyd, Feb 04 2020

a(16)-a(17) from Yi Yang, Oct 03 2022

A094857 Coefficient of identity representation in k-th tensor power of the irreducible representation of S_n indexed by (n-2,1,1).

Original entry on oeis.org

0, 1, 1, 16, 162, 2661, 53154

Offset: 1

Alain Goupil, Jun 14 2004

nonn

			a(4)=16

A090809 Coefficient of the irreducible character of S_m indexed by (m-2n+2,2n-2) in the n-th Kronecker power of the representation indexed by (m-2,2).

Original entry on oeis.org

0, 0, 2, 10, 31, 75, 155, 287, 490, 786, 1200, 1760, 2497, 3445, 4641, 6125, 7940, 10132, 12750, 15846, 19475, 23695, 28567, 34155, 40526, 47750, 55900, 65052, 75285, 86681, 99325, 113305, 128712, 145640, 164186, 184450, 206535, 230547

Offset: 0

Alain Goupil, Feb 10 2004

For n > 0, the terms of this sequence are related to A000124 by a(n) = Sum_{i=0..n-1} i*A000124(i). - Bruno Berselli, Dec 20 2013

A. Goupil, Combinatorics of the Kronecker products of irreducible representations of Sn, in preparation.

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000124, A049020.

f := proc(k) 2*binomial(k,2)+4*binomial(k,3)+3*binomial(k,4); end;
seq (f(n), n=0..50);

f[n_] := 2Binomial[n, 2] + 4Binomial[n, 3] + 3Binomial[n, 4]; Table[ f[n], {n, 0, 40}] (* Robert G. Wilson v, Feb 13 2004 *)
LinearRecurrence[{5, -10, 10, -5, 1}, {0, 0, 2, 10, 31}, 38] (* Jean-François Alcover, Sep 25 2017 *)

a(n) = 2*binomial(n, 2) + 4*binomial(n, 3) + 3*binomial(n, 4) = (n-1)*n*(3*n^2 + n + 10)/24.
a(n) = A049020(n, n-2), for n >= 2. - Philippe Deléham, Mar 06 2004
G.f.: x^2*(2 + x^2) / (1-x)^5. - Colin Barker, Nov 21 2012

More terms from Robert G. Wilson v, Feb 13 2004

cp's OEIS Frontend

User: Alain Goupil

A331986 Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A094857 Coefficient of identity representation in k-th tensor power of the irreducible representation of S_n indexed by (n-2,1,1).

Views

Author

Keywords

Examples

A090809 Coefficient of the irreducible character of S_m indexed by (m-2n+2,2n-2) in the n-th Kronecker power of the representation indexed by (m-2,2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions