A367783 Number of subsets of the integer lattice Z^2 of cardinality n such that there is no monotone lattice path which splits the set in half, up to shifts.

0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 2, 0, 2, 0, 4, 0, 6, 0, 6, 0, 11, 0, 12, 8, 7, 0, 6, 0, 8, 0, 18, 0, 32, 0, 20, 0, 29, 0, 42, 8, 67, 16, 30, 0, 13, 0, 22, 0, 32, 0, 42, 0, 64, 0, 50, 0, 64

Offset: 1

Author

Giedrius Alkauskas, Nov 30 2023

Keywords

• nonn
• more

Comments

A monotone path is a lattice path consisting of east and north unit steps or a path consisting of east and south unit steps. When counting, points lying on the path itself are discarded.

a(n) > 0 for even n >= 12.

a(n) > 0 for odd n with natural density 1 (among odd numbers).

For odd n, a(n) is divisible by 8.

Examples

			For n = 4 a(4) = 1 way to place 4 points is as follows:
  .xx.
  .xx.
For n = 8 a(8) = 2 ways to place 8 points are as follows:
  ..x.
  .xxx
  xxx.
  .x..
(and its reflection with respect to a vertical axis).
For n = 18 a(18) = 4 ways to place 18 points are as follows:
  ...x..
  ..xxx.
  .xxxxx
  xxxxx.
  .xxx..
  ..x...
(and its reflection with respect to a vertical axis), and
  .....x....
  ......x...
  .......x..
  ....x...x.
  ...xxx...x
  x...xxx...
  .x...x....
  ..x.......
  ...x......
  ....x.....
(and its reflection with respect to a vertical axis).
		

Links

• Giedrius Alkauskas, Friendly paths for finite subsets of plane integer lattice. I, arXiv:2302.01137 [math.CO], 2024.
• Giedrius Alkauskas, Problem 11484, Problems and solutions, Amer. Math. Monthly, 117 (2) February (2010), p. 182.
• Giedrius Alkauskas, Friendly paths. Problem 11484, Problems and solutions, Amer. Math. Monthly, 119 (2) February (2012), 167-168.

Crossrefs

Cf. A000009, A000292, A005232, A369382.

Extensions

a(36) corrected by Giedrius Alkauskas, Feb 02 2024

a(49)-a(60) from Giedrius Alkauskas, Feb 06 2024