For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
2answers
38 views

Derive formula for number of cables in full-mesh network

I am trying to determine how they derived number of cables needed in a full mesh network According to networking books it is $\dfrac{N * (N-1)}{2}$, where N is the number of nodes. I tried drawing ...
1
vote
1answer
51 views

How many bags can be made out of 4 kinds of balls

We have balls in a bin, $30$ balls of type $a$, $30$ balls of type $b$, $30$ balls of type $c$, $30$ balls of type $d$. We take out one ball per minute in random and move it to a bag. How ...
7
votes
1answer
139 views

Partition Generating Function

a) Let $$P(x)=\sum_{n=0}^{\infty} p_nx^n=1+x+2x^2+3x^3+5x^4+7x^5+11x^6+\cdots$$ be the partition generating function, and let $Q(x)=\sum_{n=0}^{\infty} q_nx^n$, where $q_n$ is the number of ...
5
votes
0answers
221 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
2
votes
2answers
51 views

Combinatorics of given alphabet

I'm looking for the formula to determine the number of possible words that can be formed with a fixed set of letters and some repeated letters. For instance take the 8-letter word SEASIDES and find ...
3
votes
0answers
46 views

Find naturals that are sum of numbers with the same digits in inverse order

In a test I've found the following exercise: We say $n \in \mathbb{N}$ is reflexive if is the sum of two naturals $x$ and $y$ such that $y$ has the same digits of $x$ witten in the inverse order ...
1
vote
3answers
61 views

Two combinatorial identities

I have to compute the following quantity: $$ 1) \sum\limits_{k=0}^{n} \binom{n}{k}k2^{n-k} $$ Moreover, I have to give an upper bound for the following quantity: $$ 2) \sum\limits_{k=1}^{n-2} ...
0
votes
2answers
31 views

Generating Functions Proof

Let $A=\{2,6,10,14,\ldots\}$ be the set of integers that are twice an odd number. Prove that, for every positive integer $n$, the number of partitions of $n$ in which no odd number appears more than ...
0
votes
2answers
40 views

An elevator starts with 10 people, how many ways can all the people… Cases for each floor?

An elevator starts with 10 people on the first floor of an 8 story building and stops at each floor. In how many ways can all the people get off the elevator? The only way I can think to do this is ...
1
vote
2answers
35 views

Converting a cryptographic hash to a string of English words: how many words are needed? (need help with exponentials)

A particular cryptographic hash is represented as a $57$ byte string, encoded as base $64$. RWSvUZXnw9gUb70PdeSNnpSmodCyIPJEGN1wWr+6Time1eP7KiWJ5eAM I want to ...
1
vote
0answers
35 views

Distinguished points of a cone

Sorry, as this is a rather trivial question that I am misunderstanding, but I do not understand how the distinguished point is defined. We define it as a homomorphism from some semigroup $S_{\sigma}$ ...
5
votes
2answers
63 views

Five girls and eleven boys are to be lined up in a row such that… Where is my mistake?

Five girls and eleven boys are to be lined up in a row such that from left to right, the girls are in the order $g_1g_2g_3g_4g_5$. In how many ways can this be done if $g_1$ and $g_2$ are to be ...
3
votes
3answers
245 views

How many four-digit odd numbers, all of digits different, can be formed from the digits 0 to 9, if there must be a 5 in the number?

How many four-digit odd numbers, all of digits different, can be formed from the digits 0 to 9, if there must be a 5 in the number? I know that there are 4 different cases where 5 is in the ...
3
votes
1answer
74 views

How to proof that all points lie on a common circles.

There are $n=2000$ points in the plane such that every for three of those points there exists a fourth of those points such that these four points lie on a common circle. Proof that all $2000$ points ...
0
votes
1answer
35 views

How many combinations $S$ = $T \choose m$ of combinations $T$ = $n \choose k$ exist when each $p \in [1..n]$ has to appear in a subset of $S$?

The concrete task is this: I have a database with let's say $n = 10$ attributes. Out of these, I create subsets of dimension $k = 3$. Hence, $T$ = $n \choose k$ = 120. Thus, I have subsets like ...
1
vote
3answers
178 views

A particular combinatorial identity

I have to do an estimate and I have to rewrite the following term: $$ \sum\limits_{k=0}^{n-1} \binom{n-1}{k} \frac{k}{n-k} $$ How can I do? Following the first answer given below, I deduce that ...
2
votes
2answers
61 views

Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.

Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications" Let P(n) be the number of strings not containg two containing ...
1
vote
0answers
16 views

Divided power question.

Let $E$ be a free module, we define the $r$-th divided power as the dual of the symmetric power $D_r(E):=(S_r(E^*))^*$. For every $u \in E$ we can define its $r$-th divided power $u^{(r)} \in D_r$ by ...
0
votes
0answers
14 views

Book/refrence recommendation on Set Cover Problem

Can someone introduce a book that covers the set cover problem defined in this link: https://en.wikipedia.org/wiki/Set_cover_problem The book should describe the problem from the basics and has an ...
1
vote
1answer
65 views

How many non decreasing sequence of length k is possible?

If we have a set like this { 1A ,2A ,2B, 3A, 3B, 3C}, how many non decreasing sequence is possible, such that number in left is less than number in right of length k? i.e, Length = 2 then the ...
0
votes
1answer
45 views

$n$-words from the alphabet $A=\{0, 1, 2, 3\}$. How many of them have an even number of zeros and ones?

Consider all $n$-words from the alphabet $A=\{0, 1, 2, 3\}$. How many of them have an even number of zeros and ones? I showed that the number of $n$-words from $\{0, 1, 2, 3\}$ with an even number of ...
2
votes
1answer
31 views

Maximal Triangle Partitioning in n lines

Recently I was given the following problem at work: Given a 5 pointed star, draw two straight lines through it so that there are 10 minimal triangles within the drawing. It took some work but I ...
1
vote
0answers
26 views

subvariety of $(\mathbb P^1)^4$.

Let $S$ be the sub-algebra generated by the set $S=\{ x_1x_2y_3y_4,\ x_1x_3y_2y_4,\ x_1x_4y_2y_3,\ x_2x_3y_1y_4,\ x_2x_4y_1y_3,\ x_3x_4y_1y_2 \}$ of homogeneous polynomials. I need to compute ...
0
votes
0answers
28 views

Is there any (simple) way to count the number of distinct Hamiltonian cycles of an incomplete graph?

Simply put given a graph with a set number of vertices, not k-regular and not complete is there anyway to count the number of distinct Hamiltonian cycles.
1
vote
3answers
72 views

How to find the number of spanning trees for a cube?

Can you tell me a way of finding the total number of spanning trees in a $Q_d$ undirected labelled graph for $d = 3$. I know that the answer is 384, but the way (I know there are many.) of finding ...
1
vote
1answer
31 views

How to determine lexicographically the smallest Prüfer-Code of a spanning tree?

First, lexicographically the smallest means e.g. 112 < 121 and 121 < 211. EDIT: Then how to determine the minimal Prüfer-Code of a spanning tree from the given graph: Should I first find ...
0
votes
1answer
15 views

Number of subsets transversal both to a finite set and to its complement

I have a set $V$ of $n$ elements and a subset $A$ of fixed cardinality $2 \le k \le n-2$. How many subsets $Y$ are there such that $Y \cap A \neq \emptyset \wedge Y \cap A^c \neq \emptyset \wedge A ...
2
votes
2answers
57 views

Rooks Attacking Every Square on a Chess Board

8 rooks are randomly placed on different squares of a chessboard. A rook is said to attack all of the squares in its row and its column. Compute the probability that every square is occupied or ...
5
votes
2answers
122 views

How many words can be formed using letters such that first 2 letters are…

We make an assumption that any combination of letters is a word and we should take repetition into account because that would mean the same word. How many words can be formed using all the letters in ...
2
votes
1answer
43 views

Slot Machine and Fixed Reels

Let's say we have a slot machine, with $3$ reels. For simplicity let's only consider one line. We have symbols $A,B,C,D$ in each reel. $N_A$ denotes how many times that symbol appears in each reel. ...
6
votes
1answer
97 views

Asymptotics of $\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}$, is it $\frac{2}{\pi n}$?

I am trying to work out the asymptotics of $$\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}.$$ My numerical experiments suggest it might ...
3
votes
2answers
98 views

Why is the Ramsey`s theorem a generalization of the Pigeonhole principle

German Wikipedia states that the Ramsey`s theorem is a generalization of the Pigeonhole principle source But does not say why this is true. I am doing a presentation about the Ramsey theory and also ...
1
vote
0answers
25 views

Choosing k pairs l distance apart from n numbers

I need to choose $k$ pairs of numbers out of first $n$ natural numbers such that the elements in each pair are $l$ distance apart. For example, if $n = 10, k = 3$ and $l = 2$, $\{(1,3),(4,6),(7,9)\}$ ...
1
vote
2answers
41 views

Number of arrangements in which not all the vowels are together

How many arrangements of the letters of the word ‘BENGALI’ can be made (i) If the vowels are never together. I dont want the solution by negation method. I have seen the solution on ...
3
votes
1answer
74 views

Multiple of $p$ in first $p+1$ Fibonacci Numbers

Defining $F_0 = F_1 = 1$ and $F_{n+1} = F_{n} + F_{n-1}$ for $n>0$ gives the Fibonacci sequence, and it is well-known that modulo $p$, one of the first $p+1$ terms is $0.$ In fact, more is known, ...
1
vote
1answer
42 views

(Combinatorics) number of compositions of $n$ into $k$ parts so that $i$-th part is not larger than $a_i$

Let $a_1,a_2,\ldots,a_k $ be non negative integers, and let $a(n)$ be the number of compositions of $n$ into $k$ parts so that $i$-th part is not larger than $a_i$. Find the ordinary generating ...
-1
votes
1answer
36 views

Possible outcomes [closed]

You have a set of marbles consisting of $4$ red, $3$ green, $2$ blue, $3$ orange, $2$ yellow, and $3$ purple marbles. How many sets of six marbles include at least one blue marble?
0
votes
1answer
54 views

An interesting combinatorial identity [duplicate]

I'm self studying Burton's number theory and came across the following problem: Prove that: $\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}=n2^{n-1}$ So I tried expanding $n(1+b)^{n-1}$ with the ...
7
votes
3answers
110 views

Random Sequence of Alternating Increase/Decrease Numbers

The problem statement: Repeatedly pick a random number (uniformly-distributed) between $0$ and $1$. Keeping going while the second number is smaller than the first, the third number is larger than the ...
1
vote
1answer
93 views

A question in combinatorics

Given a sequence of $0$s and $1$s think of it as blocks of $0$s and $1$s. Like $0001101001$ is a sequence of blocks $000$,$11$,$0$,$1$,$00$,$1$ How may ways can one pick $t$ bits from a $0/1$ ...
0
votes
3answers
75 views

How many arrangements of the numbers satisfy a divisibility condition? [closed]

How many ways can one arrange the numbers 21,31,41,51,61,71,81 such that sum of every 4 consecutive numbers is divisible by 3 ?
1
vote
3answers
66 views

Prove $ \sum_{x=0}^n \binom{n}{x} = 2^n$ using binomial expansion? Right or wrong?

I am in a probability and statistics class. This is one of the first proofs we are supposed to do I am not sure where to start. I have done some research and I have seen proof by induction for ...
3
votes
3answers
83 views

Graph Theory - what are related fields in maths?

I am an undergraduate student who hoping to self teach Graph Theory. I have studied elementary graph theory before, and have recently started reading 'Bollobas - Modern Graph Theory'. What are your ...
2
votes
2answers
35 views

Counting nearly-sorted permutations

Let $[n]$ denote the set $\{1,2,\ldots,n\}$. We call a permutation $\sigma:[n]\to[n]$, $(n,k$)-nearly sorted if $$\forall i\in [n]: |\sigma(i) - i|\le k,$$ i.e., every element is shifted at most ...
2
votes
2answers
38 views

Write a number N as a sum of K numbers

I need to find the no of ways of partitioning a number N as a sum of K non-negative numbers. Zeroes are also needed to be included in the sum. Ordering does matter. Example- For $N=2,K=3 $ ...
1
vote
3answers
91 views

Finding the Closed Form of: $\sum\limits_{i=1}^n k\cdot{n-2 \choose k-2}$

I am stuck with this example in the textbook: find a closed form of: $$\sum\limits_{k=1}^n k\cdot{n-2 \choose k-2}.$$ I haven't found anything helpful on the web. Thanks for any advice.
0
votes
1answer
40 views

(combinatorics)Use compositional formula $G(x)$=$\sum_{n>=0}^\ g_n{x^n\over n!}$ ,and then find $g_n$

$g_n$=the number of ways of selecting a permutation of length n,and then selecting a cycle of that permutation. Use compositional formula $G(x)$=$\sum_{n>=0}^\ g_n{x^n\over n!}$ ,and then find ...
3
votes
1answer
49 views

Finding the number of primes numbers using exclusion/inclusion principle: What am I doing wrong?

I want to find the number of primes numbers between 1 and 30 using the exclusion and inclusion principle. This is what I got: The numbers in sky-blue are the ones I have to subtract. The others are ...
-2
votes
1answer
28 views

Stable matching solutions

The stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the ...
0
votes
1answer
52 views

How many pairs of consecutive integers? [closed]

How many pairs of consecutive integers? How many pairs of consecutive integers between and inclusive 1000 to 2000 is no carry required when the two integers added ? for example: 1001+1002=1003 is a ...