TopCoder Statistics - Problem Statement

Problem Statement

We want to design a network consisting of n identical Worker nodes and one Server node. The network must be connected and must not contain any cycles. We also require that each Worker node must be connected to an odd number of other nodes. How many distinct networks are there?

Here is a listing of all the distinct networks containing exactly 5 worker nodes:

                                                       
       W               W     W              W          W  W 
       |                \    |              |          | /   
   W---S----W            S---W          S---W      S---W    
       | \              /    |              |          | \  
       W  W            W     W          W---W---W      W  W

Two configurations G and G' are not distinct if there is a 1-1 mapping between their nodes such that the server in G maps to the server in G', and such that for every pair of nodes in G the pair that they are mapped to in G' is connected if and only if the pair in G is connected. Note that two configurations are not distinct if they have the same connection pattern, even if they are different geometrically as displayed in the plane. For example, these two configurations with 8 worker nodes are not distinct:

   W   W   W          W       W                                      
   |   |   |          |       |  
   W---S---W      W---S-------W                                                 
   |   |   |          |       | 
   W   W   W      W---W---W   W

Given n, return the number of distinct networks that can be constructed with exactly n worker nodes.

Definition

Class:: OddGraph
Method:: count
Parameters:: int
Returns:: int
Method signature:: int count(int n)
(be sure your method is public)

Notes

The answer will fit in an int.

Constraints

n will be between 1 and 40, inclusive.

Examples

5

Returns: 4

The 4 networks are listed above.
1

Returns: 1

S---W is the only network with 1 worker node.
40

Returns: 929556155
2

Returns: 1
3

Returns: 2
4

Returns: 2
6

Returns: 5
7

Returns: 10
8

Returns: 12
9

Returns: 25
10

Returns: 33
11

Returns: 68
12

Returns: 91
13

Returns: 190
14

Returns: 264
15

Returns: 555
16

Returns: 780
17

Returns: 1649
18

Returns: 2365
19

Returns: 5021
20

Returns: 7274
21

Returns: 15518
22

Returns: 22727
23

Returns: 48646
24

Returns: 71784
25

Returns: 154162
26

Returns: 229094
27

Returns: 493346
28

Returns: 737215
29

Returns: 1591518
30

Returns: 2390072
31

Returns: 5170896
32

Returns: 7798020
33

Returns: 16903848
34

Returns: 25587218
35

Returns: 55561618
36

Returns: 84377881
37

Returns: 183509750
38

Returns: 279499063
39

Returns: 608726985

Statistics

Problem Statement for "OddGraph"

Problem Statement

Definition

Notes

Constraints

Examples