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)

3
votes
4answers
284 views

why isn't the counting principle giving the right answer?

Note : This is not homework, it is self-study. An employer interviews eight people for four openings in the company. Three of the eight people are women. If all eight are qualified, in how many ...
-4
votes
1answer
43 views

Clique and anti clique in a graph [closed]

I have been stuck for long time on this question: Let $A$ and $B$ be sets such that $|A| = 8$ and $|B| = 5$. Calculate how many functions $f:A\to B$ there are such that there isn't a member of ...
2
votes
2answers
28 views

Permutations with Condition

I have looked at this old problem in my textbook: How many permutations $\pi \in S_n (n \geq 3)$ meet the requirement: $\pi (1) < \pi (2) $ or $\pi (1) < \pi (3)$? I am not sure how to ...
-2
votes
0answers
49 views

Number of solutions of the equation $x_1+x_2+\cdots+x_n=3$ with constraint [closed]

Find number of solutions of the equation $$x_1+x_2+\cdots+x_n=3,$$ where $x_i\in\{-1,1\}$, and $\sum_{i=1}^kx_i<3$ for $k=1,2,\ldots,n-1$. In general, find number of solutions of the equation ...
1
vote
1answer
61 views

Solve $n(n+1) \equiv 0 \pmod{1004}$

Solve: $$n(n+1) \equiv 0 \pmod{1004}$$ For the smallest possible $n > 0$. It's either $n \equiv 0$ or $n \equiv -1 \pmod{1004}$. The correct answer is $251$, I'm not sure how though.
5
votes
3answers
98 views

How many ways to arrange the flags?

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ be the number of distinguishable arrangements ...
2
votes
1answer
40 views

Prove that $\displaystyle \binom{n}{r} \leq \displaystyle \binom{n}{\lfloor{\frac{n}{2}}\rfloor} $ is true [duplicate]

I was trying to prove $\displaystyle \binom{n}{r} \leq \displaystyle \binom{n}{\lfloor{\frac{n}{2}}\rfloor} $ where $r=0,1...,n$ I supposed that n is even and tried to divide: $\frac{\displaystyle ...
3
votes
3answers
76 views

Combinatorics - Distribution of Coins

I am preparing for a competitive exam. Sorry if the question sounds naive. The Below example was listed when I was studying Fundamental Principle of Counting which is If you must make a number of ...
3
votes
1answer
42 views

One-to-One correspondence in Counting

I have a confusion on the one-to-one correspondence in combinatorics. Take the problem: In how many ways may five people be seated in a row of twenty chairs given that no two people may sit next ...
-1
votes
1answer
36 views

How to calculate the number of possible combinations? [closed]

I have 110 labels that can have one of three values: 1, 0 or "?" The first time I receive a set of these labels, it could look something like this: ...
-1
votes
1answer
54 views

Find the number of six-digit numbers that can be formed

find the number of six-digit numbers that can be formed using the digits from the number 112 233. If these numbers are arranged in ascending order,find a.) the largest number. b.) the 30th number. ...
-1
votes
2answers
37 views

ways to buy the six marbles [closed]

A boy wishes to buy exactly six marbles. There are four different colours of marbles available. In how many ways can he buy six marbles? hint:arrange 111 000000
19
votes
1answer
368 views

What function satisfies $F'(x) = F(2x)$?

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed ...
3
votes
1answer
37 views

A problem on counting sub-graphs

How many distinct sub-graphs of a complete graph of $n$ labelled vertices are there, such that the sub-graph is a spanning tree connecting all the vertices and the degree of no vertex is more than ...
4
votes
2answers
111 views

Maths Puzzle: Partitioning a set into two disjoint sets

Le $X$ be the set of all non-empty subsets of $\{a,b,c,d,e,f\}$. So $X=\{a,b,c,d,e,f,ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef,abc,\cdots,abcdef\}$; i.e., $|X|=63$. We want to partition $X$ into ...
0
votes
1answer
30 views

Given the size of $\mathscr{U}, A, B$, how many possible combinations of $A$ and $B$ such that $A\cap B \neq \varnothing$?

Given the $\mathscr{U} = n, |A| = c_1$, how many possible set $B$ with size $|B| = c_2$ are there, such that $A \cap B \neq \varnothing$.
5
votes
4answers
97 views

Verify that $\binom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$ for $n \geq 4$

Verify that for $n \geq 4$ $$\dbinom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$$ Now present a combinatoric argument for the above. First, by verify does ...
1
vote
1answer
60 views

Construction of Rauzy Fractals with substitutions without a fixed point

The formal definition of a Rauzy fractal can be found at the beginning of this paper Using Sage-math-cloud, I can generate Rauzy fractals of substitutions that I choose. Should I choose the ...
0
votes
1answer
70 views

Verifying coin flipping result

An interesting coin flipping game is described here: flip a fair coin, stopping whenever you like, with a maximum number of tosses. Try to maximize the ratio of heads to total flips. What is the ...
4
votes
1answer
93 views

What tactics could help with this probability questions

I'm not too sure if this question is solvable (I sort of just thought of it yesterday) but when I brute force numerical answers on my computer they seem to show a pattern, so I believe it to be ...
10
votes
1answer
1k views

Why isnt there only one way of painting these horses?

If you have $11$ identical horses in how many ways can you paint 5 of them red 3 of them blue and 3 brown. My intuition instantly tells me there is only one way of doing this. I mean if the ...
2
votes
1answer
39 views

Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective.

Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective. Say $g(n,r,m)$ is the number of such combinations. The two cases of $m=r$ and $m=1$ ...
11
votes
2answers
89 views

Let $x$ be an irrational number. Prove that there exist infinitely many rational numbers $\dfrac pq$ that satisfy the following

$$\bigg|\,x-\dfrac pq\,\bigg|<\dfrac 1{q^2+q}$$ My idea would be to solve the inequality for $\frac pq$ and then somehow use the pigeonhole principle. Is this heading in the right direction? Any ...
2
votes
2answers
78 views

Messaging probabilities

New to site! I'm a near-retirement cellist who likes to mess with math, but I have a probability problem beyond me. I'm part of a large family - we have twenty-four people who send texts back and ...
-4
votes
0answers
49 views

The sum $\sum_{k=0}^m(-1)^k { n \choose k}$ [closed]

I am trying to evaluate $$\sum_{k=0}^m(-1)^k { n \choose k}$$ I'm struggling on this one, I'm pretty sure you have to use a pascal identity.
1
vote
2answers
26 views

Probability of getting same configuration in 2 throws with R dices

EDIT: There's same question already: Probability of throwing the same multiset twice in a row with six dice I'm trying to find general solution for a problem from Feller's book (p. 56): What ...
3
votes
2answers
79 views

Graph theory-related problem, unit distance graph, pairs of people with restraining orders

This problem is for my own exploration, not for class. The problem goes as follows: There are $n$ pairs of people with restraining orders against one another. However, all $2n$ people are friends ...
3
votes
5answers
87 views

How many $5$ element sets can be made?

Let $m$ be the number of five-element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find the remainder when $m$ ...
0
votes
1answer
50 views

Mountain of coins

Let a mountain of coins be an arrangement coins in rows such that the coins in each row form a single block, and that in all rows (except the bottom row) each coin touches exactly two coins from the ...
1
vote
1answer
48 views

Special Palindromic String

A string of length $N$ can be made from $6$ characters $a$, $b$, $c$, $d$, $e$ and $f$. There are some rules to make such a string: 1) $b$ can not come directly after $a$. 2) $d$ can not come ...
2
votes
3answers
101 views

Fast way to get a position of combination (without repetitions)

This question has an inverse: (Fast way to) Get a combination given its position in (reverse-)lexicographic order What would be the most efficient way to ...
3
votes
3answers
1k views

Place maximum Rooks on a chessboard

I am given a chessboard of size $8*8$. In this chessboard there are two holes at positions $(X1,Y1)$ and $(X2,Y2)$. Now I need to find the maximum number of rooks that can be placed on this chessboard ...
2
votes
1answer
52 views

Easiest way to find the 'area of a Venn diagram,' given certain information.

We have a bunch of intersecting regions: $$X_1,\dots, X_n,$$ all with non-negative volume, and we know $V(X_i)$ and $V\left((\cup_{a\in A}X_a)\cap (\cup_{b\in B}X_b)\right)$ for any disjoint ...
2
votes
1answer
52 views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length ...
1
vote
1answer
22 views

Writing a Sum of Partition Items in Combinatorial Form

For each partition $\lambda$ we can define \begin{equation} n(\lambda) = \sum_{i \geq 1}(i-1)\lambda_i. \end{equation} According to my book this is equivalent to \begin{equation} n(\lambda)=\sum_{i ...
0
votes
0answers
45 views

Question on how to manipulate terms in this expression

sorry for the vague title, i dont know how else to express what i mean with this question. But what i need to do is find out which terms on the RHS of the expression are constants. It is clear that it ...
5
votes
2answers
52 views

Floor Function Equation

How many positive integers $ N$ less than $ 1000$ are there such that the equation $ x^{\lfloor x\rfloor} = N$ has a solution for $ x$? (The notation $ \lfloor x\rfloor$ denotes the greatest ...
21
votes
1answer
372 views

What is the intuition behind generating functions? What makes them valuable?

I'm sorry if this question makes no sense. I have been reading generatingfunctionology and I have been able to solve the problems in the first chapters and I understand the mechanism I have to follow ...
0
votes
1answer
21 views

Representing a combinatorial sum with an equation

I am trying to represent a situation with an equation that is fairly conceptually simple, but I am not sure what is the proper way to represent it as a formal mathematical equation. I have a set of n ...
1
vote
1answer
16 views

Maximal number of subsets with 3 elements and small intersection - special Constant Weight Codes

in the middle of some proof I encountered a combinatorial problem and tracked it back to the theory of Constant Weight Codes. Those problems seem hard to solve, but my question is rather specific, so ...
0
votes
0answers
30 views

Calculating the minimum number of players required for a system to operate

Players wish to find other players to play games against, games are 1 v 1. Games are played in discrete time periods of 1 hr on the hour for one week (i.e. starting Monday 00:00 and ending Sunday ...
3
votes
2answers
57 views

Maximum and minimum Expected values when taking colored balls

We have a sack with $60$ balls. From them $15$ balls are red, $15$ green, $15$ blue and $15$ yellow. We take $30$ balls from the sack. What's the expected number of balls of the color from which ...
0
votes
4answers
47 views

Choosing a ball randomly from each urn

I am stucked at this combinatorics/probability problem: There are 10 urns, each contains 8 balls numbered 1,2,...,8 If we randomly choose 1 ball from each urn, what is the probability that the ...
1
vote
1answer
43 views

Find the Sum using bijection

Find the sum of $S=\displaystyle\sum_{i,j,k \ge 0, i+j+k=17} ijk$. I am looking for a solution that uses some bijection. I couldn't find any bijection. I am able to do the problem by other method by ...
0
votes
1answer
105 views

number of ways to choose a convex subset that contains exactly 98 points (from MIT-Harvard Math Tournament) [closed]

A set of points is convex if the points are the vertices of a convex polygon (that is, a non-self intersecting polygon with all angles less than or equal to $180^\circ$ ). Let $S$ be the set of points ...
8
votes
3answers
153 views

Non combinatorial proof of formula for $n^n$?

I came across the below identity: $$ n^n=\sum_{k=1}^n\frac{n!}{(n-k)!}\cdot k\cdot n^{n-k-1} $$ A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where ...
1
vote
2answers
48 views

Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
0
votes
2answers
69 views

Find the coefficient of $x^{17}$

Find the coefficient of $x^{17}$ in:$$ (1 + x^5 + x^7)^{20}$$ $x^{17} = x^{5} x^5 x^{7}$ I would say: $$\frac{17!}{5!5!7!} $$ But this isnt the correct answer. I know I need to use ...
2
votes
1answer
52 views

Homomorphism of Free Groups

I am reading the theorem of homomorphism of free group from Fraleigh's text in $\S$36 and could only get a fuzzy idea at best: Let $G$ be generated by $A = \{a_i \mid i \in I \}$ and let $G'$ be ...
1
vote
1answer
37 views

TCP Connection, 6 Packets, Probability of certain arrival orders

So I have a very hard time with statistics and probability. This comes from not being able to extract what I need to do from the given information. I don't get why I can't solve such easy stuff... :( ...