Math Formula for a Recursive Relation of any K-Ary Tree

First hand, my apologies if the question has already been repeated before.

Currently, I'm trying to figure out what exactly the formula for any recursive k-ary tree would look like at any depth for a program I'm writing on.

So far, I know this formula is great for a 2-ary tree:

T(n) = T(n-1) + T(n-2)

[ https://qph.cf2.quoracdn.net/main-qimg-40df14204e47a8e36be14e29994b2a70 ] (I can't post images yet but this link will show you what the formula above is able to do..)


However, I'm trying to see if there is a formula that works with ANY K-ary tree. I'm trying to come up with a program where the user decides what k will be and how much total depth will it contain.

For example, if a k-ary tree has k = 5 and total depth d = 2 then mathematically, it will know for parent node 5 the child nodes are: 25, 26, 27, 28, 29 and 30.

(I know this isn't the coding section of Stack Exchange but for now I'm just trying to find a formula).

Thank you!

• What are you trying to count? Jul 15, 2022 at 14:08
• @DanielV My apologies, I don't understand your question. I'm looking for a recurrence regression formula that can work with any k and depth value. I don't know exactly where to look for one that fits this description... Jul 15, 2022 at 14:10
• A tree is not a number. Jul 15, 2022 at 14:12
• @DanielV No, as in a formula that's able to determine what the NEXT nodes would be. For example, for the formula I listed above, it can tell what the next set of child nodes are (for node 1, it knows the next child nodes are 3 and 4) by utilizing mathematics. Jul 15, 2022 at 14:13
• There's more than one way to label a tree with numbers. Can you clarify what the trees you're interested in look like and explain what the values of your desired function represent?
– Karl
Jul 15, 2022 at 14:37