Skip to main content
removed contradiction in (c)
Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.

Edit In the light of the comments, there can be 3 scenarios, all interesting.

a) all with same difference. b

b) all differences distinct. c

c) differences all satisfy $\leq D.$$t\leq d \leq D.$

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.

Edit In the light of the comments, there can be 3 scenarios, all interesting.

a) all with same difference. b) all differences distinct. c) differences all $\leq D.$

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.

Edit In the light of the comments, there can be 3 scenarios, all interesting.

a) all with same difference.

b) all differences distinct.

c) differences all satisfy $t\leq d \leq D.$

added 177 characters in body
Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.

Edit In the light of the comments, there can be 3 scenarios, all interesting.

a) all with same difference. b) all differences distinct. c) differences all $\leq D.$

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.

Edit In the light of the comments, there can be 3 scenarios, all interesting.

a) all with same difference. b) all differences distinct. c) differences all $\leq D.$

Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

Number of partitions of $\{1,2,\ldots,n\}$ whose blocks are arithmetic progressions of length $t$ or more

This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.

The set $\{1,\ldots,n\}$ has $2^n$ subsets. It also has $B_n$ (the $n$th Bell number) partitions, where $B_n<2^{2^n}$ and $B_n<n^n$ for large $n$.

I would like to determine the number $A_{n,t}$ of partitions of $\{1,\ldots,n\}$ in which each block is an arithmetic progression and has size $\geq t\geq 3$. What can be said about the growth rate of $A_{n,t}$:

  1. If $t$ is kept constant?
  2. If $t=O(\log n),$ say?

If any other growing $t$ proves amenable to analysis, I would be interested in that case as well.