A brand new sentence is a sentence which we consider to have never been spoken or written, or thought of (at least the ones which are not recorded). And just swapping a noun with another noun (for example a name of a place or person) while may techinically be considered new sentence, it is not really matching the spirit of brand new sentence.
for the linguists, can you try to come up with a better estimate (better than just coming up (all the words)^(to the power average sentence length)). Maybe by using the description of using different forms of verbs (like we consider in NLP) (verbs which take DP, CP), then adding standard adjectives and finish with remaining grammar (sorry if I am getting it all wrong, it has been a while since I took my intro to linguistics class). Also, consider a morpheme less form. This exercise is for a more realistic guess.
what?
what…