Conversation so far:
What is Leaving Basie?
Young left the Basie band in late 1940.
Why did he leave?
He is rumored to have refused to play with the band on Friday, December 13 of that year for superstitious reasons spurring his dismissal.
How did he react to his dismissal?
CANNOTANSWER.
What did he do after he was dismissed?
Young accompanied the singer Billie Holiday in a couple of studio sessions (during 1937 - 1941 period) and also made a small set of recordings with Nat "King" Cole.

Question: What did record with them?
Self-contained rewrite: What did Lester Young  record with  Billie Holiday?