This tag is for basic 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 (5)

0
votes
2answers
69 views

Visualizing generalized basic principle of counting

The basic principle of counting states: Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of m possible outcomes and if, for each outcome of experiment ...
0
votes
1answer
52 views

Round Robin for Team Matches

My question came from the Bridge-game (Teams). This is what happens: Ideally, there are 4 pairs (A,B,C,D). We have 2 tables. In every table, there are 2 pairs. One pair is sitting in the North-South ...
2
votes
2answers
256 views

Counting Shaded Squares

In a $4 \times 4$ square, how many different patterns can be made by shading exactly two of the sixteen squares? Patterns that can be matched by flips and/or turns are not considered different. How ...
0
votes
1answer
37 views

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$?

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$? This is from the text A First Course on Probability by Sheldon Ross. The solution he ...
0
votes
0answers
47 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
3
votes
2answers
82 views

Counting divisibility from 1 to 1000

Of the integers $1, 2, 3, ..., 1000$, how many are not divisible by $3$, $5$, or $7$? The way I went about this was $$\text{floor}(1000/3) + \text{floor}(1000/5) + ...
0
votes
2answers
30 views

Simple Word problem question with boxes and bottles

Bottles are either packed in boxes of 6 *OR* 12. The number of small boxes must atleast be half the number of big boxes. If 240 bottles need to be packed, what's the minimum mumber of boxes needed? ...
0
votes
2answers
40 views

Different values of $x$ and $y$ between $\sqrt{39}$ and $\sqrt{224}$

If $x$ and $y$ are whole numbers between $\sqrt{39}$ and $\sqrt{224}$, then how many different values can $x$ + $y$ have? OK, first I found that the set numbers are: $$7, 8 ,9 ,10 ,11 ,12, 13,14$$ ...
1
vote
1answer
31 views

Combinatorial interpretation of identity for stirling number of second kind

I'm trying to find a combinatorial interpretation for the following identity $$S(n+1, m+1)=\sum_{k=m}^{n}\binom{n}{k}S(k,m)$$. And am having a lot of trouble thinking of one. Any pointers?
0
votes
1answer
28 views

what is the number of possibilities

I have 9 variables that can vary each from 0 to 100.(natural number). And the sum of the first 3 should be between 20 and 30. And the sum of the 9 variables should be equal to 100. What is the number ...
0
votes
1answer
197 views

How many ways are there to put 5 identical balls into 2 different boxes?

The only way I know how to solve this problem is by drawing a table: Making $6$ the answer. ...
0
votes
4answers
44 views

Finding nth term application problem

I was given this question class today and I wasn't quite sure how to solve it "There are $10$ computers all connected with a cable to each other computer" 1) How many wires are there? 2) How many ...
4
votes
2answers
189 views

Green balls and Red balls, probability problem

I'm studying for my exam and I came across the following draw without replacement problem : ...
1
vote
2answers
37 views

The binomial formula. how to show: $\Sigma_{k=0}^n k \binom{n}{k} = n2^{n-1}$ [duplicate]

Does anyone know how to show that: $\Sigma_{k=0}^n k \binom{n}{k} = n2^{n-1}$? I think we are suppose to use the binomial formula for that.. Thank you!
2
votes
2answers
51 views

number of options to divide $n$ white balls into $r$ cells

I am trying to solve the following question: number of options to divide $n$ white balls into $r$ cells. or, more specifically: what is the number of options to divide 4 white balls into 3 cells? ...
2
votes
1answer
66 views

Seating $2n$ people around a table with each person has at most $n-1$ friends

I am trying to show that with the setting in the title, that it is always possible to arrange the seats so that no person sits beside his/her friend. I am not good at this kinds of problems at all, ...
0
votes
1answer
24 views

Sperners lemma how to mark internal vertices

Was reading sperners lemma from this http://www.math.hmc.edu/funfacts/ffiles/20001.4.shtml Couldn't understand certain things How to mark internal vertices? I could have mark some other number for ...
1
vote
1answer
33 views

triangles and lines

There are 12 points in a plane. If 4 of them are on a straight line and no other 3 points are on a straight line, then find the difference between the number of triangles and the number of straight ...
4
votes
1answer
109 views

How many surjective functions are there from $A=${$1,2,3,4,5$} to $B=${$1,2,3$}?

I want to find how many surjective functions there are from the set $A=${$1,2,3,4,5$} to the set $B=${$1,2,3$}? I think the best option is to count all the functions ($3^5$) and then to subtract the ...
2
votes
2answers
758 views

Number of ways to form a 3-letter word with repetition allowed?

The additional rule is: no letter can be used more often than it appears in MILLENNIUM? (Which is pretty logical I guess) MILLENNIUM = MM, II, LL, NN, E, U My logic: Case 1: Double letters + 1 ...
0
votes
3answers
78 views

Forming words from letters

If we have five letters e.g. a,b,c,d,e a. How many four-letter words can we make that have exactly two vowels and two consonants? b. from (a), how many of those words have distinct vowels?
0
votes
2answers
165 views

No. of 5-digit monotonic numbers

The monotonic number is made of digits 1, 2, …, 9, such that each subsequent number equal to or greater than the previous number. Examples: 11119, 12369, 18999 etc. I understand that I can isolate ...
0
votes
3answers
69 views

Are the following sets countable?

I'm trying to determine if the following sets are countable: (a) $\mathbb{Z}^{[0,1]}, (b) [0,1]^{\mathbb{Z}}, (c) \mathbb{Z}^{\mathbb{Z}}$, (d) the set given by functions $f:\mathbb{Z}\to\mathbb{R}$ ...
0
votes
2answers
42 views

Solving Problem by different Method ( non-induction)

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method). I want to find number of solution for $$0 \le ...
1
vote
0answers
66 views

Proof of the Catalan number formula using Dyck walks

In our notes we were given the formula $C(n)=\frac{1}{n+1}\binom{2n}{n}$ It was proved by counting the number of paths above the line y=0 from (0,0) to (2n,0) using n(1,1) up arrows and n(1,-1) down ...
2
votes
5answers
239 views

Deriving Closed Form for a Recursion via Generating Functions

Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$. Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain $$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
1
vote
0answers
59 views

How to answer the following question related to counting the number of trees of a graph?

I am asked to prove the equality $$ 2(n-1)n^{n-2} = \sum_{k=1}^{n-1} \binom{n}{k} k(n-k)T(k)T(n-k) , $$ where $T(k)$ is the number of different trees with $k$ numbered vertices. I think the ...
2
votes
3answers
161 views

Functional equations and generating functions

The problem asks to find the functional equations for the generating functions whose coefficients satisfy $$ a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1 $$ There's an example that's ...
1
vote
2answers
56 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...
2
votes
3answers
122 views

Solving recurrence relation with generating functions - Nearly got the answer

I'm trying to solve the following recurrence relation (Find closed formula) using generating functions: $f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ I'm having a small difficulty at the end and can ...
0
votes
2answers
64 views

Counting integer solutions

how many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 24$ where $x_1 \ge 0, x_2 \ge 1, x_3 \ge 2, x_4 \ge 3$ I have no idea how to go about this problem. Any help would be ...
0
votes
0answers
73 views

Alternating permutation exponential generating function

A permutation pi is alternating if pi_1 > pi_2 < pi_3 > pi_4 <….Let a(n) be the number of alternating permutations of size n. (a) Find a recurrence relation for a(n). (b) Evaluate the ...
0
votes
5answers
138 views

How many non-ordered quadruples satisfy $a+b+c+d=18$?

How many non-ordered quadruples satisfy $a+b+c+d=18$? I know how to do this if this is ordered quadruples, but in non-ordered quadruples $(1,1,1,15)$ is the same as $(15,1,1,1)$ so you have to ...
1
vote
1answer
71 views

counting Number of matrices

We have a $2 \times 2$ matrix. We are given the trace of the matrix as $N$. Also, all elements of the matrix are greater than or equal to $1$. And, the determinant of matrix is $\geq 1$. QUESTIONS: ...
5
votes
0answers
68 views

Maximal hamming distance

Here is a combinatorial problem : let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming ...
1
vote
1answer
48 views

question on combinatorics and number theory

We have an equation as: $a\times b < n$ where $n$ is any positive integer. Now my question is how many pairs of positive integers $(a,b)$ can be found to satisfy the equation. For example, ...
2
votes
1answer
116 views

Characterizing a certain set of matrices arising from binary trees

Suppose I have a binary tree, like v1 v4 \ / -------- / \ v2 v3 I can write a matrix for this tree whose $(i,j)$th ...
0
votes
1answer
89 views

Round table exponential generating function

Let $r(n)$ be the number of different ways to seat $n$ people around a round table. Find the exponential generating function for $r$. I believe $r(n)$ is just equal to $n!/n = (n-1)!$. So then I ...
0
votes
2answers
41 views

Question on counting

If 8 identical whiteboards must be divided among 4 schools, how many divisions are possible? For this, the answer is 11C3, and I know this is obtained using stars and bars counting method. ...
0
votes
2answers
169 views

Problem with Set Theory Counting Principle

I'm trying to apply the counting principle to the following: "Of 300 people: 35 - bicycle and car. 40 - car and bus. 60 - bicycle and bus. 90 - bicycle. 70 - car. 105 - bus. 25 - bicycle, car, and ...
1
vote
0answers
54 views

Minimum Number of Possible Combinations to Predict Results of Double-Outcome Events

There are "n" different events. Each event can result in two possible outcomes (ie Yes or No). You make a guess for each event and list this (ie YYNYYNN for 7 events). To guarentee to correctly guess ...
1
vote
1answer
64 views

Number of ordered pairs $(x,y)$ of positive integers such that $x+y=90$ and their GCD is $6$

The number of ordered pairs $(x,y)$ of positive integers such that $x+y=90$ and their greatest common divisor is $6$ equals $8$. But I did this way: As $x$ and $y$ both are divisible by $6$, so ...
1
vote
1answer
22 views

Probability of winning after x coin tossses

I'm not sure how to reason about this problem. Say we toss 12 coins in a row. What is the probability that 7 of those tosses were heads, and five were tails? I've tried thinking of it as the number ...
10
votes
3answers
831 views

What is the Probability that a Knight stays on chessboard after N hops?

Say a $8 \times 8$ chessboard as per picture. A position is represented here by co-ordinates $(x,y)$. A move is aslo considered as valid, where the Knight lands outside the chessboard [ For eg. ...
1
vote
1answer
63 views

Probability: 30 balls in a bucket, homework

i need some help with some homework, first time i am doing probability and statistics, id like to know if my 2 answers below are correct, and how i can solve the remaining 2. There are 30 balls in a ...
1
vote
2answers
89 views

“Relatively Close” Soccer Game

A soccer game between 2 teams is "relatively close" if the scores never differ by more than 2. In how many ways can the game be "relatively close" for the first 12 goals? Just to clear it up, the ...
1
vote
1answer
136 views

Probability that between two Bernoulli sequences, one will get 'ahead' and remain there to sequence end.

As per title, given two Bernoulli sequences both of length $N$ with probability of success $P$ the same for both, what is the probability that one will 'get ahead' in its sum from 1st of the sequence ...
3
votes
1answer
113 views

Number of subsets without consecutive numbers

Consider $S=\{1,2,\ldots,15\}$. Let $X$ denote the number of subsets of $S$ of four elements which contain no consecutive numbers. The claim is that $X$ equals the coefficient of $x^{14}$ in ...
1
vote
1answer
46 views

Simplifying Sum of Subsets

Given sets $A$ and $R$ such that $R \subseteq A$ and a number $x \leq |A|$, I am trying to simplify the following sum: $$\begin{equation*} \sum_{R \subseteq W \subseteq A : |W| = x} \Big( \sum_{Y ...
1
vote
1answer
241 views

Pigeonhole Principle Question: Given any 5 points inside a square of side length 2, there is always a pair whose distance apart is at most $\sqrt2$

The question I am looking at: Prove that given 5 points inside a square of side length 2, it is always possible to find two of them whose distance apart is at most $\sqrt2$. This looks to me like I ...