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)

2
votes
2answers
30 views

Prove that, given any positive integer n, some multiple of it must be of the form 99…900…0

Prove that, given any positive integer n, some multiple of it must be of the form 99...900...0 Give me a hand, please.
1
vote
1answer
28 views

octagonal number theorem $q$-Pochhammer symbol expression

Setting the exponents of this analogue of the series in Euler's Pentagonal Number theorem to be the octagonal numbers: $$U(q)= \sum_{n\in\mathbb{Z}} (-1)^{n}q^{n(6n-4)/2}$$ in mpmath: ...
0
votes
0answers
15 views

Number of solutions for a multiple traveling salesman (mTSP) problem

Traveling salesman problem (TSP) with n-number of cities and only one salesman has "nPn" solutions which is n! but when you have more than one salesman, say k-number salesman, to travel n-number of ...
1
vote
3answers
61 views

$2^n$ binomial theorem

How can I prove that $$2^n=2\left({n \choose 0}+{n \choose 2}+{n \choose 4}+\dots\right)$$ using the binomial theorem. I've tried expanding $(x-y)^n$ with multiple different values of $x$ and $y$ but ...
3
votes
1answer
46 views

solving a combinatorial problem

Alex has $N$ dice; each of them has $K$ faces numbered from $1$ to $K$. Now he has arranged the $N$ dice in a line. He can rotate/flip any die if he wants. How many ways he can set the top faces such ...
2
votes
1answer
61 views
+100

A Law of Large Numbers Without Replacement

Let $(n_1,...,n_r)$ be $r$ positive integers, and let $n=n_1+...+n_r$. Fo each positive integer $m$ consider an urn containing $mn$ balls, of which $mn_1$ are of type 1,..., $mn_r$ of type r. For each ...
0
votes
1answer
22 views

Proving a combination problem?

Given n and r are positive integers, how should I go about proving this statement? I tried using the combination forumula but I didnt really came close of solving it. Any help is appreciated. ...
3
votes
2answers
46 views

Expected number of cycles in permutation

Consider a random permutation of $1,2,\ldots,n$. What is the expected number of cycles in it? I thought about using linearity of expectation, but here it's not clear how we can break down the main ...
0
votes
0answers
17 views

Properties of the 'forgotten' symmetric polynomials

In I.G. Mcdonald "Symmetric Functions and Hall Polynomials" pg.22, the forgotten symmetric functions 'f' are introduced very briefly as the result of applying an involution w to the monomial symmetric ...
1
vote
1answer
20 views

Question regarding an algebraic manipulation in GFology

How does the author arrive at the last equality in the first line, i.e.$$\text{why is } [x^k]\frac{1}{1-y(1+x)} = \frac{1}{1-y}[x^k]\frac{1}{1-\left(\frac{y}{1-y}\right)x} \text{?}$$
1
vote
1answer
81 views

combination/induction question, number of ways you can divide n people into groups of 1 or 2

this is homework!! Let $n \geq 1$ be an integer and consider $n$ people $P_1,P_2,\ldots,P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group ...
0
votes
3answers
34 views

Ways of spending money combinatorial problem

Suppose person X has $12$ dollars.In each of the first 5 days he buys one of the following items. 1.Item A for $1 2.Item B for $2 3.Item C for $3. In how many ways can he spend the money ...
0
votes
0answers
17 views

Combinatorial proof of an identity of Striling number of first kind

I can prove this identity using induction but i was looking for a combinatorial proof for this identity regarding stirling numbers of first kind. How should i proceed? Where, Thanks in advance.
5
votes
0answers
90 views

Number of restricted ways to two-color a necklace [duplicate]

There are $n$ beads placed on a circle, $n\ge 3$. They are numbered in random order as viewed clockwise. Beads for which the number of the previous bead is less than the number of a next bead are ...
0
votes
0answers
51 views

A problem related to combinatorics

If we choose $r$ objects from $n$ objects, where every combination of objects always contains a particular object, the number of ways for such a choice equals $C(n-1,r-1)$. Can someone explain why? ...
4
votes
1answer
66 views

No. of integral solutions of $x_1+x_2+x_3+x_4=20.$

I've to solve a no. of questions of this type but don't get how to do it: Determine the no. of integral solutions of $x_1+x_2+x_3+x_4=20.$ given the constraint that $$1\leq x_1\leq ...
1
vote
2answers
43 views

Number of ways to group digits in {1,2,3,4,5,6,7,8,9} into numbers, while maintaining order

I have a set of integers from 1 to 9, call it A: $$A=[1,2,3,4,5,6,7,8,9]$$ How could I find the total number of possible combination of numbers within that set, while maintaining order? For example, ...
2
votes
2answers
42 views

How many 7-digit telephone numbers have an odd number of even numbers?

((7 choose 1)*5^7) + (7 choose 3)*5^7) + (7 choose 3)*5^7) + (7 choose 1)*5^7) This is how I attempted to solve the problem, but I'm not sure if its correct.
7
votes
1answer
61 views

Sets of size at least $k$ with intersection of size at most $1$ cool problem.

At the OMM School every student goes to at least $k$ classes and two classes have at most $1$ student in common. Prove there is a set of $k$ classes where all of those classes have the same amount of ...
3
votes
2answers
62 views

$P(AB=BA)$ , $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$

Let $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$ ($p$ a prime number). Find the probability $P$ that $AB=BA$ that is $P(AB=BA)$ $$A=\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} ...
0
votes
3answers
38 views

Number of ways to park $10$ cars

Given $10$ cars (5 Fords, 3 Dodges, and 2 Hondas), how many ways can the cars be parked if there are (a) $10$ spots available? (b) $15$ spots available? My solution: (a) ${10 \choose 5} + {5 \choose ...
1
vote
2answers
12 views

Sum of Cells in Corner and in Center of Magic Square

For the magic square of order 4, the sum of 4 cells in each corner and sum of 4 cells in the center is the same which is equal to 34. But I don't have idea how to prove it. Any hint?
2
votes
1answer
33 views

On the number of cycles and independent edges in $K_{8}$

I am trying to find the number of cycles and $K_{2}$'s in $K_{8}$. That is, partition $8$ into all the ways such that the lowest part can be a $2$, so we have $8 = 8$, $6+2$, $5+3$, $2+3+3$, $4+4$, ...
0
votes
2answers
123 views

How many Binary numbers?

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$? My questions is, can I choose an $n$ randomly? For example, let's say ...
0
votes
1answer
29 views

Combo: Unambiguous expression - String

I am stuck on finding an unambiguous express so that it can produce all the strings in the given set, for the set of binary strings where for each block of zero's which are of length minimum 3 must be ...
-3
votes
1answer
41 views

Combinatorics binary strings [closed]

I am having trouble understanding ambiguity. Say you have something like {000,00000}* Why is would this be ambiguous?
4
votes
0answers
55 views

Ordinary or Rational Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These ...
7
votes
1answer
104 views
+50

The meaning of a definition involving multiple sums with Bernoulli numbers

Reading a paper regarding Bernoulli numbers, and I stumbled onto a definition. First let $$\frac{x}{e^x-1}=\sum_{k=0}^{\infty}B_k\frac{x^k}{k!}$$ The author then goes on to define new terms. Let ...
1
vote
3answers
33 views

Total number of possibilities

I have 3 buckets, 1st bucket has 5 red balls, 2nd bucket has 3 green balls and 3rd one has 2 blue balls. so I have total 10 balls in 3 buckets. I need to know, what are the possible combination ...
2
votes
1answer
28 views

$\sum_{i=0}^n (-1)^i \delta_i(\sum_{j=0}^{n+1} (-1)^j \delta_j) = 0$, given that $\delta_i \delta_j = \delta_{j-1}\delta_i$ whenever $i < j$

$\sum_{i=0}^n (-1)^i \delta_i(\sum_{j=0}^{n+1} (-1)^j \delta_j) = 0$, given that $\delta_i \delta_j = \delta_{j-1}\delta_i$ whenever $i < j$ This problem shows up in the middle of dealing with ...
0
votes
2answers
72 views

Biased coin flip from an unbiased coin flip

Von Neumman's method allows us to generate a fair coin flip from any unbiased coin flip using only two bits (two tosses) of information (http://en.wikipedia.org/wiki/Fair_coin). Is the reverse ...
0
votes
1answer
28 views

Predicting the outcomes of a subset of chess games correctly

Suppose $n$ games of chess are played. In how many ways can I predict the outcomes of $m$ of the games ($A$ wins, $B$ wins, there is a draw) correctly? Here's my solution. I can choose the $m$ ...
1
vote
1answer
32 views

The no. of ways dividing a polygon with $n+1$ sides into triangular regions…

Please if any one can help me explaining this concept,as I have my exam tomorrow and I can't proceed further due to this.... Let $h(n)$ denote the no. of ways dividing a convex polygon region ...
0
votes
2answers
41 views

Application of Principle of Inclusion-Excclusion [closed]

Let $$A=\{{1,2,...,300}\}$$ Find the number of subsets $\{a,b\}$ of A such that $a+b$ is the multiple of 3
2
votes
0answers
31 views

Threshold probability subset

Let $S=\{1,...,n\}$ and random subset $A \in S$ and $\forall a \in A$ we choose $a$ from $S$ with probability $p$. How find threshold probability for the property of $A$ to include 4 numbers ...
1
vote
1answer
42 views

Count the number of a kind of matrix

I want to count the number of $M\times N$ matrices with $0s$ and $1s$ which have exactly $k$ $1s$ and of which each column and each row has a least one 1. It is a little difficult for me. Could anyone ...
0
votes
2answers
41 views

How to solve $\frac{15!}{(x-1)!(16-x)!}=\frac{15!}{(2x+1)!(14-2x)!}$ for $x$?

I have to solve this problem. $$\frac{15!}{(x-1)!(16-x)!}=\frac{15!}{(2x+1)!(14-2x)!}$$ I imagine that the answer somehow lies in the recursive definition of $n!$ which is $n(n-1)!$. But I can't ...
1
vote
2answers
46 views

N circles in the plane

You are given a family of n pairwise intersecting circles in the plane. No three intersect(share a common point). Find a simple formula for counting the number of regions determined by these circles. ...
0
votes
2answers
32 views

Need help in proving combinatorial identity involving unions, intersections and complements over sets using induction

The identity is the following: $$\left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C = \bigcup_{i=1}^n (A_i^C\cap B_i^C)$$ I must use induction to prove it. Base. Ok, I think I got how to prove base case: ...
0
votes
1answer
42 views

Each Point in Cirlce

Each point in a circle is colored in one of 3 colors (blue, White, or red). Prove that one can find points that are vertices of an isosceles triangle, and either 3 points are all colored with the same ...
0
votes
1answer
32 views

how many boquets of 10 flowers can you make with 4 types of flowers

How many boquets of 10 flowers can you make with 4 types of flowers? Tough one. I heard using "stars and bars" is the approach, but still don't get it. thanks.
1
vote
2answers
67 views

combinatorial or algebraic proof of combinatorial identity

I would like to find out how to prove the following identity, assuming it is correct: $\displaystyle\sum_{r=0}^n\binom{n}{r}\binom{m+r}{l}=\sum_{r=0}^n\binom{n}{r}\binom{m}{r+l-n}2^r$ for ...
1
vote
2answers
23 views

Combinatorics. Picking items with and without replacement. Am I reasoning in a right way?

We have n keys and we want to choose right one to open the door. a. We choose keys w/o replacement. What is probability to choose right one: one the first try, second try, k-th try? b. What if we do ...
2
votes
3answers
53 views

How many ways can the average of n dice be a?

For example, if n = 2, and a = 3.5 one could have (1,6), (2,5), (3,3), (4,3), (5, 2), (6,1) = 6 if n = 10 and a =3.5, one possible combination could be (1, 6, 1, 6, 1, 6, 1, 6, 1, 6)
0
votes
2answers
31 views

Given numbers from $1$ to $N$, find the number of arrangements in which $a$ comes before $b$

We have $N$ numbers from $1$ to $N$. What is the number of arrangements in which number $a$ appears before number $b$? My solution: I keep number $a$ fixed at one location, and find the number of ...
1
vote
3answers
66 views

Draw 4 cards where: 3 cards same suit and remaining card of different suit

Four cards are drawn from a standard 52-card deck without replacement. Find the probability that exactly 3 cards are of the same suit and the remaining card is of a different suit. What I did: ...
0
votes
1answer
78 views

Pascal's Triangle

My question is the following; Q: Prove that if we move straight down in Pascal’s Triangle (visiting every other row), then the numbers we see are increasing. Found an answer but that doesn't count ...
1
vote
2answers
56 views

Solve for the number of students who took an exam.

An exam consisted of $28$ problems. Each student solved $7$ problems correctly. For every pair of problems solved, there are exactly $2$ students who solved them correctly. How many students took the ...
3
votes
1answer
46 views

Proving a Binomial Identity

Can you please help me with problem 25. I need to prove that $f(n+1)=2 f(n)$, where $f(n)$ is the LHS of the expression, from there on I can do it my self. I have tried using the binominal theorem ...