Whenever I delete a song from iTunes, for some reason, it doesn't show up in the trash can right away. Usually, if I click on the trash can to open it up, it will then appear. But if you deleted the song from the library (and not just a playlist) it should be in the trash. If you only deleted it from a playlist, it should still be in your library.