Black and red are together - Ee and EE are black horses, ee is a red horse (chestnut)
Bay and brown are agouti mutations - A is bay, At is brown. Agouti doesn't act on a red horse, but can be carried by a red. It is dominant, so only needs one copy to be expressed.
Cream is again on a different locus. Crcr is a single dilute, CrCr is double. It depends on the coat colour that the cream has to act on as to what colour the horse is.
So theoretically, we can narrow down the sire's genes a bit - he has to be ee Crcr as he is palomino. A palomino is a red horse with a single cream gene, which makes it nice and easy to figure out those genes. He could be carrying bay or brown, but we wouldn't know as it won't act on his red based coat. We do know, however, that he only has one of these genes maximum, as the foal has a black base with no agouti. So the sire must have a recessive agouti gene, and we can say that he is a? Because we don't know what the other gene is.
Mumma is somewhat harder. We know she has at least one black gene, as she is a black base herself. However, we can't tell if she is carrying one or two black genes. So we put her down as E?. Agouti she has to have one (provided I am right about her being brown), but not two, as she can't have passed one on to her foal. So she is Ata. She doesn't have a cream gene (although there is a slight chance she could be smoky black, but I doubt it very much in this case).
So daddy - ee Crcr a?
Mumma - E? Crcr Ata
The possible combinations from this mating look complicated, but really aren't. Most people assume that an unknown part is heterozygous, just to give complete coverage of possible outcomes. So Ee x ee means 50% of the foals will be red based (chestnut) and 50% will be black based (black, bay, brown). Crcr x crcr means half of the foals will be single dilutes (palomino, buckskin, brown buckskin, smoky black) and 50% won't be diluted at all (chestnut, bay, brown, black). Ata x Aa is the most complex - 25% will be non agouti carriers (black on a black base, chestnut not carrying agouti on red base), 25% will be bay carrying non-agouti, 25% will be bay carrying brown, and 25% will be brown carrying non-agouti*.
Ok, novel finished lol.
*This is the theory currently on agouti dominance, but it is just a theory and not proved yet :)