My unsolved problems

I don't think I'm smart enough to solve any of these problems in the near future. I'd be very interested if anybody happens to know how to solve these.

1) Picky partitons

Given a set $A$ and a family $\mathcal{F}$ of subsets of $A$ such that every set in $\mathcal{F}$ contains more than one element, consider a partition of $A$ such that no set in $\mathcal{F}$ is a subset of any of the pieces of the partition of $A$. How many of these partitions are possible, and what is the minimum cardinality of these partitions?

2) Rolling polyhedra

A polyhedron is placed onto a plane. The polyhedron will repeatedly roll over along one of the edges of the face against the plane. The edge is chosen before each roll randomly (independently and uniformly). After $n$ rolls, what is the probability that it will rest on the same face that it started on? (Also, what is the probability it will return to its original position?)

I don't think this problem has a general solution, however I solved it for regular tetrahedra, cubes, octahedra and dodecahedra, and I suspect that there is a reasonably simple solution for all uniform polyhedra.

3) Partial combination sums

Find a formula for $\displaystyle S(x,y)=\sum_{k=0}^{\frac{x}{y}}\binom{x}{ky}$, where $y|x$.

If I'm not mistaken, these should be correct: $S(n,1)=2^n$ $S(n,2)=2^{n-1}$ $S(n,3)=\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}2^{n-2k}$

The third result was from this problem.

I worked on this several weeks ago. I lost the details, but I remember coming up with a (probably incorrect) result that was something like this:

$S(n,b)\stackrel{?}{=}\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}2^{n-2k}a_i$ where $a_i$ is the $i^\text{th}$ coefficient of the generating function $\displaystyle\frac{x}{F_b(x)}$, where $F_b(x)$ is a Fibonacci polynomial.

4) Partition maxima

Let $J_a(m,k)$ be the number of ways to partition $k$ into ordered $a$-tuples such that the maximum of the tuples is $m$. Find a formula for $J_a(m,k)$.

This is as far as I got:

$J_2(m,k)=\begin{cases} 2 &\mbox{if } m \leq k < 2m \\ 1 &\mbox{if } k=2m \\ 0 &\mbox{otherwise} \end{cases}$

$J_3(m,k)=\begin{cases} 3(k-m+1) &\mbox{if } m \leq k < 2m \\ 3(3m-k) &\mbox{if } 2m \leq k < 3m \\ 1 &\mbox{if } k=3m \\ 0 &\mbox{otherwise} \end{cases}$

5) Some bigger grids

Generalize this problem for all such rectangular grids.

Define $F(a,b)$ as the number of paths from the top-left corner to position $(a,b)$, where $(0,0)$ is the top-left corner and $(m,n)$ is the bottom-right corner $(m$ is the horizontal position starting from the left, $n$ is the vertical position starting from the top). Define $F(0,0)=1$, and $F(c,d)=0$ for any point $(c,d)$ outside of the grid.

We can easily derive the recurrence relation $F(a,b)=F(a,b-1)+F(a-1,b)+F(a-1,b+1)$. It is possible to write this as a system of $m+1$ first-order linear recurrences, which can collapse into a $(m+1)^{\text{th}}$-order linear recurrence so that $F(a,0)$ is defined in terms of $F(a-1,0), F(a-2,0), F(a-3,0), \ldots , F(a-(m+1),0)$.

I couldn't figure out how to come to this final recurrence except by lots of tedious substitutions within the system of recurrences. If I do find the final recurrence, the only way I know how to find an explicit formula is by factoring a $(m+1)^{\text{th}}$-degree polynomial, which poses obvious problems for $m\ge 4$.

Pardon the poor explanation. Hopefully this is somewhat comprehensible.